{"entities":{"Q867859":{"pageid":869707,"ns":120,"title":"Item:Q867859","lastrevid":50035573,"modified":"2026-01-12T18:18:14Z","type":"item","id":"Q867859","labels":{"en":{"language":"en","value":"Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5128021"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$8E87EEC5-9C8C-4BC3-B979-C732278B21B6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a82aecb68d66184c7a00f5f2e88b452c4235365","datavalue":{"value":{"text":"Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q867859$C4928225-5783-471D-8649-CF07D1E1E7E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"167d6b483a704bb68f83cea234b651ae1527ad70","datavalue":{"value":"1110.68169","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$C64CB23C-7370-4260-8123-94971300EE00","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1f732cbf1f5a68ea518754ac75a3e43eb85a3ef","datavalue":{"value":{"entity-type":"item","numeric-id":178353,"id":"Q178353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$E260BCDA-3A69-4683-A91C-C01F427B4FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5154d9f452c87a53238268589183b3b4627e016","datavalue":{"value":{"entity-type":"item","numeric-id":527401,"id":"Q527401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$BDD6913E-12D6-4721-AE0C-5C1AC03BE59A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$F3CAF9A9-FA0B-4398-8B98-9724E7FD947A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"97b507c351932721346fb052e20f9e8975c84342","datavalue":{"value":{"time":"+2007-02-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q867859$3067D173-6124-45B4-B228-9E51F97E3FD1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$C054984F-70C8-4853-9641-6BB3A29106AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$7D4442C0-D3E4-47C2-8BC3-2A4E5F021807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$2FF67E60-3EBA-43E4-84DA-B52C76AFFCA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$E8ED417B-A88F-4B30-9923-85D749A4D2A9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"92f685ebb028c6e69a84c17dce6f775c46c9f9fb","datavalue":{"value":"5128021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$136BAF6F-5A43-437A-BBEA-10BDEFB747B3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e6f2842ba16618da57de12b4c27b4274e41c364","datavalue":{"value":"approximation hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q867859$6087A054-6A7E-4B05-8B0B-2E29529A694C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d50bb4c955f6c519a142fbc9efe8b11036ec4d4","datavalue":{"value":"2SAT-deletion","type":"string"},"datatype":"string"},"type":"statement","id":"Q867859$D16E997F-C762-40B8-AD05-CBC244AD265E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q867859$0E250EAD-BB85-4BA6-AE61-63D95E4E2D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e52734bacf624bebd44dc277687e1b1bbb6580ca","datavalue":{"value":"\\(k\\)-approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q867859$7A52E787-4FF3-4FE5-8866-411FE2D056BA","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$BD8629BC-61EC-4CE6-B6A7-ED4040C56523","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"09a600b3b8a2650a688e552ba0c3d0ae2975746a","datavalue":{"value":"https://doi.org/10.1016/j.dam.2006.04.039","type":"string"},"datatype":"url"},"type":"statement","id":"Q867859$752C1AC1-0260-44E9-BF22-A271615C901C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"454139e3813a702324f0e60578ab892991d89521","datavalue":{"value":"W1972203976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$85603007-8FC2-48DD-9D20-211C0896F15E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aa2a1ac4e864d41c30b8a828a68a91d18d8ecae","datavalue":{"value":{"entity-type":"item","numeric-id":4258216,"id":"Q4258216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$4780A5B0-FF93-49FA-B3E7-A7A0A1055053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"264cd15f78b9795d676e715dfd2e735f58fc18b5","datavalue":{"value":{"entity-type":"item","numeric-id":3221758,"id":"Q3221758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$75C5B056-11E0-465E-BDEE-9F839748D6D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2bd2046a83bc0f68f71a2bf2db06fcbfb9ac34d","datavalue":{"value":{"entity-type":"item","numeric-id":4472486,"id":"Q4472486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$91A2125E-EFEF-45E1-9C5A-43248665259B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"662bf0b7e881dacafbad52f5cefe06bd2a17e84c","datavalue":{"value":{"entity-type":"item","numeric-id":2368970,"id":"Q2368970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$B095B948-5CD5-4DB6-BEEB-5B59891F67EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a085110f25069146b2ebfef0f9dedd979d8f36a1","datavalue":{"value":{"entity-type":"item","numeric-id":3579199,"id":"Q3579199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$B65AEED7-9A14-4ABA-B1AD-A7E59D5BBE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"978a6a974e4834f87547771d4b49ddcc8731f47c","datavalue":{"value":{"entity-type":"item","numeric-id":679458,"id":"Q679458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$969B275B-0966-4089-A57D-506A5CEDFE40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$0B90769D-A47B-4AF9-AE37-33042378DC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b58fad3b4ec3d547a24cb6c24802aad6e81000e4","datavalue":{"value":{"entity-type":"item","numeric-id":5716851,"id":"Q5716851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$BFD92824-96B6-431D-B8E5-6CF8B6C56C22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0891b0f78fe192ff4a86a61c6866f5144054df8d","datavalue":{"value":{"entity-type":"item","numeric-id":3128195,"id":"Q3128195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$149D218C-6AE8-4F9B-8E03-0B0A2B4CB76E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41e4f083b9b8c3cefd59525749074259a09a0360","datavalue":{"value":{"entity-type":"item","numeric-id":4737518,"id":"Q4737518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$11BC5556-9E7A-4A2E-BEB7-9FC7978C4615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a0983ce7a664c54ed4274f83ecbe33679a4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4074668,"id":"Q4074668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$DDAFB73A-9281-40EE-8C48-A9D20AE3FD6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a163c003fbc5b1f9b3cbaa6cf90d46a8c1c3a723","datavalue":{"value":{"entity-type":"item","numeric-id":4542575,"id":"Q4542575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q867859$D1227C18-A394-4868-BE07-00EC87C6A93D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cb09eb696ad77b85d06bd36ab8a17ca0ad0b218b","datavalue":{"value":"10.1016/J.DAM.2006.04.039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q867859$ACFEC4CA-2255-4042-85A1-F76EA087C3BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8ed0fd94f713c133b1903edf67dc8891871cc03","datavalue":{"value":{"entity-type":"item","numeric-id":5311102,"id":"Q5311102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32bd985f59c26acb80aef11423e8e2d688d2ca8f","datavalue":{"value":{"amount":"+0.9748072028160096","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q867859$83539E07-C270-44E6-AF4B-291F06FAE5E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90f9200e1a43cd7afef68a034c74667e054b7e46","datavalue":{"value":{"entity-type":"item","numeric-id":1351157,"id":"Q1351157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4103a44116534131effd5138c590d2946e86b14","datavalue":{"value":{"amount":"+0.8212928175926208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q867859$9B8A1AF3-5E87-4E19-8313-17B633BBA62D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d78bcebe9d6af1d737c4b93057c2a24032fc8dc","datavalue":{"value":{"entity-type":"item","numeric-id":1780843,"id":"Q1780843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e63aba8fa97751105d63cf63765488f19599d59","datavalue":{"value":{"amount":"+0.8132290840148926","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q867859$BABFCEEC-0ECE-4CEF-9B51-0A881E572892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6586d3772caf2671dab1a0b6d590c8c65becfd02","datavalue":{"value":{"entity-type":"item","numeric-id":4427868,"id":"Q4427868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"846d3b8b3a305cbd745c96da95c4c082d660298e","datavalue":{"value":{"amount":"+0.8001022338867188","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q867859$615E4BB3-F182-4779-98E1-BC50020C84DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"041548ccef668d26b14b69110ac0532e30ff48e4","datavalue":{"value":{"entity-type":"item","numeric-id":393120,"id":"Q393120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc462e116e10554281807e493fb4dce58585d5e0","datavalue":{"value":{"amount":"+0.7858622074127197","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q867859$A3E64152-5BDC-42DD-B78A-5F683F96D8D5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:867859","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:867859"}}}}}