Vis enkel innførsel

dc.contributor.authorDabrowski, Konrad K.
dc.contributor.authorGolovach, Petr
dc.contributor.authorvan' t Hof, Pim
dc.contributor.authorPaulusma, Daniël
dc.date.accessioned2016-04-26T13:15:24Z
dc.date.available2016-04-26T13:15:24Z
dc.date.issued2014
dc.PublishedLeibniz International Proceedings in Informatics 2014, 29:97-108eng
dc.identifier.urihttps://hdl.handle.net/1956/11951
dc.description.abstractWe 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 NP-complete and W-hard 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 out-degree of every vertex equals a prescribed value. As an important implication of our results, we obtain polynomial-time algorithms for Eulerian Editing problem and its directed variant. To the best of our knowledge, the only other natural non-trivial graph class H for which the H-Editing problem is known to be polynomial-time solvable is the class of split graphs.en_US
dc.language.isoengeng
dc.publisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbHen_US
dc.rightsAttribution CC BYeng
dc.rights.urihttp://creativecommons.orgeng
dc.subjectEulerian graphseng
dc.subjectgraph editingeng
dc.subjectpolynomial algorithmeng
dc.titleEditing to Eulerian Graphsen_US
dc.typeConference object
dc.date.updated2016-03-31T09:45:27Z
dc.description.versionpublishedVersionen_US
dc.rights.holderCopyright Konrad K. Dabrowski, Petr A. Golovach, Pim van ’t Hof, and Daniël Paulusmaen_US
dc.identifier.doihttps://doi.org/10.4230/lipics.fsttcs.2014.97
dc.identifier.cristin1216385
dc.subject.nsiVDP::Matematikk og Naturvitenskap: 400en_US


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel

Attribution CC BY
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution CC BY