Editing to a Graph of Given Degrees
Petr A. Golovach · arXiv (Cornell University) · 2013
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\subseteq coNP/poly.