Petr Golovach
Bergen, Norway

Editing to a connected graph of given degrees

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 asks for a graph G, non-negative integers d,k and a
function \delta:V(G)->{1,...,d}, whether it is possible to obtain a
connected graph G' from G such that the degree of v is \delta(v) for any
vertex v by at most k edge editing operations. As the problem is NP-complete
even if \delta(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
\delta(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.