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

DOI10.7155/JGAA.00584MaRDI QIDQ5084707zbMATH OpenOpenAlexFDO

Authors

Publication date 28 June 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.11215

zbMATH Keywords

bipartite graphfixed-parameter tractabilitypartial vertex coverW[1-hardness]

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Combinatorial optimization (90C27)

Abstract: 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^{\prime }$ of $V$ of size at most $R$, such that $V^{\prime }$ 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^{\prime }$ of vertices of $G$ of size at most $R$, such that the edges of $G$ covered by $V^{\prime }$ 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.

Recommendations

• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• An unfeasible matching problem
• scientific article; zbMATH DE number 2080245
• Constrained weighted matchings and edge coverings in graphs
• The maximum vertex coverage problem on bipartite graphs

Cites work

• A better approximation ratio for the vertex cover problem
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• A unified approach to approximating partial covering problems
• Algorithms and Data Structures
• Approximation algorithms for partial covering problems
• Approximation of Partial Capacitated Vertex Cover
• Computing small partial coverings
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 6515828 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• scientific article; zbMATH DE number 1979504 (Why is no real title available?)
• Implicit branching and parameterized partial cover problems
• Improved approximation of maximum vertex coverage problem on bipartite graphs
• Improved Upper Bounds for Partial Vertex Cover
• Intuitive Algorithms and t-Vertex Cover
• On non-optimally expanding sets in Grassmann graphs
• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Parameterized algorithms
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• Partial vs. Complete Domination: t-Dominating Set
• Reducibility among combinatorial problems
• The approximability of partial vertex covers in trees
• The budgeted maximum coverage problem
• The maximum vertex coverage problem on bipartite graphs
• Using homogeneous weights for approximating the partial cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(4)

• On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Solving partial dominating set and related problems using twin-width

This page was built for publication: On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084707)