Top

Published in:

2020 | OriginalPaper | Chapter

Packing Arc-Disjoint Cycles in Bipartite Tournaments

Authors : Ajay Saju Jacob, R. Krithika

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

An r-partite tournament is a directed graph obtained by assigning a unique orientation to each edge of a complete undirected r-partite simple graph. Given a bipartite tournament T on n vertices, we explore the parameterized complexity of the problem of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k. Although the maximization version of this problem 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 bipartite tournaments, surprisingly no algorithmic results seem to exist. We show that this problem can be solved in \(2^{\mathcal {O}(k \log k)} n^{\mathcal {O}(1)}\) time and admits a kernel with \(\mathcal {O}(k^2)\) vertices.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Maximum Edge-Pair Embedding Bipartite Matching

next chapter Matching Random Colored Points with Rectangles

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

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

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

Bessy, S., et al.: Packing arc-disjoint cycles in tournaments. In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), pp. 27:1–27:14 (2019)

Bessy, S., et al.: Kernels for feedback arc set in tournaments. J. Comput. Syst. Sci. 77(6), 1071–1078 (2011)MathSciNetCrossRef

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

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

Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3CrossRefMATH

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013). https://doi.org/10.1007/978-1-4471-5559-1CrossRefMATH

10.

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

11.

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

12.

Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-29953-XCrossRefMATH

13.

Fomin, F., Pilipczuk, M.: Subexponential parameterized algorithm for computing the cutwidth of a semi-complete digraph. In: 21st Annual European Symposium on Algorithms (ESA 2013), vol. 8125, pp. 505–516 (2013)

14.

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

15.

Guo, J., Hüffner, F., Moser, H.: Feedback arc set in bipartite tournaments is \( NP\)-complete. Inf. Process. Lett. 102(2), 62–65 (2007)MathSciNetCrossRef

16.

Karpinski, M., Schudy, W.: Faster algorithms for feedback arc set tournament, kemeny rank aggregation and betweenness tournament. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol. 6506, pp. 3–14. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17517-6_3CrossRefMATH

17.

Kemeny, J.: Mathematics without numbers. Daedalus 88(4), 577–591 (1959)

18.

Kemeny, J., Snell, J.: Mathematical Models in the Social Sciences. Blaisdell, New York (1962)MATH

19.

Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 95–103 (2007)

20.

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

21.

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), pp. 71:1–71:15 (2017)

22.

Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of IEEE 36th Annual Foundations of Computer Science, pp. 182–191 (1995)

23.

Paul, C., Perez, A., Thomassé, S.: Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems. CoRR abs/1101.4491 (2011)

24.

Sanghvi, B., Koul, N., Honavar, V.: Identifying and eliminating inconsistencies in mappings across hierarchical ontologies. In: Meersman, R., Dillon, T., Herrero, P. (eds.) OTM 2010. LNCS, vol. 6427, pp. 999–1008. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16949-6_24CrossRef

25.

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

26.

Xiao, M., Guo, J.: A quadratic vertex kernel for feedback arc set in bipartite tournaments. Algorithmica 71(1), 87–97 (2015)MathSciNetCrossRef

27.

van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. Theoret. Comput. Sci. 412(23), 2556–2561 (2011)MathSciNetCrossRef

Title: Packing Arc-Disjoint Cycles in Bipartite Tournaments
Authors: Ajay Saju Jacob
R. Krithika
Publisher: Springer International Publishing
Book: WALCOM: Algorithms and Computation
Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39881-1_21

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner