Search

Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits k and the maximum degree r are taken together as a combined parameter, the problems are tractable (i.e. in FPT ), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural k + r parameterization. [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σ by at most k vertex deletions, edge deletions and edge additions. We show that the problem is W [ 1 ] -hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2 O ( k ( Δ ⁎ + k ) 2 ) n 2 log ⁡ n for n -vertex graphs, where Δ ⁎ = max ⁡ σ , i.e., the problem is FPT when parameterized by k + Δ ⁎ . We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k + Δ ⁎ if only edge additions are allowed, and there is no polynomial kernel unless NP ⊆ co - NP / poly for all other combinations of the allowed editing operations. [ABSTRACT FROM AUTHOR]

We consider the Editing to a Graph of Given Degrees problem that asks for a graph G , non-negative integers d , k and a function δ : V ( G ) → { 1 , … , d } , whether it is possible to obtain a graph G ′ from G such that the degree of v is δ ( v ) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for Editing to a Graph of Given Degrees parameterized by d + k . We complement this result by showing that the problem has no polynomial kernel unless NP ⊆ coNP / poly . [ABSTRACT FROM AUTHOR]

Abstract: 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 where denotes the total number of recolored edges. [Copyright &y& Elsevier]

Abstract: We examine the parameterized complexity of the problem of editing a graph to obtain an -degenerate graph. We show that for the editing operations vertex deletion and edge deletion, both separately and combined, the problem is -complete, and remains -complete even if the input graph is already -degenerate, or has maximum degree for all . We also demonstrate fixed-parameter tractability for several Clique based problems when the input graph has bounded degeneracy. [Copyright &y& Elsevier]