Document Open Access Logo

Packing Arc-Disjoint Cycles in Tournaments

Authors Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.27.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Stéphane Bessy
  • Université de Montpellier, LIRMM, CNRS, Montpellier, France
Marin Bougeret
  • Université de Montpellier, LIRMM, CNRS, Montpellier, France
R. Krithika
  • Indian Institute of Technology Palakkad, India
Abhishek Sahu
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Bergen, Norway
Jocelyn Thiebaut
  • Université de Montpellier, LIRMM, CNRS, Montpellier, France
Meirav Zehavi
  • Ben-Gurion University, Beersheba, Israel

Cite As Get BibTex

Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi. Packing Arc-Disjoint Cycles in Tournaments. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.27

Abstract

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, they can be solved in 2^{O(k log k)} n^{O(1)} time and 2^{O(k)} n^{O(1)} time respectively. Moreover, they both admit a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2^{o(sqrt{k})} n^{O(1)} time under the Exponential-Time Hypothesis.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Complexity classes
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • arc-disjoint cycle packing
  • tournaments
  • parameterized algorithms
  • kernelization

Metrics

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

Related Versions

References

  1. F. N. Abu-Khzam. An Improved Kernelization Algorithm for r-Set Packing. Inf. Process. Lett., 110(16):621-624, 2010. Google Scholar
  2. I. Akaria and R. Yuster. Packing Edge-Disjoint Triangles in Regular and Almost Regular Tournaments. Discrete Math., 338(2):217-228, 2015. Google Scholar
  3. N. Alon. Ranking Tournaments. SIAM J. Discrete Math., 20(1):137-142, 2006. Google Scholar
  4. N. Alon, D. Lokshtanov, and S. Saurabh. Fast FAST. In 36th International Colloquium on Automata, Languages, and Programming (ICALP) Part I, pages 49-58, 2009. Google Scholar
  5. N. Alon, R. Yuster, and U. Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  6. J. Bang-Jensen and G. Gutin. Paths, Trees and Cycles in Tournaments. Congressus Numerantium, 115:131-170, 1996. Google Scholar
  7. J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer-Verlag London, 2009. Google Scholar
  8. S. Bessy, M. Bougeret, and J. Thiebaut. Triangle Packing in (Sparse) Tournaments: Approximation and Kernelization. In 25th Annual European Symp. on Algorithms (ESA 2017), volume 87, pages 14:1-14:13, 2017. Google Scholar
  9. S. Bessy, F. V. Fomin, S. Gaspers, C. Paul, A. Perez, S. Saurabh, and S. Thomassé. Kernels for Feedback Arc Set in Tournaments. J. Comput. Syst. Sci, 77(6):1071-1078, 2011. Google Scholar
  10. H. L. Bodlaender. On Disjoint Cycles. Int. J. Found. Comput. S., 5(1):59-68, 1994. Google Scholar
  11. H. L. Bodlaender, S. Thomassé, and A. Yeo. Kernel Bounds for Disjoint Cycles and Disjoint Paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. Google Scholar
  12. A. Caprara, A. Panconesi, and R. Rizzi. Packing Cycles in Undirected Graphs. J. Algorithms, 48(1):239-256, 2003. Google Scholar
  13. P. Charbit, S. Thomassé, and A. Yeo. The Minimum Feedback Arc Set Problem is NP-hard for Tournaments. Comb Probab Comput., 16(1):1-4, 2007. Google Scholar
  14. M. Chudnovsky, P. Seymour, and B. Sullivan. Cycles in Dense Digraphs. Combinatorica, 28(1):1-18, 2008. Google Scholar
  15. W. W. Cohen, R. E. Schapire, and Y. Singer. Learning to Order Things. Journal of Artificial Intelligence Research, 10:243-270, 1999. Google Scholar
  16. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  17. Jean-Charles de Borda. Mémoire sur les élections au scrutin. Histoire de l'Académie Royale des Sciences, 1781. Google Scholar
  18. D. Dorninger. Hamiltonian Circuits Determining the Order of Chromosomes. Discrete Appl. Math., 50(2):159-168, 1994. Google Scholar
  19. R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer-Verlag London, 2013. Google Scholar
  20. C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank Aggregation Methods for the Web. In 10th International World Wide Web Conference, pages 613-622, 2001. Google Scholar
  21. P. Erdős and L. Pósa. On Independent Circuits Contained in a Graph. Canadian J. Math., 17:347-352, 1965. Google Scholar
  22. S. Even, A. Itai, and A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM J. Comput., 5(4):691-703, 1976. Google Scholar
  23. U. Feige. Faster FAST(Feedback Arc Set in Tournaments), 2009. URL: http://arxiv.org/abs/0911.5094.
  24. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  25. F. V. Fomin, D. Lokshtanov, V. Raman, and S. Saurabh. Fast Local Search Algorithm for Weighted Feedback Arc Set in Tournaments. In 24th AAAI Conf. on Artificial Intelligence, pages 65-70, 2010. Google Scholar
  26. F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. Google Scholar
  27. S. Fortune, J. Hopcroft, and J. Wyllie. The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci., 10(2):111-121, 1980. Google Scholar
  28. R. B. Gardner. Optimal Packings and Coverings of the Complete Directed Graph with 3-Circuits and with Transitive Triples. In 28th Southeastern International Conference on Combinatorics, Graph Theory and Computing, volume 127, pages 161-170, 1997. Google Scholar
  29. E. Hemaspaandra, H. Spakowski, and J. Vogel. The Complexity of Kemeny Elections. Theor. Comput. Sci., 349(3):382-391, 2005. Google Scholar
  30. R. Impagliazzo, R. Paturi, and F. Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci, 63(4):512-530, 2001. Google Scholar
  31. M. Karpinski and W. Schudy. Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. In 21st International Symp. on Algorithms and Computation (ISAAC), pages 3-14, 2010. Google Scholar
  32. T. P. Kirkman. On a Problem in Combinations. Cambridge and Dublin Mathematical Journal, 2:191-204, 1847. Google Scholar
  33. M. Krivelevich, Z. Nutov, M. R. Salavatipour, J. V. Yuster, and R. Yuster. Approximation Algorithms and Hardness Results for Cycle Packing Problems. ACM Transactions on Algorithms, 3(4), 2007. Google Scholar
  34. M. Krivelevich, Z. Nutov, and R. Yuster. Approximation Algorithms for Cycle Packing Problems. In 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 556-561, 2005. Google Scholar
  35. T. Le, D. Lokshtanov, S. Saurabh, S. Thomassé, and M. Zehavi. Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems. In 29th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 331-342, 2018. Google Scholar
  36. D. Lokshtanov, A. Mouawad, S. Saurabh, and M. Zehavi. Packing Cycles Faster Than Erdős-Pósa. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 71:1-71:15, 2017. Google Scholar
  37. M. Mahajan and V. Raman. Parameterizing Above Guaranteed Values: MaxSat and MaxCut. J. Algorithms, 31(2):335-354, 1999. Google Scholar
  38. J.W. Moon. Topics on Tournaments. Holt, Rinehart and Winston, New York, 1968. Google Scholar
  39. C. H. Papadimitriou. Computational Complexity. John Wiley and Sons Ltd., 2003. Google Scholar
  40. M. Pilipczuk. Tournaments and Optimality: New Results in Parameterized Complexity. PhD thesis, The University of Bergen, 2013. Google Scholar
  41. J. P. Schmidt and A. Siegel. The Spatial Complexity of Oblivious k-Probe Hash Functions. SIAM J. Comput., 19(5):775-786, 1990. Google Scholar
  42. A. Slivkins. Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs. SIAM J. Discrete Math., 24(1):146-157, 2010. Google Scholar
  43. C. A. Tovey. A simplified NP-complete satisfiability problem. Discrete Appl. Math., 8(1):85-89, 1984. Google Scholar
  44. R. Yuster. Packing Triangles in Regular Tournaments. J. of Graph Theory, 74(1):58-66, 2013. 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