Parameterized algorithms for Partial vertex covers in bipartite graphs

Abstract

In the weighted partial vertex cover problem (WPVC), we are given a graph $G=(V,E)$, cost function $c:V\to N$, profit function $p:E\to N$, and positive integers $R$ and $L$. The goal is to check whether there is a subset $V^{\prime }\subseteq V$ of cost at most $R$, such that the total profit of edges covered by $V^{\prime }$ is at least $L$. In this paper we study the fixed-parameter tractability of WPVC in bipartite graphs (WPVCB). By extending the methods of Amini et al., we show that WPVCB is FPT with respect to $R$ if $c\equiv 1$. On the negative side, it is $W[1]$-hard for arbitrary $c$, even when $p\equiv 1$. In particular, WPVCB is $W[1]$-hard parameterized by $R$. We complement this negative result by proving that for bounded-degree graphs WPVC is FPT with respect to $R$. The same result holds for the case of WPVCB when we allow to take only one fractional vertex. Additionally, we show that WPVC is FPT with respect to $L$. Finally, we discuss a variant of PVCB in which the edges covered are constrained to include a matching of prescribed size and derive a paramterized algorithm for the same.

12 pages, no figures