LIPIcs.IPEC.2016.24.pdf
- Filesize: 481 kB
- 10 pages
Document
Improved Bounds for Minimal Feedback Vertex Sets in Tournaments
Authors
-
Part of:
Volume:
11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-02-09
Cite AsGet BibTex
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)
https://doi.org/10.4230/LIPIcs.IPEC.2016.24
https://doi.org/10.4230/LIPIcs.IPEC.2016.24
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).
Keywords
- exponential-time algorithms
- feedback vertex sets
- tournaments
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jeffrey S. Banks. Sophisticated voting outcomes and agenda control. Soc. Choice Welf., 1(4):295-306, 1985.
-
Felix Brandt, Andre Dau, and Hans Georg Seedig. Bounds on the disparity and separation of tournament solutions. Discrete Appl. Math., 187:41-49, 2015.
-
Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993-2007, 2001.
-
Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truss. Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms, 8(1):76-86, 2010.
-
Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proc. STOC 2016, pages 764-775, 2016.
-
Serge Gaspers and Matthias Mnich. Feedback vertex sets in tournaments. J. Graph Theory, 72(1):72-89, 2013.
-
Sushmita Gupta, Venkatesh Raman, and Saket Saurabh. Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discrete Math., 26(4):1758-1780, 2012.
-
Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85-103. Plenum, New York, 1972.
-
Mithilesh Kumar and Daniel Lokshtanov. Faster exact and parameterized algorithm for feedback vertex set in tournaments. In Proc. STACS 2016, volume 47 of Leibniz Int. Proc. Informatics, pages 49:1-49:13, 2016.
-
Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A 7/3-approximation for feedback vertex sets in tournaments. In Proc. ESA 2016, volume 57 of Leibniz Int. Proc. Informatics, pages 67:1-67:14, 2016.
-
J. W. Moon. On maximal transitive subtournaments. Proc. Edinburgh Math. Soc. (2), 17:345-349, 1970/71.
-
Benno Schwikowski and Ewald Speckenmeyer. On enumerating all minimal solutions of feedback problems. Discrete Appl. Math., 117(1-3):253-265, 2002.
-
Ewald Speckenmeyer. On feedback problems in digraphs. In Proc. WG 1989, volume 411 of Lecture Notes Comput. Sci., pages 218-231. Springer, 1990.
-
Gerhard J. Woeginger. Banks winners in tournaments are difficult to recognize. Soc. Choice Welf., 20(3):523-528, 2003.
-
Gerhard J. Woeginger. Open problems around exact algorithms. Discrete Appl. Math., 156(3):397-405, 2008.