{"entities":{"Q2564046":{"pageid":2574789,"ns":120,"title":"Item:Q2564046","lastrevid":73797924,"modified":"2026-04-14T17:17:34Z","type":"item","id":"Q2564046","labels":{"en":{"language":"en","value":"Sparse parameterized problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 961245"}},"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":"Q2564046$2855ABAE-6DF1-4882-A28B-4B9E565C1C82","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"abe43268995ee88f5ec353a7b6b57df23f834b7d","datavalue":{"value":{"text":"Sparse parameterized problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2564046$6CC89942-439A-44AF-9C5E-C6FEA06F156F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"59f2145ea26306793b91dd136342dd1ca2f5c2a4","datavalue":{"value":"0863.03020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$72643331-1E63-4C04-9028-D41564FEC231","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dfdea4cb5975a6ba58b889b2495410c34ac259ee","datavalue":{"value":"10.1016/0168-0072(95)00069-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$17AD3DBA-6007-4F68-93E6-2431A2DAB535","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7498e7bc15a09b88bafb9e27c36762945347ac6","datavalue":{"value":{"entity-type":"item","numeric-id":290267,"id":"Q290267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$E1259927-3B56-471B-983C-F802BD5E6518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"057c48278a1d014d58f7703e66b1dc164eccfbc4","datavalue":{"value":{"entity-type":"item","numeric-id":175527,"id":"Q175527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$BAC039F6-8D8C-4F8B-A03F-4D2A94572417","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$FF91C788-2C95-49EF-9182-AF718307B38E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"79f3427dbe586b2e10a9738d4e235ad1517b497f","datavalue":{"value":{"time":"+1997-02-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2564046$3BE91357-A563-4B3D-A952-BC7716AE1867","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d58746d326a2f29686c208f097a71e802a20301e","datavalue":{"value":"Mike Fellows and the reviewer developed a complexity theory for parametrized problems: that is, problems of the form:  \\[ \\begin{aligned} \\text{Input} \\quad & \\langle x,k \\rangle\\\\ \\text{Parameter} \\quad & k \\\\ \\text{Question} \\quad & \\text{Is } \\langle x,k \\rangle \\in L? \\end{aligned} \\]  For instance, VERTEX COVER is (classically) NP complete, but as a parametrized problem, it is fixed parameter tractable, meaning that there is an algorithm \\(A\\) and a constant \\(c\\) \\((=1)\\) for VERTEX COVER) such that \\(A\\) decides, for a fixed \\(k\\), if \\(G\\) has a vertex cover of size \\(k\\) in terms \\(O (|G |^c)\\). On the other hand, there are problems where only brute force seems possible. These give rise to parameter classes akin to NP. The paper at hand examines the analogue of Mahaney's Theorem for sparse sets to the parametric setting. The analogue is found to hold, but the combinatorics are significantly more difficult.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2564046$3C1BAFC9-3572-4D1C-AFF4-3E877A30B877","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$0C15521B-A7C1-4B7E-BFD6-5BE574E1B1B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$1599F3C8-A7E8-45CF-A1F7-1D9E6EC77621","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0e43c6d10386c9f344267572d870fb9e1cbdebe0","datavalue":{"value":"961245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$2FD2CC77-1AC4-4697-AE56-B45A9FCBD7B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4dfa9a861b6c56d5795587296c153ce00a31fc0b","datavalue":{"value":"Mahaney's theorem for sparse sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2564046$E21D6AFD-A9BF-4C76-8644-36795EC2940D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d635e1049e31ea996fab3a10ca1db7cb6a36998a","datavalue":{"value":"complexity theory for parametrized problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2564046$F6FCEF37-0BC9-412B-8CCC-D32711A31B12","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8d89c094c10f916fc184498b2e53ee8d25bf632f","datavalue":{"value":"Q57360100","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$5A116870-F74A-489F-BF21-992781D58133","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8055ef4c08baf7aae068108b5a3771ed10ad54de","datavalue":{"value":{"entity-type":"item","numeric-id":247180,"id":"Q247180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$9F277279-AEF9-44EA-B8CA-7065045567E1","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":"Q2564046$AFD1F0EC-7755-403E-AAA8-CB8B44A69E64","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d614311f5635fdc1ad16a9f50f465e3610287b3","datavalue":{"value":"https://doi.org/10.1016/0168-0072(95)00069-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q2564046$3234B382-17E7-4511-BAE9-9798FF2FE3BA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bf56e9335403dab2ce183f0f0e4a5a6ecc05e87f","datavalue":{"value":"W2001859438","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$02985730-A710-400E-916B-F3DF6B3507A9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"87f001f0cbad53dd7b0f7605c3f62967f6287c69","datavalue":{"value":{"entity-type":"item","numeric-id":4281539,"id":"Q4281539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$482EFB06-4B88-4D58-B81D-EB58C2800868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae78a63a69a74848d5aeaa89bef60027b93de2fb","datavalue":{"value":{"entity-type":"item","numeric-id":1892937,"id":"Q1892937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$04E77786-7437-4249-B89F-D24B652D7C3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dbc76eea5fe82f8ed1d1d58b9e1c031533a42a9","datavalue":{"value":{"entity-type":"item","numeric-id":4305363,"id":"Q4305363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$0A9646D3-54A9-4A8F-ACAD-BC135EFF696D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f66b4844bcb79a520b665f58fdec673994d537","datavalue":{"value":{"entity-type":"item","numeric-id":4393480,"id":"Q4393480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$09890715-5495-48AE-A653-308C17408E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d98f7bca7625c9749c75727f2dff082e7e78c44d","datavalue":{"value":{"entity-type":"item","numeric-id":4027320,"id":"Q4027320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$8E15D767-41CF-4236-AB40-01C63390DA75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f72dbacf36642446a4b5f28604fada2a145433b","datavalue":{"value":{"entity-type":"item","numeric-id":4281497,"id":"Q4281497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$D5DC24BB-E691-4519-86F3-E502324DFA22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6e20515d7fb50e98c7d3215121fe76d91ec6609","datavalue":{"value":{"entity-type":"item","numeric-id":4850549,"id":"Q4850549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$C3566BD8-6724-4AEB-90F6-5827EDB80612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fa1290987e9e9910315413923140808cd3d7e8a","datavalue":{"value":{"entity-type":"item","numeric-id":4852629,"id":"Q4852629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$050AB131-BDE6-479A-AB64-13033E8DDD73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$CF9CA42F-706F-4BD5-B97C-9D0F21A82BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba48c6dd75052862185f5069e893f6b665add1de","datavalue":{"value":{"entity-type":"item","numeric-id":3978778,"id":"Q3978778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2564046$0E8B4AA7-C5CF-47BC-A4A6-D570945F5FBC","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"050645de743af0f61b5816c0fdf71555431ddd64","datavalue":{"value":"journals/apal/CesatiF96","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2564046$95B5B152-CFC8-4383-AAD9-13D92ADD1389","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebca7d03a69716129e79ccc39d992d938bc5f85b","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cada7dcecc203bcd482c89433e774578af0996a2","datavalue":{"value":{"amount":"+0.7692158818244934","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":"Q2564046$83834BE1-2E29-42BB-A717-5E39C6D082CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b346b4598bbd4175a3420c5fce008260265d43","datavalue":{"value":{"entity-type":"item","numeric-id":4852629,"id":"Q4852629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9df5555fb350fcf2b7f57ff06c0230598eaede9","datavalue":{"value":{"amount":"+0.7651360034942627","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":"Q2564046$A77A648F-0E6E-4836-84AE-94B2D4B50095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4db79391db6ef3e493dcb66ab095ac52ec64ce2e","datavalue":{"value":{"entity-type":"item","numeric-id":2408196,"id":"Q2408196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09fa4d44854bb5aff09ba31aeccadc190a9aa29f","datavalue":{"value":{"amount":"+0.7624843120574951","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":"Q2564046$E193D639-E2F3-433F-AD8A-889AE050E346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69c4c476563aaf97fa04deb97fa7c13801a7dee5","datavalue":{"value":{"entity-type":"item","numeric-id":5363788,"id":"Q5363788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d42c0b93edd87c02f1475daee9e2981a950afb8","datavalue":{"value":{"amount":"+0.7617591619491577","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":"Q2564046$01B40326-4CED-491B-A091-D8F5325FAA1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32409818ea05dd6b0b9ff52718c6447a048f158c","datavalue":{"value":{"entity-type":"item","numeric-id":4850549,"id":"Q4850549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70c7c2facdbdadbb427970c7e294ffee9ba58cde","datavalue":{"value":{"amount":"+0.7616047859191895","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":"Q2564046$7E81DE45-9C93-43D0-9989-EB17431274B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sparse parameterized problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sparse_parameterized_problems"}}}}}