Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00584
On the fixedparameter tractability of the partial vertex cover problem with a matching constraint in edgeweighted bipartite graphs
Vahan Mkrtchyan and
Garik Petrosyan
Vol. 26, no. 1, pp. 91110, 2022. Regular paper.
Abstract In the classical partial vertex cover problem, we are given a graph $G$ and two positive integers $k_1$ and $k_2$. The goal is to check whether there is a subset $V'$ of $V$ of size at most $k_1$, such that $V'$ covers at least $k_2$ edges of $G$. The problem is NPhard as it includes the Vertex Cover problem. Previous research has addressed the extension of this problem where one has weightfunctions defined on sets of vertices and edges of $G$. In this paper, we consider the following version of the problem where as the input we are given an edgeweighted bipartite graph $G$ with weights from $\mathbb{N}$, and three positive integers $k_1$, $k_2$ and $k_3$. The goal is to check whether $G$ has a subset $V'$ of vertices of $G$ of size at most $k_1$, such that the edges of $G$ covered by $V'$ have weight at least $k_2$ and they include a matching of weight at least $k_3$. In the paper, we address this problem from the perspective of fixedparameter tractability and algorithms. We present some W[1]hardness, paraNPhardness results for our problem. On the positive side, we show that the problem is fixedparameter tractable with respect to certain parameters. One of our W[1]hardness results is obtained via a reduction from the biobjective knapsack problem, which we show to be W[1]hard with respect to one of the parameters. We believe that this problem might be useful in obtaining similar results in other situations.
Keywords: partial vertex cover; bipartite graph; fixedparameter tractability; W[1]hardness
This work is licensed under the terms of the CCBY license.

Submitted: April 2021.
Reviewed: October 2021.
Revised: November 2021.
Accepted: March 2022.
Final: March 2022.
Published: April 2022.
Communicated by
Giuseppe Liotta

Journal Supporters
