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

## DOI:

https://doi.org/10.7155/jgaa.00584## Keywords:

partial vertex cover , bipartite graph , fixed-parameter tractability , W[1]-hardness## 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 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 as the input we are given an edge-weighted 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 fixed-parameter tractability and algorithms. We present some W[1]-hardness, paraNP-hardness results for our problem. On the positive side, we show that the problem is fixed-parameter tractable with respect to certain parameters. One of our W[1]-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 the parameters. We believe that this problem might be useful in obtaining similar results in other situations.*Keywords:*partial vertex cover; bipartite graph; fixed-parameter tractability; W[1]-hardness

### Downloads

Download data is not yet available.

## Downloads

## Published

2022-01-01

## How to Cite

*Journal of Graph Algorithms and Applications*,

*26*(1), 91–110. https://doi.org/10.7155/jgaa.00584

## License

Copyright (c) 2022 Vahan Mkrtchyan, Garik Petrosyan

This work is licensed under a Creative Commons Attribution 4.0 International License.