Editing to Eulerian graphs

DOI10.1016/J.JCSS.2015.10.003MaRDI QIDQ896016zbMATH OpenOpenAlexFDO

Authors Konrad Dabrowski, Petr A. Golovach, Pim Van 't Hof, Daniël Paulusma

Publication date 11 December 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.6863

zbMATH Keywords

polynomial algorithmgraph editingEulerian graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

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 $Ssubseteqea,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 $deltacolonV(G)ightarrow0,1$, and asks whether $G$ can be modified into a connected graph $H$ with $$ for each $vinV(H)$, using at most $k$ operations from $S$. We prove that 1. if $S=ea$ or $S=ea,ed$, then CDPE($S$) can be solved in polynomial time; 2. if $vdsubseteqSsubseteqea,ed,vd$, then CDPE($S$) is NP-complete and W[1]-hard when parameterized by $k$, even if $deltaequiv0$. 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 $Ssubseteqea,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 the Eulerian Editing problem and its directed variant.

Recommendations

• Editing to Eulerian graphs
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of Eulerian deletion problems
• Finding even subgraphs even faster
• Finding even subgraphs even faster

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• An Eulerian exposition
• Complexity classification of some edge modification problems
• Computing the Deficiency of Housing Markets with Duplicate Houses
• Editing graphs to satisfy degree constraints: a parameterized approach
• Editing to Eulerian graphs
• Editing to a connected graph of given degrees
• Efficient algorithms for Eulerian extension and rural Postman
• Finding even subgraphs even faster
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Matching, Euler tours and the Chinese postman
• NP-completeness results for edge modification problems
• On Eulerian extensions and their application to no-wait flowshop scheduling
• Parameterized Eulerian strong component arc deletion problem on tournaments
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of finding regular induced subgraphs
• Parameterized complexity of three edge contraction problems with degree constraints
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• The node-deletion problem for hereditary properties is NP-complete
• The spanning subgraphs of eulerian graphs
• The splittance of a graph
• Win-win kernelization for degree sequence completion problems

Cited in

(13)

• Augmenting plane straight-line graphs to meet parity constraints
• Parameterized complexity of Eulerian deletion problems
• A survey of parameterized algorithms and the complexity of edge modification
• Parameterized complexity of Eulerian deletion problems
• Switches in Eulerian graphs
• Plane augmentation of plane graphs to meet parity constraints
• Deviation estimates for Eulerian edit numbers of random graphs
• Graph editing to a fixed target
• Finding even subgraphs even faster
• From few components to an Eulerian graph by adding ARCS
• Editing to Eulerian graphs
• Editing to Connected F-Degree Graph
• Editing to a planar graph of given degrees

This page was built for publication: Editing to Eulerian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896016)