Search

For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H-Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP-complete cases depending on the choice of H. Moreover, when G is AT-free, chordal or planar, we show that H-Minor Edit is polynomial-time solvable for all graphs H.

We study a novel generalization of the Vertex Cover problem which is motivated by, e.g., error correction (data cleaning) prior to inference of chemical mixtures by their observable reaction products. We focus on the important case of deciding on one of two candidate substances. This problem has nice graph-theoretic formulations situated between Vertex Cover and 3-Hitting Set. In order to characterize its parameterized complexity we devise parameter-preserving reductions, and we show that some minimum solution can be computed faster than by solving 3-Hitting Set in general. More explicitly, we introduce the Union Editing problem: In a hypergraph with red and blue vertices, edit the colors so that the red set becomes exactly the union of some hyperedges. The case of degree 2 is equivalent to Star Editing: in a graph with red and blue edges, edit the colors so that the red set becomes exactly the union of some stars, i.e., vertices with all their incident edges. Our time bound is O∗(1.84c) where c denotes the total number of recolored edges.

We examine the parameterized complexity of the problem of editing a graph to obtain an r-degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is W[P]-complete, and remains W[P]-complete even if the input graph is already (r+1)-degenerate, or has maximum degree 2r+1 for all r≥2.We also demonstrate fixed-parameter tractability for several Clique based problems when the input graph has bounded degeneracy.

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\colon V(G)\rightarrow\{0,1\}$, and asks whether $G$ can be modified into a connected graph $H$ with $d_{H}(v)\equiv\delta(v)~(\bmod~2)$ for each $v\in V(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 $\{vd\} \subseteq S\subseteq \{ea,ed,vd\}$, then CDPE($S$) is NP-complete and W[1]-hard when parameterized by $k$, even if $\delta\equiv 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 the Eulerian Editing problem and its directed variant., Comment: 33 pages. An extended abstract of this paper will appear in the proceedings of FSTTCS 2014

We study a wide class of graph editing problems that ask whether a given graph can be modified to satisfy certain degree constraints, using a limited number of vertex deletions, edge deletions, or edge additions. The problems generalize several well-studied problems such as the General Factor Problem and the Regular Subgraph Problem. We classify the parameterized complexity of the considered problems taking upper bounds on the number of editing steps and the maximum degree of the resulting graph as parameters. © 2011 Elsevier Inc. All rights reserved.