Editing to Eulerian graphs

DOI10.1016/J.JCSS.2015.10.003zbMATH Open1346.05150arXiv1410.6863OpenAlexW200506746MaRDI QIDQ896016FDOQ896016

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

Publication date: 11 December 2015

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

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.

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

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

zbMATH Keywords

polynomial algorithmgraph editingEulerian graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Matching, Euler tours and the Chinese postman
• Parameterized complexity of finding regular induced subgraphs
• The node-deletion problem for hereditary properties is NP-complete
• The spanning subgraphs of eulerian graphs
• The splittance of a graph
• Editing to a graph of given degrees
• Editing to a Connected Graph of Given Degrees
• Editing graphs to satisfy degree constraints: a parameterized approach
• Title not available (Why is that?)
• Complexity classification of some edge modification problems
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• On Eulerian extensions and their application to no-wait flowshop scheduling
• NP-completeness results for edge modification problems
• Title not available (Why is that?)
• Efficient Algorithms for Eulerian Extension and Rural Postman
• Parameterized complexity of even/odd subgraph problems
• Computing the Deficiency of Housing Markets with Duplicate Houses
• Parameterized Eulerian strong component arc deletion problem on tournaments
• Parameterized complexity of three edge contraction problems with degree constraints
• Parameterized complexity of Eulerian deletion problems
• Win-Win Kernelization for Degree Sequence Completion Problems
• An Eulerian exposition
• Finding Even Subgraphs Even Faster

Cited In (6)

• A survey of parameterized algorithms and the complexity of edge modification
• Switches in Eulerian graphs
• Plane augmentation of plane graphs to meet parity constraints
• Graph editing to a fixed target
• 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)