Dabrowski, Konrad K. ;
Golovach, Petr A. ;
van 't Hof, Pim ;
Paulusma, Daniel
Editing to Eulerian Graphs
Abstract
We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and vertex deletion respectively. For any S subseteq {ea,ed,vd}, we define Connected Degree Parity Editing (S) (CDPE(S)) to be the problem that takes as input a graph G, an integer k and a function delta: V(G) > {0,1}, and asks whether G can be modified into a connected graph H with d_H(v) = delta(v)(mod 2) for each v in V(H), using at most k operations from S. We prove that (*) if S={ea} or S={ea,ed}, then CDPE(S) can be solved in polynomial time; (*) if {vd} subseteq S subseteq {ea,ed,vd}, then CDPE(S) is NPcomplete and Whard when parameterized by k, even if delta = 0.
Together with known results by Cai and Yang and by Cygan, Marx, Pilipczuk, Pilipczuk and Schlotter, our results completely classify the classical and parameterized complexity of the CDPE(S) problem for all S subseteq {ea,ed,vd}. We obtain the same classification for a natural variant of the cdpe(S) problem on directed graphs, where the target is a weakly connected digraph in which the difference between the in and outdegree of every vertex equals a prescribed value.
As an important implication of our results, we obtain polynomialtime algorithms for Eulerian Editing problem and its directed variant. To the best of our knowledge, the only other natural nontrivial graph class H for which the HEditing problem is known to be polynomialtime solvable is the class of split graphs.
BibTeX  Entry
@InProceedings{dabrowski_et_al:LIPIcs:2014:4835,
author = {Konrad K. Dabrowski and Petr A. Golovach and Pim van 't Hof and Daniel Paulusma},
title = {{Editing to Eulerian Graphs}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {97108},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4835},
URN = {urn:nbn:de:0030drops48356},
doi = {10.4230/LIPIcs.FSTTCS.2014.97},
annote = {Keywords: Eulerian graphs, graph editing, polynomial algorithm}
}
2014
Keywords: 

Eulerian graphs, graph editing, polynomial algorithm 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 