Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
<|reference_start|>Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion: 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.<|reference_end|>
@article{jansen2024search-space,
    title={Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut
  and Cograph Deletion},
    author={Bart M. P. Jansen, Ruben F. A. Verhaegh},
    journal={arXiv preprint arXiv:2404.09769},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.09769},
    primaryClass={cs.DS}
}