Structural parametrization for weighted vertex cover

Question

Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(2^\ell n^c)$ time, where $n$ is the number of vertices and $c$ is a constant.

I tried to approach this by finding a tree and find VWVC there with polynomial time and then brute forcing the rest $\ell$ edges in $O(2^{\ell})$, unfortunately i found a counterexample very quickly. Also I attempted to somehow assign all edges a weight (maybe for $uv\in E$ set $w(uv)=w(u)+w(v)$) and compute the minimal spanning tree and do something with that but I couldn't show that this would yield optimal vertex cover either. I'm kinda lost. Any hints appreciated.

Answer 1

Find the set $L$ containing the $\ell$ extra edges (actually, find any set $L$ of $\ell$ edges such that $G-L$ is a tree).

Let $C$ be an optimal solution. For each edge $(u,v)$ in $L$, guess whether $u \in C$. If you guess "yes", add $u$ to a set $X$, otherwise add $v$ to $X$. (Notice that it is possible for both $u$ and $v$ to be in $C$, but we do not need to explicitly consider this case).

Overall, there are at most $2^\ell$ distinct choices for the $\ell$ guesses. At least one set $X^*$ among the guessed sets $X$ is a subset of $C$.

Given $X^*$ you can find the minimum weighted vertex cover in poylnomial-time by considering $F=G-X^*$. Since all the edges in $L$ have an endpoint in $X^*$, $F$ is a forest. Then you can find a minimum weighted vertex cover $C_i$ for each tree $T_i$ in $F$. The set $\cup_i C_i$ is a minimum weighted vertex cover for $F$, and $X^* \cup (\cup_i C_i)$ is the sought solution.

You could also directly find a minimum weighted vertex cover for $G-L$ with the constraints that the vertices in $X^*$ are forced to be in the cover. This can be done, e.g., with a straightforward modification of the dynamic programming algorithm for trees. Another option is setting the weights of the vertices in $X^*$ to $0$ (or to $\sum_{v \in V}$) making them essentially "free" to select.

Since you don't actually know $X^*$ you can run the above procedure on each guess $X$ and then select the cover of minimum weight.