Vertex cover interdiction problem is np-complete for bipartite graphs
Vertex Cover Interdiction in Bipartite Graphs
Data Structures and Algorithms
Summary
The vertex cover interdiction problem asks how to stop small vertex covers in a graph by removing a few special vertices. The authors show that this problem is computationally hard (NP-complete) even for bipartite graphs, where the usual vertex cover problem is easier. However, if only the smallest possible vertex covers need to be blocked, the problem can be solved efficiently for bipartite graphs. They also study how the difficulty changes when allowing vertex covers slightly larger than the minimum.
What this means in practice
- •For network security engineers: Understand limits of efficiently blocking critical nodes in bipartite network structures under vertex cover constraints.
- •For graph algorithm developers: Design algorithms for vertex cover interdiction in bipartite graphs with parameters focused on minimum cover sizes.
A theory result. No direct application yet.
Authors
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
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$.