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

Eulerian graphsgraph editingpolynomial algorithm

Mathematics Subject Classification ID

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

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

• 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 a connected graph of given degrees
• Editing to Eulerian graphs
• Efficient algorithms for Eulerian extension and rural Postman
• Finding even subgraphs even faster
• Fixed-parameter tractability of graph modification problems for hereditary properties
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• 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 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
• Parameterized Eulerian strong component arc deletion problem on tournaments
• The node-deletion problem for hereditary properties is NP-complete
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• The spanning subgraphs of eulerian graphs
• The splittance of a graph
• Win-win kernelization for degree sequence completion problems

Cited in

(13)

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