{"entities":{"Q2672940":{"pageid":2683683,"ns":120,"title":"Item:Q2672940","lastrevid":79193261,"modified":"2026-05-06T13:21:25Z","type":"item","id":"Q2672940","labels":{"en":{"language":"en","value":"On the parameterized complexity of grid contraction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7540616"}},"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":"Q2672940$BD646D4E-D60A-432D-B184-779203EBEC3F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b2b8362d8cdff6ad5fe6f52591abbf6c4f8367ef","datavalue":{"value":{"text":"On the parameterized complexity of grid contraction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2672940$557DB8B7-DC18-4498-B6C5-FF6EAB230632","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4c94b3ffb9126e44d6290bf90c68c0230922966","datavalue":{"value":"1501.68001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$2541A7A7-8904-4FBE-9ABE-2AC9CABE70E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31c0d4a00f475577a11aceb1985d009cf97e6c2b","datavalue":{"value":{"entity-type":"item","numeric-id":261392,"id":"Q261392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$D5C50896-6D49-4734-B1C1-8059BE53A390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"352fd252272d717862e518caabed2c092cbd920b","datavalue":{"value":{"entity-type":"item","numeric-id":324702,"id":"Q324702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$3CCC191E-E0B5-42DF-A86C-BC62297C1947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf7a41cf4ace7f3b8c8fa49676272d59668ca9ce","datavalue":{"value":{"entity-type":"item","numeric-id":722545,"id":"Q722545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$8D0EE7AD-6196-425B-885F-886B73D0C5FB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$C1E06ADA-0130-420A-B951-7A74A23F07BE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"77075991782c40305711c3d33a7ecd0dd8eab84c","datavalue":{"value":{"time":"+2022-06-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":"Q2672940$51E40EF2-FCD7-4B3B-9A90-0D10E450BCA3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"273b398e642c4bb465a480ed33556fb5dcd1bfc3","datavalue":{"value":"https://arxiv.org/abs/2008.07967","type":"string"},"datatype":"url"},"type":"statement","id":"Q2672940$1A482813-AF18-42BC-B79A-D88119DCFA9F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"20fa561ebb5aa06bb6adca186cacc03edd5ff314","datavalue":{"value":"This paper initiates the parameterized study of the grid contraction problem. The input to the \\(\\mathcal{G}\\)-contraction problem for a family of graphs \\(\\mathcal{G}\\) is a graph \\(G\\) and an integer \\(k\\), and the goal is to decide if there exists a subset of at most \\(k\\) edges whose contraction in \\(G\\) makes the contracted graph a member of \\(\\mathcal{G}\\). The authors propose a parameterized algorithm with running time \\(2^{\\mathcal{O}(k)}|V(G)|^{\\mathcal{O}(1)}\\) for this problem with respect to the grid family of graphs. Moreover, they provide a kernelization algorithm for this problem. Finally, they show, under the ETH assumption, that their algorithm is optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2672940$1DDC17F9-A202-47D7-BD63-8EABD6CA9F58","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6c1d39d6f200578316757400ebc308169220aec9","datavalue":{"value":{"entity-type":"item","numeric-id":2093878,"id":"Q2093878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$ABE109DF-48FE-499C-B5C3-7D91BC9B21F0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$316B5AC1-B744-452C-B459-DDB0BEB9922E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$CAA30A88-5AD2-4522-8583-4B6CD7C6BD5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$CB4C5812-4B79-4B23-88F0-FDE7AF8C9B4B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"55122d48a2257ddfdf282e50b9314195aba6b4b5","datavalue":{"value":"7540616","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$B87DB5DE-58E0-4718-A0F4-09B03C5EE8DE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"040e5cadc2542137fa22dc2efc65268bb08b809c","datavalue":{"value":"kernelization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2672940$3C6F8ACF-58BF-4576-875F-DB54929AB3A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd18fb4fc3234bce5e8c85db754639f992d65d75","datavalue":{"value":"contraction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2672940$F1571FA3-AF9B-4A3D-A340-50DBE7104325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39c9e86a8c0ac704e1de13a66a9fdebb1fb49be9","datavalue":{"value":"parameterized algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2672940$F949B1E5-2A5D-47DB-A506-F871A1842E28","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":"Q2672940$DA800380-1A02-4358-9F5D-CB2F0A838F35","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f8d50e78c580ede8ef1ec9233baa04aa7dc2bee9","datavalue":{"value":"W3063414738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$D1B4325E-72F8-4555-8CD0-A170CCEAFF5D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f6e21f081b18e8c1b37c600fa32ad6a2a06b4c0","datavalue":{"value":{"entity-type":"item","numeric-id":1146698,"id":"Q1146698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$E035BAC0-BBF2-439C-933E-AA7E484D7905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800c12c223c9230176c5818497cd3dcaea9831c9","datavalue":{"value":{"entity-type":"item","numeric-id":1838829,"id":"Q1838829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$3EF437E5-879A-470B-B7A6-4D4058F4854C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e0245c7f45c98a3194aa05bbbd892ac22e5116","datavalue":{"value":{"entity-type":"item","numeric-id":794164,"id":"Q794164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$50568B33-47AC-4859-AD80-CC8FE29C6EFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b3146341f0fd2377f313f4028df6fdb8adcedd9","datavalue":{"value":{"entity-type":"item","numeric-id":3739139,"id":"Q3739139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$F33A74D5-CAD9-4831-BBB5-06317300C49D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c92ae26afaf2fc29594ce0f474a585f4ae33f73c","datavalue":{"value":{"entity-type":"item","numeric-id":2000005,"id":"Q2000005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$F5564D2A-D2EF-4FEB-9680-7CEEE3DF46AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d34b9f20d5237c086a9c8ebdd8a9e5e8355569d","datavalue":{"value":{"entity-type":"item","numeric-id":1790990,"id":"Q1790990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$C4AB33B8-49AC-478B-A345-51C6A93ECEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"344ed1b726a032a11b3cf792f49238cddf794423","datavalue":{"value":{"entity-type":"item","numeric-id":2867076,"id":"Q2867076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$DD16641B-108A-4DF8-BCF3-74777E86AFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcebb3648867bee0223bbc439c47070b6d28d82c","datavalue":{"value":{"entity-type":"item","numeric-id":1945931,"id":"Q1945931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$2BC23E36-B5F4-4470-9BC1-23E2FAA6A905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f13ef4c2c6973b12ec6c31d897cba9f4a089962","datavalue":{"value":{"entity-type":"item","numeric-id":5408613,"id":"Q5408613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$163A786E-D2F1-483A-881C-467E7DFB5DFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c379702ea23ed6636e4d161b9c4df13544d93b81","datavalue":{"value":{"entity-type":"item","numeric-id":385061,"id":"Q385061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$EF95E915-D68D-4A3B-86D4-DA7C30A9115B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b3dafc39bf65de25ff96234ab8f78cab4a326bb","datavalue":{"value":{"entity-type":"item","numeric-id":471188,"id":"Q471188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$705E0A1A-E7FF-4372-9301-5B2685DACC83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c722379e005b36e214882515877defb3048373b6","datavalue":{"value":{"entity-type":"item","numeric-id":6089673,"id":"Q6089673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$9EC9FC2D-4C5D-473D-9255-EFB4E63646A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84e24d8ccd51739a9938f91a2e5e49bcaea3f1e2","datavalue":{"value":{"entity-type":"item","numeric-id":5205814,"id":"Q5205814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$7A459584-4395-4554-9630-82B80B56F62D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"387c76408ea1ea129c5447e4fd35ce406ff5c527","datavalue":{"value":{"entity-type":"item","numeric-id":2867087,"id":"Q2867087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$DDC6ADFA-03C2-4D6B-896F-0834C4E2D8F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08df24d182baaffcc57c1a2db145dc169d159d3a","datavalue":{"value":{"entity-type":"item","numeric-id":5283353,"id":"Q5283353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$D6898023-3CB8-4169-A0F5-5160DC368302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df834a2ccc96a5199bba70d5b068293e81b627ea","datavalue":{"value":{"entity-type":"item","numeric-id":4636570,"id":"Q4636570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$1FC52781-223D-46C5-94B6-E809C9D6637C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a669be7c2f5911aff056eed9c6f0de47aa155136","datavalue":{"value":{"entity-type":"item","numeric-id":5091159,"id":"Q5091159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$42E3BE68-7027-4159-9DC3-CF2F5EE09051","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cc9cdd9999a46859ae4f667ab34baac016718b","datavalue":{"value":{"entity-type":"item","numeric-id":5502162,"id":"Q5502162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$28720FCC-19EB-4B6A-8A2C-8982EEC24362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97899b2a503251389d97100a20e4ddcb6332a1d1","datavalue":{"value":{"entity-type":"item","numeric-id":4646517,"id":"Q4646517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$E7FD8318-65D7-4A3C-89B1-BAEC10B17A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47af0a53c73cdb404b79a5b5867bdbf005fbbb7","datavalue":{"value":{"entity-type":"item","numeric-id":6059202,"id":"Q6059202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$D5EC78E7-1FFD-4063-A7F9-8FAB7CD5DC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2672940$E13181E4-EC9C-4C4E-8F40-CBDF4808EEEF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35df66a4924e8842f1585b0dbc1d470fe07e848d","datavalue":{"value":"10.1016/J.JCSS.2022.04.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2672940$B0302AB5-7ABF-4800-A724-815A9502EE06","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f71f1e20b72adc73484aeb07434c254a69adf29a","datavalue":{"value":{"entity-type":"item","numeric-id":2000005,"id":"Q2000005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f714a4bf00135e70986c00682973f5dfe34cbeb","datavalue":{"value":{"amount":"+0.8164302706718445","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":"Q2672940$E026EC03-FAEE-4495-B3B0-B6921E0633F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ee96b5b86ba81d9142b48383bdfb45ba601b855","datavalue":{"value":{"entity-type":"item","numeric-id":5111860,"id":"Q5111860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f75097d28ccc60dcc75d3a5cbab5bf1e3b9b350","datavalue":{"value":{"amount":"+0.8118715882301331","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":"Q2672940$77F26299-97A7-4FBD-B215-9E85D171526B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f88a0516d5d6ada66e5398a3cb379a21fd1f8a01","datavalue":{"value":{"entity-type":"item","numeric-id":2912744,"id":"Q2912744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d949bc5cd342c51a79379c5a01ef0a71f3027568","datavalue":{"value":{"amount":"+0.8083670735359192","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":"Q2672940$D549C1FC-D97A-4E91-84D3-933D25015E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c39d9027a996155d82926ee401fcad389c22b75","datavalue":{"value":{"entity-type":"item","numeric-id":1790990,"id":"Q1790990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6acb795a2571b4f52bdc70ace1960bb5f5e7cbe7","datavalue":{"value":{"amount":"+0.8039510250091553","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":"Q2672940$732AD210-C975-4A8D-887D-F59C1DBBE8A5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the parameterized complexity of grid contraction","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_parameterized_complexity_of_grid_contraction"}}}}}