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

DOI10.4230/LIPICS.ICALP.2017.65zbMATH Open1441.68179arXiv1704.07279OpenAlexW2918931394MaRDI QIDQ5111396FDOQ5111396

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

Publication date: 27 May 2020

Abstract: We give algorithms with running time $2^{O(sqrtklogk)}cdot{n}^{O(1)}$ for the following problems. Given an $n$-vertex unit disk graph $G$ and an integer $k$, decide whether $G$ contains (1) a path on exactly/at least $k$ vertices, (2) a cycle on exactly $k$ vertices, (3) a cycle on at least $k$ vertices, (4) a feedback vertex set of size at most $k$, and (5) 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}logk)}cdot{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(sqrtk)$ times. The running times of our algorithms are optimal up to the $logk$ factor in the exponent, assuming the Exponential Time Hypothesis.

Full work available at URL: https://arxiv.org/abs/1704.07279

zbMATH Keywords

longest cycleparameterized complexityfeedback vertex setcycle packingunit disk graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (4)

• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Optimality program in segment and string graphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

This page was built for publication: Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111396)