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.STACS.2017.5
URN: urn:nbn:de:0030-drops-70297
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7029/
Go to the corresponding LIPIcs Volume Portal

Agrawal, Akanksha ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

Split Contraction: The Untold Story

pdf-format:
LIPIcs-STACS-2017-5.pdf (0.6 MB)

Abstract

The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this paper, we examine an important family of graphs, namely the family of split graphs, which in the context of edge contractions, is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, the Split Contraction problem asks whether there exists a subset X of edges of G such that G/X is a split graph and X has at most k elements. Here, G/X is the graph obtained from G by contracting edges in X. It was previously claimed that the Split Contraction problem is fixed-parameter tractable. However, we show that, despite its deceptive simplicity, it is W[1]-hard. Our main result establishes the following conditional lower bound: under the Exponential Time Hypothesis, the Split Contraction problem cannot be solved in time 2^(o(l^2)) * poly(n) where l is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2^(o(l^2)) * poly(n) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.

BibTeX - Entry

@InProceedings{agrawal_et_al:LIPIcs:2017:7029,
  author =	{Akanksha Agrawal and Daniel Lokshtanov and Saket Saurabh and Meirav Zehavi},
  title =	{{Split Contraction: The Untold Story}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7029},
  URN =		{urn:nbn:de:0030-drops-70297},
  doi =		{10.4230/LIPIcs.STACS.2017.5},
  annote =	{Keywords: Split Graph, Parameterized Complexity, Edge Contraction}
}

Keywords: Split Graph, Parameterized Complexity, Edge Contraction
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

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