2026-07-22T12:34:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12281 2024-03-06T10:49:31Z ddc:004 open_access

On the Parameterized Complexity of Grid Contraction Saurabh, Saket Souza, Uéverton dos Santos Tale, Prafullkumar Grid Contraction FPT Kernelization Lower Bound For a family of graphs 𝒢, the 𝒢-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F ⊆ E(G) of size at most k such that G/F belongs to 𝒢. Here, G/F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time c^k ⋅ |V(G)|^{{O}(1)}, for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time c^{o(k)} ⋅ |V(G)|^{{O}(1)}. We also present a polynomial kernel for this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Saket Saurabh and Uéverton dos Santos Souza and Prafullkumar Tale 2020 Is Part Of LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2020.34 urn:nbn:de:0030-drops-122810 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.34 eng https://creativecommons.org/licenses/by/3.0/legalcode