CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers)) ; Leonid Molokov (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
Theoretical Computer Science (0304-3975). Vol. 452 (2012), p. 39-46.
[Artikel, refereegranskad vetenskaplig]

We study a novel generalization of the Vertex Cover problem which is motivated by, e.g., error correction (data cleaning) prior to 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 its 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 exactly 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 exactly the union of some stars, i.e., vertices with all their incident edges. Our time bound is O*(1.84^c) where c denotes the total number of recolored edges.

Nyckelord: vertex cover, hitting set, graph editing, error correction, parameterized complexity, problem kernel



Denna post skapades 2012-08-20. Senast ändrad 2015-02-11.
CPL Pubid: 162210

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)




Projekt

Denna publikation är ett resultat av följande projekt:


Generalized and fast search strategies for parameterized problems (VR//2010-4661)