On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs

04/22/2021
by   Vahan Mkrtchyan, et al.
0

In the classical partial vertex cover problem, we are given a graph G and two positive integers R and L. The goal is to check whether there is a subset V' of V of size at most R, such that V' covers at least L edges of G. The problem is NP-hard as it includes the Vertex Cover problem. Previous research has addressed the extension of this problem where one has weight-functions defined on sets of vertices and edges of G. In this paper, we consider the following version of the problem where on the input we are given an edge-weighted bipartite graph G, and three positive integers R, S and T. The goal is to check whether G has a subset V' of vertices of G of size at most R, such that the edges of G covered by V' have weight at least S and they include a matching of weight at least T. In the paper, we address this problem from the perspective of fixed-parameter tractability. One of our hardness results is obtained via a reduction from the bi-objective knapsack problem, which we show to be W[1]-hard with respect to one of parameters. We believe that this problem might be useful in obtaining similar results in other situations.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset