Editing to Connected F-Degree Graph

Abstract

In the Edge Editing to Connected $f$-Degree Graph problem we are given a graph $G$, an integer $k$, and a function $f$ assigning integers to vertices of $G$. The task is to decide whether there is a connected graph $F$ on the same vertex set as $G$, such that for every vertex $v$, its degree in $F$ is $f(v)$, and the number of edges in $E(G)\triangle E(F)$, the symmetric difference of $E(G)$ and $E(F)$, is at most $k$. We show that Edge Editing to Connected $f$-Degree Graph is fixed-parameter tractable (FPT) by providing an algorithm solving the problem on an $n$-vertex graph in time $2^{\mathcal O(k)}n^{\mathcal O(1)}$. We complement this result by showing that the weighted version of the problem with costs $1$ and $0$ is W[1]-hard when parameterized by $k$ and the maximum value of $f$ even when the input graph is a tree. Our FPT algorithm is based on a nontrivial combination of color-coding and fast computations of representative families over the direct sum matroid of $\ell$-elongation of the co-graphic matroid associated with $G$ and a uniform matroid over the set of nonedges of $G$. We believe that this combination could be useful in designing parameterized algorithms for other edge editing and connectivity problems.