K. K. Dabrowski
Editing to Eulerian Graphs
Dabrowski, K. K.; Golovach, P. A; Hof, van't P.; Paulusma, D.
Authors
Contributors
Venkatesh Raman
Editor
S. P. Suresh
Editor
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 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.
Citation
Dabrowski, K. K., Golovach, P. A., Hof, V. P., & Paulusma, D. (2014). Editing to Eulerian Graphs. In V. Raman, & S. P. Suresh (Eds.), 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) (97-108). https://doi.org/10.4230/lipics.fsttcs.2014.97
Conference Name | 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
---|---|
Conference Location | Budapest, Hungary |
Publication Date | Jan 1, 2014 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Jan 8, 2015 |
Pages | 97-108 |
Series Title | Leibniz International Proceedings in Informatics (LIPIcs) |
Series Number | 29 |
Series ISSN | 1868-8969 |
Book Title | 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). |
DOI | https://doi.org/10.4230/lipics.fsttcs.2014.97 |
Keywords | Eulerian graphs, graph editing, polynomial algorithm |
Public URL | https://durham-repository.worktribe.com/output/1153534 |
Files
Published Conference Proceeding
(534 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nd/4.0/
Copyright Statement
Available under License Creative Commons Attribution No Derivatives.
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search