License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.34
URN: urn:nbn:de:0030-drops-122810
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12281/
Go to the corresponding LIPIcs Volume Portal

Saurabh, Saket ; Souza, Uéverton dos Santos ; Tale, Prafullkumar

On the Parameterized Complexity of Grid Contraction

pdf-format:
LIPIcs-SWAT-2020-34.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{saurabh_et_al:LIPIcs:2020:12281,
  author =	{Saket Saurabh and U{\'e}verton dos Santos Souza and Prafullkumar Tale},
  title =	{{On the Parameterized Complexity of Grid Contraction}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12281},
  URN =		{urn:nbn:de:0030-drops-122810},
  doi =		{10.4230/LIPIcs.SWAT.2020.34},
  annote =	{Keywords: Grid Contraction, FPT, Kernelization, Lower Bound}
}

Keywords: Grid Contraction, FPT, Kernelization, Lower Bound
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI