Article ID Journal Published Year Pages File Type
4950580 Information and Computation 2017 17 Pages PDF
Abstract
We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks, given a graph G, non-negative integers d,k and a function δ:V(G)→{1,…,d}, whether it is possible to obtain a connected graph G′ from G such that the degree of v is δ(v) for every 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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,