[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Packing Arc-Disjoint Cycles in Tournaments

  • Published:
Algorithmica Aims and scope Submit manuscript

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 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 is fixed-parameter tractable via a \(2^{\mathcal {O}(k \log k)} n^{\mathcal {O}(1)}\)-time algorithm and admits a kernel with \(\mathcal {O}(k)\) vertices. Then, we show that ATT too has a kernel with \(\mathcal {O}(k)\) vertices and can be solved in \(2^{\mathcal {O}(k)} n^{\mathcal {O}(1)}\) time. Afterwards, we describe polynomial-time algorithms for ACT and ATT when the input tournament has a feedback arc set that is a matching. We also prove that ACT and ATT cannot be solved in \(2^{o(\sqrt{n})} n^{\mathcal {O}(1)}\) time under the exponential-time hypothesis.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. The authors would like to thank F. Havet for pointing out that Lemma 13 was a consequence of a result by Chudnovsky et al. [15], as well for an improvement of the constant in Theorem 14.

  2. Lemma 15 is Lemma 3.9 of [10] that has been rephrased to avoid the use of several definitions and terminology introduced in [10].

References

  1. Abu-Khzam, F.N.: An improved Kernelization algorithm for r-set packing. Inf. Process. Lett. 110(16), 621–624 (2010)

    Article  MathSciNet  Google Scholar 

  2. Akaria, I., Yuster, R.: Packing edge-disjoint triangles in regular and almost regular tournaments. Discrete Math. 338(2), 217–228 (2015)

    Article  MathSciNet  Google Scholar 

  3. Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20(1), 137–142 (2006)

    Article  MathSciNet  Google Scholar 

  4. Alon, N., Lokshtanov, D., Saurabh, S.: Fast FAST. In: 36th International Colloquium on Automata, Languages, and Programming (ICALP 2009) Part I, pp. 49–58 (2009)

  5. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)

    Article  MathSciNet  Google Scholar 

  6. Bang-Jensen, J., Gutin, G.: Paths, trees and cycles in tournaments. Congressus Numerantium 115, 131–170 (1996)

    MathSciNet  MATH  Google Scholar 

  7. Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications. Springer, London (2009)

    Book  Google Scholar 

  8. Bessy, S., Bougeret, M., Thiebaut, J.: Triangle packing in (sparse) tournaments: approximation and kernelization. In: 25th Annual European Symposium on Algorithms (ESA 2017), vol. 87, pp. 14:1–14:13 (2017)

  9. Bessy, S., Bougeret, M., Thiebaut, J.: (Arc-disjoint) cycle packing in tournament: classical and parameterized complexity (2018). arXiv:1802.06669

  10. Bessy, S., Fomin, F.V., Gaspers, S., Paul, C., Perez, A., Saurabh, S., Thomassé, S.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. 77(6), 1071–1078 (2011)

    Article  MathSciNet  Google Scholar 

  11. Bodlaender, H.L.: On disjoint cycles. Int. J. Found. Comput. Sci. 5(1), 59–68 (1994)

    Article  Google Scholar 

  12. Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570–4578 (2011)

    Article  MathSciNet  Google Scholar 

  13. Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms 48(1), 239–256 (2003)

    Article  MathSciNet  Google Scholar 

  14. Charbit, P., Thomassé, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Comb. Probab. Comput. 16(1), 1–4 (2007)

    Article  MathSciNet  Google Scholar 

  15. Chudnovsky, M., Seymour, P., Sullivan, B.: Cycles in dense digraphs. Combinatorica 28(1), 1–18 (2008)

    Article  MathSciNet  Google Scholar 

  16. Cohen, W.W., Schapire, R.E., Singer, Y.: Learning to order things. J. Artif. Intell. Res. 10, 243–270 (1999)

    Article  MathSciNet  Google Scholar 

  17. Conitzer, V.: Computing slater rankings using similarities among candidates. In: 21st National Conference on Artificial Intelligence, vol. 1, pp. 613–619 (2006)

  18. Cygan, M.: Improved approximation for 3-dimensional matching via bounded pathwidth local search. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pp. 509–518 (2013)

  19. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)

    Book  Google Scholar 

  20. de Borda, J.-C.: Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences (1781)

  21. Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discrete Appl. Math. 50(2), 159–168 (1994)

    Article  MathSciNet  Google Scholar 

  22. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)

    Book  Google Scholar 

  23. Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: 10th International World Wide Web Conference, pp. 613–622 (2001)

  24. Erdős, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347–352 (1965)

    Article  MathSciNet  Google Scholar 

  25. Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691–703 (1976)

    Article  MathSciNet  Google Scholar 

  26. Feige, U.: Faster FAST(Feedback Arc Set in Tournaments) (2009). arXiv:0911.5094

  27. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)

    MATH  Google Scholar 

  28. Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Fast local search algorithm for weighted feedback arc set in tournaments. In: 24th AAAI Conference on Artificial Intelligence, pp. 65–70 (2010)

  29. Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)

    MATH  Google Scholar 

  30. Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111–121 (1980)

    Article  MathSciNet  Google Scholar 

  31. Gardner, R.B.: 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, vol. 127, pp. 161–170 (1997)

  32. Grohe, M., Grüber, M.: Parameterized approximability of the disjoint cycle problem. In: 34th International Colloquium on Automata. Languages, and Programming (ICALP), pp. 363–374. Springer, Berlin (2007)

  33. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)

    Article  MathSciNet  Google Scholar 

  34. Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In: 21st International Symposium on Algorithms and Computation (ISAAC 2010), pp. 3–14 (2010)

  35. Kirkman, T.P.: On a problem in combinations. Camb. Dublin Math. J. 2, 191–204 (1847)

    Google Scholar 

  36. Krithika, R., Sahu, A., Saurabh, S., Zehavi, M.: The parameterized complexity of packing arc-disjoint cycles in tournaments (2018). arXiv:1802.07090

  37. Krivelevich, M., Nutov, Z., Salavatipour, M.R., Yuster, J.V., Yuster, R.: Approximation algorithms and hardness results for cycle packing problems. ACM Trans. Algorithms 3(4), 48 (2007)

    Article  MathSciNet  Google Scholar 

  38. Krivelevich, M., Nutov, Z., Yuster, R.: Approximation algorithms for cycle packing problems. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 556–561 (2005)

  39. Le, T., Lokshtanov, D., Saurabh, S., Thomassé, S., Zehavi, M.: Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. In: 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 331–342 (2018)

  40. le Marquis de Condorcet, M.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, Paris (1785)

  41. Lokshtanov, D., Mouawad, A., Saurabh, S., Zehavi, M.: Packing cycles faster than Erdős–Pósa. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 71:1–71:15 (2017)

  42. Lucchesi, C.L., Younger, D.H.: A minimax theorem for directed graphs. J. Lond. Math. Soc. 17(2), 369–374 (1978)

    Article  MathSciNet  Google Scholar 

  43. Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335–354 (1999)

    Article  MathSciNet  Google Scholar 

  44. Moon, J.W.: Topics on Tournaments. Holt, Rinehart and Winston, New York (1968)

    MATH  Google Scholar 

  45. Papadimitriou, C.H.: Computational Complexity. Wiley, New York (2003)

    MATH  Google Scholar 

  46. Pilipczuk, M.: Tournaments and optimality: new results in parameterized complexity. PhD thesis, The University of Bergen (2013)

  47. Raman, V., Saurabh, S.: Parameterized algorithms for feedback set problems and their duals in tournaments. Theor. Comput. Sci. 351(3), 446–458 (2006)

    Article  MathSciNet  Google Scholar 

  48. Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775–786 (1990)

    Article  MathSciNet  Google Scholar 

  49. Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math. 24(1), 146–157 (2010)

    Article  MathSciNet  Google Scholar 

  50. Speckenmeyer, E.: On feedback problems in digraphs. In: 15th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 218–231 (1990)

  51. Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8(1), 85–89 (1984)

    Article  MathSciNet  Google Scholar 

  52. Yuster, R.: Packing triangles in regular tournaments. J. Graph Theory 74(1), 58–66 (2013)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

Saket Saurabh is supported by funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 819416) and also acknowledges the support of Swarnajayanti Fellowship Grant DST/SJF/MSA-01/2017-18.

Author information

Authors and Affiliations

  1. LIRMM, CNRS, Université de Montpellier, Montpellier, France

    Stéphane Bessy, Marin Bougeret & Jocelyn Thiebaut

  2. Indian Institute of Technology Palakkad, Palakkad, India

    R. Krithika

  3. The Institute of Mathematical Sciences, HBNI, Chennai, India

    Abhishek Sahu & Saket Saurabh

  4. Ben-Gurion University, Beersheba, Israel

    Meirav Zehavi

Authors
  1. Stéphane Bessy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marin Bougeret
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. Krithika
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Abhishek Sahu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Saket Saurabh
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jocelyn Thiebaut
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Meirav Zehavi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Krithika.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This paper is based on the two independent manuscripts [9] and [36]. A preliminary version of this work appears in the Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bessy, S., Bougeret, M., Krithika, R. et al. Packing Arc-Disjoint Cycles in Tournaments. Algorithmica 83, 1393–1420 (2021). https://doi.org/10.1007/s00453-020-00788-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-020-00788-2

Keywords

Search

Navigation