Metraipolis › archive › dc_ed25ad5fa74d

Vertex Cover Interdiction in Bipartite Graphs — arXiv:2609.24624

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.24624
License (as archived)
CC0-1.0
Archived
2026-10-09T22:40:53.672Z
SHA-256 of the archived text
821f79cd44f6a935a938695d810b42515b1eb75d1deef4cba8afc4c60cbde0c9
Stable URL of this page
https://metraipolis.com/documento/dc_ed25ad5fa74d

How to cite

Vertex Cover Interdiction in Bipartite Graphs — arXiv:2609.24624 — arXiv (en), https://arxiv.org/abs/2609.24624 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ed25ad5fa74d (Metraipolis archive dc_ed25ad5fa74d, sha256 821f79cd44f6a935a938695d810b42515b1eb75d1deef4cba8afc4c60cbde0c9)
BibTeX
@misc{dced25ad5fa74d,
  title = {Vertex Cover Interdiction in Bipartite Graphs — arXiv:2609.24624},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24624},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ed25ad5fa74d; sha256 821f79cd44f6a935a938695d810b42515b1eb75d1deef4cba8afc4c60cbde0c9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24624. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Sigma_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$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.24624 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T22:24:05.641Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).