2011 | OriginalPaper | Buchkapitel
Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
verfasst von : Peter Damaschke, Leonid Molokov
Erschienen in: Algorithms and Data Structures
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
We study a novel generalization of the
Vertex Cover
problem which is motivated by, e.g., error correction in the inference of chemical mixtures by their observable reaction products. We focus on the important case of deciding on one of two candidate substances. This problem has nice graph-theoretic formulations situated between
Vertex Cover
and
3-Hitting Set
. In order to characterize their parameterized complexity we devise parameter-preserving reductions, and we show that some minimum solution can be computed faster than by solving
3-Hitting Set
in general. More explicitly, we introduce the
Union Editing
problem: In a hypergraph with red and blue vertices, edit the colors so that the red set becomes the union of some hyperedges. The case of degree 2 is equivalent to
Star Editing
: In a graph with red and blue edges, edit the colors so that the red set becomes the union of some stars, i.e., vertices with
all
their incident edges.