Document Open Access Logo

A 7/3-Approximation for Feedback Vertex Sets in Tournaments

Authors Matthias Mnich, Virginia Vassilevska Williams, László A. Végh

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.67.pdf
  • Filesize: 0.58 MB
  • 14 pages

Document Identifiers

Author Details

Matthias Mnich
Virginia Vassilevska Williams
László A. Végh

Cite As Get BibTex

Matthias Mnich, Virginia Vassilevska Williams, and László A. Végh. A 7/3-Approximation for Feedback Vertex Sets in Tournaments. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.67

Abstract

We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that intersects all cycles. This problem is NP-hard to solve exactly, and Unique Games-hard to approximate by a factor better than 2. We present the first 7/3 approximation algorithm for this problem, improving on the previously best known ratio 5/2 given by Cai et al. [FOCS 1998, SICOMP 2001].

Subject Classification

Keywords
  • Approximation algorithms
  • feedback vertex sets
  • tournaments

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jeffrey S. Banks. Sophisticated voting outcomes and agenda control. Soc. Choice Welf., 1(4):295-306, 1985. Google Scholar
  2. Reuven Bar-Yehuda and Dror Rawitz. On the equivalence between the primal-dual schema and the local ratio technique. SIAM J. Discrete Math., 19(3):762-797, 2005. Google Scholar
  3. Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé. Tournaments and colouring. J. Combin. Theory Ser. B, 103(1):1-20, 2013. Google Scholar
  4. Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput., 30(6):1993-2007 (electronic), 2001. Google Scholar
  5. Mao-cheng Cai, Xiaotie Deng, and Wenan Zang. A min-max theorem on feedback vertex sets. Math. Oper. Res., 27(2):361-371, 2002. Google Scholar
  6. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Ann. of Math. (2), 162(1):439-485, 2005. Google Scholar
  7. 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. Google Scholar
  8. Guy Even, Joseph (Seffi) Naor, Baruch Schieber, and Madhu Sudan. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151-174, 1998. Google Scholar
  9. Samuel Fiorini, Gwenaël Joret, and Oliver Schaudt. Improved approximation algorithms for hitting 3-vertex paths. In Proc. IPCO 2016, volume 9682 of Lecture Notes Comput. Sci., pages 238-249, 2016. Google Scholar
  10. Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. Exact algorithms via monotone local search. In Proc. STOC 2016, pages 764-775, 2016. Google Scholar
  11. Serge Gaspers and Matthias Mnich. Feedback vertex sets in tournaments. J. Graph Theory, 72(1):72-89, 2013. Google Scholar
  12. Kamal Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  13. 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. Google Scholar
  14. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. System Sci., 74(3):335-349, 2008. Google Scholar
  15. Michael Krivelevich. On a conjecture of Tuza about packing and covering of triangles. Discrete Math., 142(1):281-286, 1995. Google Scholar
  16. 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. Google Scholar
  17. Lap Chi Lau, R. Ravi, and Mohit Singh. Iterative methods in combinatorial optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, New York, 2011. Google Scholar
  18. John W. Moon. On maximal transitive subtournaments. Proc. Edinburgh Math. Soc. (2), 17:345-349, 1970/71. Google Scholar
  19. Adolfo Sanchez-Flores. On tournaments free of large transitive subtournaments. Graphs Comb., 14(2):181-200, 1998. Google Scholar
  20. Prashant Sasatte. Improved approximation algorithm for the feedback set problem in a bipartite tournament. Oper. Res. Lett., 36(5):602-604, 2008. Google Scholar
  21. Paul D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281-288, 1995. Google Scholar
  22. Ewald Speckenmeyer. On feedback problems in digraphs. In Proc. WG 1989, volume 411 of Lecture Notes Comput. Sci., pages 218-231. Springer, 1990. Google Scholar
  23. Anke van Zuylen. Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theor. Comput. Sci., 412(23):2556-2561, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact