Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950580 | Information and Computation | 2017 | 17 Pages |
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
Petr A. Golovach,