Improved bounds for minimal feedback vertex sets in tournaments

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949(n) minimal FVS. This significantly improves the previously best upper bound of 1.6667(n) by Fomin et al. [STOC 2016] and 1.6740...

Descripción completa

Detalles Bibliográficos
Autores principales: Mnich, M., Teutrine, E.
Formato: Online Artículo Texto
Lenguaje:English
Publicado: John Wiley and Sons Inc. 2017
Materias:
Articles
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5969329/
https://www.ncbi.nlm.nih.gov/pubmed/29861538
http://dx.doi.org/10.1002/jgt.22225
Descripción
Sumario:We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949(n) minimal FVS. This significantly improves the previously best upper bound of 1.6667(n) by Fomin et al. [STOC 2016] and 1.6740(n) by Gaspers and Mnich [J. Graph Theory 72(1):72–89, 2013]. Our new upper bound almost matches the best‐known lower bound of [Formula: see text] , due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time [Formula: see text].

Ejemplares similares