2011 | OriginalPaper | Chapter
Parameterized Reductions and Algorithms for Another Vertex Cover Generalization
Authors : Peter Damaschke, Leonid Molokov
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.