License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.217
URN: urn:nbn:de:0030-drops-33579
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3357/
Go to the corresponding LIPIcs Volume Portal

Heggernes, Pinar ; van 't Hof, Pim ; Lokshtanov, Daniel ; Paul, Christophe

Obtaining a Bipartite Graph by Contracting Few Edges

pdf-format:
39.pdf (0.5 MB)

Abstract

We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph G on n vertices and an integer k, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most k edge contractions. Our main result is an f(k) n^{O(1)} time algorithm for Bipartite Contraction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertex, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.

BibTeX - Entry

@InProceedings{heggernes_et_al:LIPIcs:2011:3357,
  author =	{Pinar Heggernes and Pim van 't Hof and Daniel Lokshtanov and Christophe Paul},
  title =	{{Obtaining a Bipartite Graph by Contracting Few Edges}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{217--228},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3357},
  URN =		{urn:nbn:de:0030-drops-33579},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.217},
  annote =	{Keywords: fixed parameter tractability, graph modification problems, edge contractions, bipartite graphs}
}

Keywords: fixed parameter tractability, graph modification problems, edge contractions, bipartite graphs
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

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