2026-09-22T20:11:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20068 2026-09-05T16:29:04Z ddc:004 open_access

Search-Space Reduction via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion Jansen, Bart M. P. Verhaegh, Ruben F. A. fixed-parameter tractability essential vertices integrality gap For an optimization problem Π on graphs whose solutions are vertex sets, a vertex v is called c-essential for Π if all solutions of size at most c ⋅ 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^𝒪(𝓁³)⋅n^𝒪(1), where 𝓁 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-ε)-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bart M. P. Jansen and Ruben F. A. Verhaegh 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.28 urn:nbn:de:0030-drops-200683 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode