Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.24
URN: urn:nbn:de:0030-drops-69236
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6923/
Mnich, Matthias ; Teutrine, Eva-Lotta
Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
| pdf-format: |
|
Abstract
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). Our new upper bound almost matches the best known lower bound of 21^{n/7} approx 1.5448^n, due to Gaspers and Mnich (ESA 2010). Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time O(1.5949^n).
BibTeX - Entry
@InProceedings{mnich_et_al:LIPIcs:2017:6923,
author = {Matthias Mnich and Eva-Lotta Teutrine},
title = {{Improved Bounds for Minimal Feedback Vertex Sets in Tournaments}},
booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
pages = {24:1--24:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-023-1},
ISSN = {1868-8969},
year = {2017},
volume = {63},
editor = {Jiong Guo and Danny Hermelin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6923},
URN = {urn:nbn:de:0030-drops-69236},
doi = {10.4230/LIPIcs.IPEC.2016.24},
annote = {Keywords: exponential-time algorithms, feedback vertex sets, tournaments}
}
| Keywords: | exponential-time algorithms, feedback vertex sets, tournaments | |
| Seminar: | 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) | |
| Issue date: | 2017 | |
| Date of publication: | 09.02.2017 |
