The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that for a given graph G, non-negative integers d, k and a function δ: V(G) → {1,..., d}, asks whether it is possible to obtain a connected graph G' from G such that the degree of v is δ(v) for any vertex v by at most k edge editing operations. As the problem is NP-complete even if δ(v) = 2, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d + k. For the special case δ(v) = d, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only.
展开▼
