Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909999769321472 |
|---|---|
| author | Spirkl, Sophie Xing, Yun |
| author_facet | Spirkl, Sophie Xing, Yun |
| contents | In this paper, we consider the complexity of the minimum feedback vertex set problem (MFBVS) for tournaments with forbidden subtournaments. The MFBVS problem in general tournaments is known to be NP-complete. We prove that the MFBVS problem for $W_5$-free and $U_5$-free tournaments is in P, and for $T_5$-free tournaments it remains NP-complete. Moreover, we prove a necessary condition for all $H$ such that the MFBVS problem for $H$-free tournaments is in P. We also show that the necessary condition is not sufficient. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17169 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments Spirkl, Sophie Xing, Yun Combinatorics Discrete Mathematics In this paper, we consider the complexity of the minimum feedback vertex set problem (MFBVS) for tournaments with forbidden subtournaments. The MFBVS problem in general tournaments is known to be NP-complete. We prove that the MFBVS problem for $W_5$-free and $U_5$-free tournaments is in P, and for $T_5$-free tournaments it remains NP-complete. Moreover, we prove a necessary condition for all $H$ such that the MFBVS problem for $H$-free tournaments is in P. We also show that the necessary condition is not sufficient. |
| title | Complexity of the Feedback Vertex Set Problem in Tournaments with Forbidden Subtournaments |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2601.17169 |