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

Sullivan, Blair D. ; van der Poel, Andrew

A Fast Parameterized Algorithm for Co-Path Set

pdf-format:
LIPIcs-IPEC-2016-28.pdf (0.6 MB)

Abstract

The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time, randomized fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.

BibTeX - Entry

@InProceedings{sullivan_et_al:LIPIcs:2017:6937,
  author =	{Blair D. Sullivan and Andrew van der Poel},
  title =	{{A Fast Parameterized Algorithm for Co-Path Set}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{28:1--28: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/6937},
  URN =		{urn:nbn:de:0030-drops-69371},
  doi =		{10.4230/LIPIcs.IPEC.2016.28},
  annote =	{Keywords: co-path set, parameterized complexity, Cut&Count, bounded treewidth}
}

Keywords: co-path set, parameterized complexity, Cut&Count, bounded treewidth
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