0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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". $\endgroup$
    – Michal Dvořák
    Mar 3, 2021 at 10:38
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Mar 3, 2021 at 11:49
  • $\begingroup$ 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. $\endgroup$
    – Michal Dvořák
    Mar 3, 2021 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.