Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On a Generalization of Nemhauser and Trotter’s Local Optimization Theorem
verfasst von : Mingyu Xiao
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The Nemhauser and Trotter’s theorem applies to the famous Vertex Cover problem and can obtain a 2-approximation solution and a problem kernel of 2k vertices. This theorem is a famous theorem in combinatorial optimization and has been extensively studied. One way to generalize this theorem is to extend the result to the Bounded-Degree Vertex Deletion problem. For a fixed integer \(d\ge 0\), Bounded-Degree Vertex Deletion asks to delete at most k vertices of the input graph to make the maximum degree of the remaining graph at most d. Vertex Cover is a special case that \(d=0\). Fellows, Guo, Moser and Niedermeier proved a generalized theorem that implies an O(k)-vertex kernel for Bounded-Degree Vertex Deletion for \(d=0\) and 1, and for any \(\varepsilon >0\), an \(O(k^{1+\varepsilon })\)-vertex kernel for each \(d\ge 2\). In fact, it is still left as an open problem whether Bounded-Degree Vertex Deletion parameterized by k admits a linear-vertex kernel for each \(d\ge 3\). In this paper, we refine the generalized Nemhauser and Trotter’s theorem. Our result implies a linear-vertex kernel for Bounded-Degree Vertex Deletion parameterized by k for each \(d\ge 0\).