# Structural parametrization for weighted vertex cover

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.

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.

• So, for each edge you try to add either $u$, $v$ or both $u,v$. But that's $O(3^\ell)$... or I don't understand the argument why we "do not need to explicitly consider this case". – Michal Dvořák Mar 3 at 10:38
• No. For each edge $(u,v)$ I either add $u$ or $v$ to $X$. I never explicitly add both $u$ and $v$ to $X$ (although this could happen if multiple edges in $L$ share the same endpoints). The goal is to add to $X$ at least one endpoint of each edge in $L$ so that $X$ is a subset of an optimal vertex cover and $G-X$ is acyclic. The set $X$ represents the vertices that we are forcing to be in the vertex cover. There is no restriction for the vertices in $V \setminus X$. If an optimal vertex cover contains both $u$ and $v$ for some $(u,v) \in L$ then it suffices to add one of $u$ and $v$ to $X$. – Steven Mar 3 at 11:49
• Ah ye, we still have the second vertex in the $V\setminus X$ so if it was in the original optimal solution, then the polynomial algorithm on the tree finds it. I got it now. Thanks. – Michal Dvořák Mar 3 at 13:38