{"entities":{"Q907218":{"pageid":909066,"ns":120,"title":"Item:Q907218","lastrevid":65256357,"modified":"2026-04-12T01:20:47Z","type":"item","id":"Q907218","labels":{"en":{"language":"en","value":"Extended formulation for CSP that is compact for instances of bounded treewidth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6534961"}},"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":"Q907218$E78F301F-2C6A-4146-A190-52B06AEC6813","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4ec0424a751faff0b8cd91d941013a983d4f9fee","datavalue":{"value":{"text":"Extended formulation for CSP that is compact for instances of bounded treewidth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q907218$53B1F004-3C1D-4A00-85E3-7132BDEEE1C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fab9ab99ddbf9fee837ccc64a57069ed9fb50668","datavalue":{"value":"1393.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$0FE366DA-9923-4E55-9AF4-07A0EAC18CC5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa63f642e27dbdecb94bd4e745870cb22f9dbc7d","datavalue":{"value":{"entity-type":"item","numeric-id":372973,"id":"Q372973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$BFF8C4E7-FBB7-4511-9943-B750B78D59B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"79e43499fdd6e0460794b611ebd926114b2c9177","datavalue":{"value":{"entity-type":"item","numeric-id":907217,"id":"Q907217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$81806FC0-D88C-4904-8F36-29A61CBA7C84","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$0958BF32-88BC-47E3-ADFB-7EBFAD1FEE3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e3f0504cdbec36416c8068369865aa5a0a508332","datavalue":{"value":{"time":"+2016-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q907218$7C4B40E1-3DC9-4570-A7D7-354F7EE5882A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5bc15acbe2c912386f050832fce7318637a8eb8b","datavalue":{"value":"https://arxiv.org/abs/1502.05361","type":"string"},"datatype":"url"},"type":"statement","id":"Q907218$4055F68A-4388-457C-9C13-8A9BEBFDC139","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d56a5198d3c81bae71c4c4e4bca3327b85997561","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p30","type":"string"},"datatype":"url"},"type":"statement","id":"Q907218$D9597DDF-0B69-44DC-B042-147B3C1C5AAE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"56f079dae5a6ef4ef2c210c0c64d399bb21b7bea","datavalue":{"value":"Summary: In this paper we provide an extended formulation for the class of constraint satisfaction problems and prove that its size is polynomial for instances whose constraint graph has bounded treewidth. This implies new upper bounds on extension complexity of several important NP-hard problems on graphs of bounded treewidth.","type":"string"},"datatype":"string"},"type":"statement","id":"Q907218$799B2F22-A737-49C9-B4C3-829974961B14","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$0B2FC2AD-EE78-4CC7-95EA-425D890717E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$8A43A3BB-945D-4F83-8450-9E234BD86727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$4E322ABB-CABA-4EAB-9D14-623AF71862FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$A30AAD56-ED3D-4806-B9C2-DF7E38844C5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c73f2e3bc8778b951d40ba9858f0fe0d1947db30","datavalue":{"value":"6534961","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$D319F83E-0896-4585-9B89-3900B1C58ED5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df25359605a7bacf8d12705a29fce2b79e2bb8b0","datavalue":{"value":"constraint satisfaction problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q907218$F44AF886-360E-453A-845C-BB6B102D7747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q907218$DB189BAB-7DEB-4B3C-A8B6-CD16A9963819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b46ef68fc07876073cc02e37407267eae98c2cb7","datavalue":{"value":"extended formulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q907218$966F3755-5974-4C6C-A670-838F0D1DFA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q907218$EF0A63B9-F235-479C-AE85-4D85695A561B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d57d68ed777850433efcc3de197edd817953ef26","datavalue":{"value":"treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q907218$12314718-E61F-4677-BEDC-D26ADCCD1FEF","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":"Q907218$3C7432D3-F4B0-4CCA-A71D-F05DE87AE983","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":"Q907218$43C78B89-BDF1-4427-95D4-7471B45B31AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eddb27c650d3e0013310cd1fc48ab87b2be7f4b9","datavalue":{"value":{"entity-type":"item","numeric-id":2386210,"id":"Q2386210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$BA1CF81F-7386-456B-94D9-F72A593175AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4a2fdb06f21d26cb09d5ec5cb36cf8a0aaa5986","datavalue":{"value":{"entity-type":"item","numeric-id":3177811,"id":"Q3177811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$8C21420B-40D0-476C-863C-F40D2DCBD739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"130de9bf1893a37422eb3474c849ad5f27ea501d","datavalue":{"value":{"entity-type":"item","numeric-id":5919994,"id":"Q5919994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$DAC0A476-83F1-4F41-873B-5D4BFD3B457E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$A7CC404C-0A56-4DF7-9507-43F81371EC39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"902738aae5d5c0a4e67cfee73c9d74c75da7c22b","datavalue":{"value":{"entity-type":"item","numeric-id":5176024,"id":"Q5176024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$4CC51D7E-BB0F-4E26-97C5-C6FA4066BF4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1a59b9106a5dd5105f2bc476300c4cdae45ec3","datavalue":{"value":{"entity-type":"item","numeric-id":3579218,"id":"Q3579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$42C59BAF-0F2C-4D41-AFAB-83C8C3A38E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3a0d4c2b83e2d1c052c87c581c72cdba8da38e3","datavalue":{"value":{"entity-type":"item","numeric-id":1338451,"id":"Q1338451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$CACF9503-60D9-4F8F-998E-DD9AE156A3A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"120e25d18c0587147339dd8f57e7cc7dca20b850","datavalue":{"value":{"entity-type":"item","numeric-id":3601990,"id":"Q3601990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$6FF59B44-95B3-42F0-9C5F-135C272642B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5762d647bad67eb99de6bbf40a6d31cb9ada3a18","datavalue":{"value":{"entity-type":"item","numeric-id":5365080,"id":"Q5365080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$5E1AB1F1-0F6C-4736-81D3-BD10E515808A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bba75b1fcf7bdfc096d3519487d870ba27bfb198","datavalue":{"value":{"entity-type":"item","numeric-id":3002818,"id":"Q3002818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$373C7226-B5E0-4FF6-9E72-71685032542D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fac33fcaba991f9403b8d09b8ef4fc791c0a07e","datavalue":{"value":{"entity-type":"item","numeric-id":3549708,"id":"Q3549708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$B5A6EE6E-8227-4DDE-8570-B1A3F2CF9516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30227856bf6de691282aab406d71fac57add10d5","datavalue":{"value":{"entity-type":"item","numeric-id":5171222,"id":"Q5171222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$1F1474EB-AE84-4C58-BE65-5BD0012E34F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee15bfc318977ec4ab8712675ed372ec0dd1bae0","datavalue":{"value":{"entity-type":"item","numeric-id":5171221,"id":"Q5171221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$3C0ABA78-39EF-4304-BBDA-8FE816B7D2FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$71CDB2D4-8CED-4C8A-A75E-73A68530297E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"715b35077767f8060e8acc35ee46a3c24449b927","datavalue":{"value":{"entity-type":"item","numeric-id":5387646,"id":"Q5387646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$7A9169FA-A51A-45E7-9EC1-5B5081D0F274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2d3207af5ea54259747675636827e00e4c927bd","datavalue":{"value":{"entity-type":"item","numeric-id":3612424,"id":"Q3612424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$82437616-0117-4D42-A8CA-852854DC41AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c1bb97e5aa8cede73a154b925bb1362eeb78ef7","datavalue":{"value":{"entity-type":"item","numeric-id":5558479,"id":"Q5558479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907218$4BA49F68-323E-48B6-8360-5FB4DBA8DAC8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"4a6029c549b5e7c6c8e3522cc5f4ed7d08ebdc20","datavalue":{"value":"bafkreiacdwy6xn7vnghzb47c32chjasqacpogagmmpsfdmbk4h3e63vsya","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907218$85876739-6797-4A3B-833A-F0C0FE67043A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a345873dac55f4b6ed8f514866bf7e00b770e9e1","datavalue":{"value":{"entity-type":"item","numeric-id":5369520,"id":"Q5369520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e2c7a3a56f006699d4df276fec94215a980aca5","datavalue":{"value":{"amount":"+0.7898144125938416","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":"Q907218$0645F24D-FAF7-447A-A462-13275BFD9E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4eefba487794f20f76350426d1975e07f3cce4a7","datavalue":{"value":{"entity-type":"item","numeric-id":3386630,"id":"Q3386630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce5e2f4dccba0d436d2f5fdd6bd57f3f5987f52f","datavalue":{"value":{"amount":"+0.7881690859794617","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":"Q907218$F886ADB2-03EF-4FE3-8918-6C15A352EFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d605e935525682481d2142667b748b34b5c3beee","datavalue":{"value":{"entity-type":"item","numeric-id":847262,"id":"Q847262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15ca9d813a333bd0cf5802ba1eb604054dee2986","datavalue":{"value":{"amount":"+0.7875563502311707","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":"Q907218$46639503-5A1C-474F-8B48-9CC226F0DD36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b96d4f1b852b8a61374a47b0bc0dffbb64181dc0","datavalue":{"value":{"entity-type":"item","numeric-id":3524254,"id":"Q3524254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d1fd38b251e33bb362b0acc9afe039cd80c34f6","datavalue":{"value":{"amount":"+0.7699146866798401","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":"Q907218$734DF5F4-0D17-418B-9D8E-C58E1A1EAC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79763542424df958fa53921d8261abfd21a87209","datavalue":{"value":{"entity-type":"item","numeric-id":3002818,"id":"Q3002818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dafd6a08fd853f22436e8048ecaf3c41e0ebf6c9","datavalue":{"value":{"amount":"+0.7579492926597595","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":"Q907218$9D9A8FCE-53F9-4985-9038-B54865D7776D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extended formulation for CSP that is compact for instances of bounded treewidth","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extended_formulation_for_CSP_that_is_compact_for_instances_of_bounded_treewidth"}}}}}