Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
2024
Online
report
For an optimization problem $\Pi$ on graphs whose solutions are vertex sets, a vertex $v$ is called $c$-essential for $\Pi$ if all solutions of size at most $c \cdot OPT$ contain $v$. Recent work showed that polynomial-time algorithms to detect $c$-essential vertices can be used to reduce the search space of fixed-parameter tractable algorithms solving such problems parameterized by the size $k$ of the solution. We provide several new upper- and lower bounds for detecting essential vertices. For example, we give a polynomial-time algorithm for $3$-Essential detection for Vertex Multicut, which translates into an algorithm that finds a minimum multicut of an undirected $n$-vertex graph $G$ in time $2^{O(\ell^3)} \cdot n^{O(1)}$, where $\ell$ is the number of vertices in an optimal solution that are not $3$-essential. Our positive results are obtained by analyzing the integrality gaps of certain linear programs. Our lower bounds show that for sufficiently small values of $c$, the detection task becomes NP-hard assuming the Unique Games Conjecture. For example, we show that ($2-\varepsilon$)-Essential detection for Directed Feedback Vertex Set is NP-hard under this conjecture, thereby proving that the existing algorithm that detects $2$-essential vertices is best-possible.
Comment: Conference version to appear at the 19th Scandinavian Symposium on Algorithm Theory (SWAT 2024)
Titel: |
Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
|
---|---|
Autor/in / Beteiligte Person: | Jansen, Bart M. P. ; Verhaegh, Ruben F. A. |
Link: | |
Veröffentlichung: | 2024 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|