DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2016.24

Improved Bounds for Minimal Feedback Vertex Sets in Tournaments

Authors: Matthias Mnich and Eva-Lotta Teutrine

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

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).

Cite as

Matthias Mnich and Eva-Lotta Teutrine. Improved Bounds for Minimal Feedback Vertex Sets in Tournaments. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 24:1-24:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mnich_et_al:LIPIcs.IPEC.2016.24,
  author =	{Mnich, Matthias and Teutrine, Eva-Lotta},
  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 =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.24},
  URN =		{urn:nbn:de:0030-drops-69236},
  doi =		{10.4230/LIPIcs.IPEC.2016.24},
  annote =	{Keywords: exponential-time algorithms, feedback vertex sets, tournaments}
}

Search Results

Documents authored by Teutrine, Eva-Lotta

Improved Bounds for Minimal Feedback Vertex Sets in Tournaments

Abstract

Cite as

Thanks for your feedback!

Could not send message