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
_version_ 1783325949144596480
author Mnich, M.
Teutrine, E.
author_facet Mnich, M.
Teutrine, E.
author_sort Mnich, M.
collection PubMed
description 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].
format Online
Article
Text
id pubmed-5969329
institution National Center for Biotechnology Information
language English
publishDate 2017
publisher John Wiley and Sons Inc.
record_format MEDLINE/PubMed
spelling pubmed-59693292018-05-30 Improved bounds for minimal feedback vertex sets in tournaments Mnich, M. Teutrine, E. J Graph Theory Articles 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]. John Wiley and Sons Inc. 2017-12-08 2018-07 /pmc/articles/PMC5969329/ /pubmed/29861538 http://dx.doi.org/10.1002/jgt.22225 Text en © 2017 The Authors. Journal of Graph Theory published by Wiley Periodicals, Inc. This is an open access article under the terms of the http://creativecommons.org/licenses/by/4.0/ License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.
spellingShingle Articles
Mnich, M.
Teutrine, E.
Improved bounds for minimal feedback vertex sets in tournaments
title Improved bounds for minimal feedback vertex sets in tournaments
title_full Improved bounds for minimal feedback vertex sets in tournaments
title_fullStr Improved bounds for minimal feedback vertex sets in tournaments
title_full_unstemmed Improved bounds for minimal feedback vertex sets in tournaments
title_short Improved bounds for minimal feedback vertex sets in tournaments
title_sort improved bounds for minimal feedback vertex sets in tournaments
topic Articles
url 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
work_keys_str_mv AT mnichm improvedboundsforminimalfeedbackvertexsetsintournaments
AT teutrinee improvedboundsforminimalfeedbackvertexsetsintournaments

Ejemplares similares