Packing Feedback Arc Sets in Tournaments Exactly

References

• [1] Abdi A, Cornuéjols G, Zlatin M (2022) On packing dijoins in digraphs and weighted digraphs. Preprint, submitted March 30, https://arxiv.org/abs/2202.00392v3.Google Scholar
• [2] Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: Ranking and clustering. J. ACM 55(5):1–27.Google Scholar
• [3] Alon N (2006) Ranking tournaments. SIAM J. Discrete Math. 20(1):137–142.Crossref, Google Scholar
• [4] Applegate D, Cook W, McCormick S (1991) Integral infeasibility and testing total dual integrality. Oper. Res. Lett. 10(1):37–41.Crossref, Google Scholar
• [5] Barahona F, Mahjoub A (1985) Composition in the acyclic subdigraph polytope. Report No. 85371-OR, Institut für Ökonometrie und Operations Research, Universität Bonn, Bonn, Germany.Google Scholar
• [6] Barahona F, Fonlupt J, Mahjoub A (1994) Compositions of graphs and polyhedra IV: Acyclic spanning subgraphs. SIAM J. Discrete Math. 7(3):390–402.Crossref, Google Scholar
• [7] Bessy S, Bougeret M, Krithika R, Sahu A, Saurabh S, Thiebaut J, Zehavi M (2021) Packing arc-disjoint cycles in tournaments. Algorithmica 83(5):1393–1420.Crossref, Google Scholar
• [8] Cai M, Deng X, Zang W (2001) An approximation algorithm for feedback vertex sets in tournaments. SIAM J. Comput. 30(6):1993–2007.Crossref, Google Scholar
• [9] Chen X, Ding G, Hu X, Zang W (2006) A min-max relation on packing feedback vertex sets. Math. Oper. Res. 31(4):777–788.Link, Google Scholar
• [10] Chen X, Ding G, Zang W, Zhao Q (2020) Ranking tournaments with no errors I: Structural description. J. Combinatorial Theory Ser. B 141(2):264–294.Crossref, Google Scholar
• [11] Chen X, Ding G, Zang W, Zhao Q (2020) Ranking tournaments with no errors II: Minimax relation. J. Combinatorial Theory Ser. B 142(3):244–275.Crossref, Google Scholar
• [12] Chen X, Hu X, Zang W (2007) A min-max theorem on tournaments. SIAM J. Comput. 37(3):923–937.Crossref, Google Scholar
• [13] Charbit P, Thomassé P, Yeo A (2007) The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics Probab. Comput. 16(1):1–4.Crossref, Google Scholar
• [14] Cornuéjols G, Guenin B (2002) On dijoins. Discrete Math. 243(1):213–216.Crossref, Google Scholar
• [15] Chudnovsky M, Edwards K, Kim R, Scott A, Seymour P (2016) Disjoint dijoins. J. Combinatorial Theory Ser. B 120:18–35.Crossref, Google Scholar
• [16] Ding G, Zang W (2002) Packing cycles in graphs. J. Combinatorial Theory Ser. B 86(2):381–407.Crossref, Google Scholar
• [17] Ding G, Xu Z, Zang W (2003) Packing cycles in graphs, II. J. Combinatorial Theory Ser. B 87(2):244–253.Crossref, Google Scholar
• [18] Edmonds J, Giles R (1977) A min-max relation for submodular functions on graphs. Hammer PL, Johnson EL, Korte BH, Nemhauser GL, eds. Annals of Discrete Mathematics. vol. 1 (North-Holland, Amsterdam), 185–204.Google Scholar
• [19] Feofiloff P, Younger D (1987) Directed cut transversal packing for source-sink connected graphs. Combinatorica 7(3):255–263.Crossref, Google Scholar
• [20] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• [21] Geelen J, Guenin B (2002) Packing odd circuits in Eulerian graphs. J. Combinatorial Theory Ser. B 86(2):280–295.Crossref, Google Scholar
• [22] Guenin B (2001) Circuit Mengerian directed graphs. Aardal K, Gerards B, eds. Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin), 185–195.Crossref, Google Scholar
• [23] Guenin B (2002) A short proof of Seymour’s characterization of the matroids with the max-flow min-cut property. J. Combinatorial Theory Ser. B 86(2):273–279.Crossref, Google Scholar
• [24] Guenin B, Thomas R (2011) Packing directed circuits exactly. Combinatorica 31(4):397–421.Crossref, Google Scholar
• [25] Frank A (1981) How to make a digraph strongly connected. Combinatorica 1(2):145–153.Crossref, Google Scholar
• [26] Jünger M (1985) Polyhedral Combinatorics and the Acyclic Subdigraph Problem (Heldermann Verlag, Berlin).Google Scholar
• [27] Lee O, Wakabayashi Y (2001) Note on a min-max conjecture of Woodall. J. Graph Theory 38(1):36–41.Crossref, Google Scholar
• [28] Lehman A (1979) On the length-width inequality. Math. Programming 17(3):403–417.Crossref, Google Scholar
• [29] Lovász L (1972) Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2(3):253–267.Crossref, Google Scholar
• [30] Lucchesi C, Younger D (1978) A minimax theorem for directed graphs. J. London Math. Soc. (2) 17(3):369–374.Crossref, Google Scholar
• [31] Mathieu C, Schudy W (2007) How to rank with few errors: A PTAS for weighted feedback arc set on tournaments. Johnson DS, Feige U, eds. Proc. 39th Annual ACM Sympos. Theory Comput. (STOC’07) (ACM, New York), 95–103.Google Scholar
• [32] Mészáros A (2018) A note on disjoint dijoins. Combinatorica 38(6):1485–1488.Crossref, Google Scholar
• [33] Schrijver A (1980) A counterexample to a conjecture of Edmonds and Giles. Discrete Math. 32(2):213–214.Crossref, Google Scholar
• [34] Schrijver A (1982) Min-max relations for directed graphs. Ann. Discrete Math. 16:261–280.Google Scholar
• [35] Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• [36] Schrijver A (2003) Combinatorial Optimization–Polyhedra and Efficiency (Springer-Verlag, Berlin).Google Scholar
• [37] Seymour P (1977) The matroids with the max-flow min-cut property. J. Combinatorial Theory Ser. B 23(2–3):189–222.Crossref, Google Scholar
• [38] Seymour P (1996) Packing circuits in Eulerian digraphs. Combinatorica 16(2):223–231.Crossref, Google Scholar
• [39] Source codes. Accessed January 1, 2023, https://www.math.lsu.edu/~ding/1publications.html.Google Scholar
• [40] Williams A, Guenin B (2005) Advances in packing directed joins. Electronic Notes Discrete Math. 19:249–255.Crossref, Google Scholar
• [41] Woodall DR (1978) Menger and Kőnig systems. Lecture Notes in Math. 642:620–635.Crossref, Google Scholar
• [42] Younger D (1963) Minimum feedback arc sets for a directed graph. IEEE Trans. Circuit Theory 10:238–245.Crossref, Google Scholar