Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
CoRR(2024)
摘要
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^O(ℓ^3)· n^O(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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要