2019/04/26 by Vahan Mkrtchyan, Mkrtchyan, Vahan, Garik Petrosyan +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1904.12011
openalex publication_date 2019/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the weighted partial vertex cover problem (WPVC), we are given a graph G=(V,E), cost function c:V→ N, profit function p:E→ N, and positive integers R and L. The goal is to check whether there is a subset V'⊆ V of cost at most R, such that the total profit of edges covered by V' 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≡ 1. On the negative side, it is W[1]-hard for arbitrary c, even when p≡ 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.