The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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

Fomin, Fedor V. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

pdf-format:
LIPIcs-ICALP-2017-65.pdf (0.6 MB)

Abstract

We give algorithms with running time 2^{O({\sqrt{k}\log{k}})} n^{O(1)} for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains (i) a path on exactly/at least k vertices, (ii) a cycle on exactly k vertices, (iii) a cycle on at least k vertices, (iv) a feedback vertex set of size at most k, and (v) a set of k pairwise vertex disjoint cycles.

For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time 2^{O(k^{0.75}\log{k})} n^{O(1)}. Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to k^{O(1)} and there exists a solution that crosses every separator at most O(\sqrt{k}) times. The running times of our algorithms are optimal up to the log{k} factor in the exponent, assuming the Exponential Time Hypothesis.

BibTeX - Entry

@InProceedings{fomin_et_al:LIPIcs:2017:7393,
  author =	{Fedor V. Fomin and Daniel Lokshtanov and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
  title =	{{Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{65:1--65:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7393},
  URN =		{urn:nbn:de:0030-drops-73937},
  doi =		{10.4230/LIPIcs.ICALP.2017.65},
  annote =	{Keywords: Longest Cycle, Cycle Packing, Feedback Vertex Set, Unit Disk Graph, Parameterized Complexity}
}

Keywords: Longest Cycle, Cycle Packing, Feedback Vertex Set, Unit Disk Graph, Parameterized Complexity
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

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