arXiv preprint ·
Vertex Cover Interdiction in Bipartite Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the vertex cover interdiction problem, we are given an undirected graph $G=(V,E)$, two integers $t$ and $k$ and a vertex subset $B\subseteq V$, and we are asked to find a set $X \subseteq B$ with $|X|\leq t$ such that $X$ hits (i.e., intersects) all the vertex covers of $G$ of size at most $k$. Recently, Grüne and Wulf proved that the problem is $Σ_2^p$-complete. However, their reduction relied on the fact that the vertex cover problem is NP-complete. This, in turn, means that we do not know the complexity status of the vertex cover interdiction problem when the input graph is restricted to a bipartite graph since the vertex cover problem can be solved in polynomial time for bipartite graphs. One of our main results shows that the vertex cover interdiction problem is NP-complete for bipartite graphs. In contrast, when $k$ is restricted to the minimum vertex cover size, i.e., we are only required to hit all the minimum vertex covers, we show that the vertex cover interdiction problem can be solved in polynomial time for bipartite graphs. This motivates us to study the parameterized complexity of the vertex cover interdiction problem for bipartite graphs when the difference of $k$ and the minimum vertex cover size is taken as a parameter. With this parameter, we show that the problem is $\mathrm{W}[1]$-hard, but can be solved in polynomial time when the parameter is constant (i.e., in XP time). We also show that the problem is fixed-parameter tractable when parameterized by $k$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Dimensional Ultra-Log-Concave Distributions
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Improved Algorithms for the Remote Point Problem
On Deterministically Computing Total Variation Distance via Zonotope Compression
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.