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

Pilipczuk, Marcin ; Pilipczuk, Michal ; Wrochna, Marcin

Edge Bipartization Faster Than 2^k

pdf-format:
LIPIcs-IPEC-2016-26.pdf (0.5 MB)

Abstract

In the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time O(2^k m^2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time O(1.977^k nm), which is the first algorithm with the running time dependence on the parameter better than 2^k. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlström [SODA'14] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.

BibTeX - Entry

@InProceedings{pilipczuk_et_al:LIPIcs:2017:6928,
  author =	{Marcin Pilipczuk and Michal Pilipczuk and Marcin Wrochna},
  title =	{{Edge Bipartization Faster Than 2^k}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6928},
  URN =		{urn:nbn:de:0030-drops-69285},
  doi =		{10.4230/LIPIcs.IPEC.2016.26},
  annote =	{Keywords: edge bipartization, FPT algorithm}
}

Keywords: edge bipartization, FPT algorithm
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

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