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.IPEC.2020.26
URN: urn:nbn:de:0030-drops-133297
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13329/
Go to the corresponding LIPIcs Volume Portal

Saurabh, Saket ; Tale, Prafullkumar

On the Parameterized Complexity of Maximum Degree Contraction Problem

pdf-format:
LIPIcs-IPEC-2020-26.pdf (0.7 MB)

Abstract

In the Maximum Degree Contraction problem, input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n^?(k). As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (ETH).
Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of Parameterized Complexity and proved, among other things, that it admits an FPT algorithm running in time (d + k)^(2k) ⋅ n^?(1) = 2^?(k log (k+d)) ⋅ n^?(1), and remains NP-hard for every constant d ≥ 2 (Acta Informatica (2014)). We present a different FPT algorithm that runs in time 2^?(dk) ⋅ n^?(1). In particular, our algorithm runs in time 2^?(k) ⋅ n^?(1), for every fixed d. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d. We answer this question in the negative and prove that it does not admit a polynomial compression unless NP ⊆ coNP/poly.

BibTeX - Entry

@InProceedings{saurabh_et_al:LIPIcs:2020:13329,
  author =	{Saket Saurabh and Prafullkumar Tale},
  title =	{{On the Parameterized Complexity of Maximum Degree Contraction Problem}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13329},
  URN =		{urn:nbn:de:0030-drops-133297},
  doi =		{10.4230/LIPIcs.IPEC.2020.26},
  annote =	{Keywords: Graph Contraction Problems, FPT Algorithm, Lower Bound, ETH, No Polynomial Kernel}
}

Keywords: Graph Contraction Problems, FPT Algorithm, Lower Bound, ETH, No Polynomial Kernel
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

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