Finding, hitting and packing cycles in subexponential time on unit disk graphs

DOI10.4230/LIPICS.ICALP.2017.65MaRDI QIDQ5111396zbMATH OpenOpenAlexFDO

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

Publication date 27 May 2020

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)

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.

Recommendations

• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• ETH-tight algorithms for long path and cycle on unit disk graphs
• scientific article; zbMATH DE number 7053376
• EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
• QPTAS and subexponential algorithm for maximum clique on disk graphs

Cited in

(10)

• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Optimality program in segment and string graphs
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Finding, hitting and packing cycles in subexponential time on unit disk graphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• ETH-tight algorithms for long path and cycle on unit disk 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)