Mnich, Matthias ;
Teutrine, Eva-Lotta
Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
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: |
|
2017 |
2017
