Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case

References

• [1] Aprile M, Fiorini S (2022) Regular matroids have polynomial extension complexity. Math. Oper. Res. 47(1):540–559.Link, Google Scholar
• [2] Aprile M, Fiorini S, Joret G, Kober S, Seweryn MT, Weltge S, Yuditsky Y (2025) Integer programs with nearly totally unimodular matrices: The cographic case. Azar Y, Panigrahi D, eds. Proc. 2025 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2301–2312.Google Scholar
• [3] Artmann S, Weismantel R, Zenklusen R (2017) A strongly polynomial algorithm for bimodular integer linear programming. Hatami H, McKenzie P, King V, eds. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1206–1219.Google Scholar
• [4] Bhaskara A, Charikar M, Chlamtac E, Feige U, Vijayaraghavan A (2010) Detecting high log-densities: An O(n1/4) approximation for densest k-subgraph. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 201–210.Google Scholar
• [5] Bock A, Faenza Y, Moldenhauer C, Ruiz-Vargas AJ (2014) Solving the stable set problem in terms of the odd cycle packing number. Raman V, Suresh SP, eds. Thirty-fourth Internat. Conf. Foundation Software Tech. Theoret. Comput. Sci. (Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Wadern, Germany), 187–198.Google Scholar
• [6] Böhme T, Mohar B (2002) Labeled K2,t minors in plane graphs. J. Combin. Theory Ser. B 84(2):291–300.Crossref, Google Scholar
• [7] Böhme T, Kawarabayashi K, Maharry J, Mohar B (2008) K3,k-minors in large 7-connected graphs. Accessed July 7, 2024, https://people.math.osu.edu/maharry.1/Preprints/BM08_Preprint_Bohme_MinorsinLarge7ConnectedGraphs.pdf.Google Scholar
• [8] Bonifas N, Di Summa M, Eisenbrand F, Hähnle N, Niemeier M (2014) On sub-determinants and the diameter of polyhedra. Discrete Comput. Geometry 52(1):102–115.Crossref, Google Scholar
• [9] Bouchet A (1978) Orientable and nonorientable genus of the complete bipartite graph. J. Combin. Theory Ser. B 24(1):24–33.Crossref, Google Scholar
• [10] Briański M, Koutecký M, Král’ D, Pekárková K, Schröder F (2024) Characterization of matrices with bounded graver bases and depth parameters and applications to integer programming. Math. Programming 208(1):497–531.Crossref, Google Scholar
• [11] Celaya M, Kuhlmann S, Paat J, Weismantel R (2022) Improving the Cook et al. proximity bound given integral valued constraints. Aardal K, Sanità L, eds. Integer Programming and Combinatorial Optimization (Springer International Publishing, Cham, Switzerland), 84–97.Crossref, Google Scholar
• [12] Chuzhoy J, Tan Z (2021) Towards tight(er) bounds for the excluded grid theorem. J. Combin. Theory Ser. B 146:219–265.Crossref, Google Scholar
• [13] Conforti M, Fiorini S, Huynh T, Weltge S (2020) Extended formulations for stable set polytopes of graphs without two disjoint odd cycles. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin, Heidelberg), 104–116.Google Scholar
• [14] Conforti M, Fiorini S, Huynh T, Joret G, Weltge S (2020) The stable set problem in graphs with bounded genus and bounded odd cycle packing number. Chawla S, ed. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2896–2915.Google Scholar
• [15] Cook W, Gerards AM, Schrijver A, Tardos É (1986) Sensitivity theorems in integer linear programming. Math. Programming 34(3):251–264.Crossref, Google Scholar
• [16] Cslovjecsek J, Eisenbrand F, Hunkenschröder C, Rohwedder L, Weismantel R (2021) Block-structured integer and linear programming in strongly polynomial and near linear time. Marx D, ed. Proc. 32nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1666–1681.Google Scholar
• [17] Cslovjecsek J, Eisenbrand F, Pilipczuk M, Venzin M, Weismantel R (2021) Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity. Mutzel P, Pagh R, Herman G, eds. 29th Annual Eur. Sympos. Algorithms (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 33:1–33:14.Google Scholar
• [18] Cslovjecsek J, Kouteckỳ M, Lassota A, Pilipczuk M, Polak A (2025) Parameterized algorithms for block-structured integer programs with large entries. TheoretiCS 4.Crossref, Google Scholar
• [19] Cunningham WH, Edmonds J (1980) A combinatorial decomposition theory. Canadian J. Math. 32(3):734–765.Crossref, Google Scholar
• [20] Dadush D (2012) Integer programming, lattice algorithms, and deterministic volume estimation. Unpublished PhD thesis, Georgia Institute of Technology, Atlanta.Google Scholar
• [21] Di Battista G, Tamassia R (1989) Incremental planarity testing. 30th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Research Triangle Park, NC), 436–441.Google Scholar
• [22] Diestel R, Kawarabayashi K, Müller T, Wollan P (2012) On the excluded minor structure theorem for graphs of large tree-width. J. Combin. Theory Ser. B 102(6):1189–1210.Crossref, Google Scholar
• [23] Dyer M, Frieze A (1994) Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Programming 64(1–3):1–16.Crossref, Google Scholar
• [24] Eisenbrand F, Vempala S (2017) Geometric random edge. Math. Programming 164(1–2):325–339.Crossref, Google Scholar
• [25] Eisenbrand F, Weismantel R (2019) Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms 16(1):1–14.Crossref, Google Scholar
• [26] Eisenbrand F, Rohwedder L, Węgrzycki K (2024) Sensitivity, proximity and FPT algorithms for exact matroid problems. IEEE 65th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 1610–1620.Google Scholar
• [27] Eisenbrand F, Hunkenschröder C, Klein KM, Koutecký M, Levin A, Onn S (2022) An algorithmic theory of integer programming. Preprint, submitted April 2, 2019, https://arxiv.org/abs/1904.01361.Google Scholar
• [28] El Maalouly N (2023) Exact matching: Algorithms and related problems. Berenbrink P, Bouyer P, Dawar A, Kanté MM, eds. 40th Internat. Sympos. Theoret. Aspects Comput. Sci. (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Wadern, Germany), 29:1–29:17.Google Scholar
• [29] Fiorini S, Joret G, Weltge S, Yuditsky Y (2025) Integer programs with bounded subdeterminants and two nonzeros per row. J. ACM 72(1):1–50.Crossref, Google Scholar
• [30] Fiorini S, Kober S, Seweryn MT, Shantanam A, Yuditsky Y (2025) Face covers and rooted minors in bounded genus graphs. Preprint, submitted March 12, https://arxiv.org/abs/2503.09230.Google Scholar
• [31] Geelen J, Gerards B, Whittle G (2014) Solving Rota’s conjecture. Notices Amer. Math. Soc. 61:736–743.Crossref, Google Scholar
• [32] Geelen J, Gerards B, Whittle G (2015) The highly connected matroids in minor-closed classes. Ann. Combin. 19:107–123.Crossref, Google Scholar
• [33] Geelen J, Nelson P, Walsh Z (2024) Excluding a Line from Complex-Representable Matroids, vol. 303 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [34] Gijswijt D (2005) Integer decomposition for polyhedra defined by nearly totally unimodular matrices. SIAM J. Discrete Math. 19(3):798–806.Crossref, Google Scholar
• [35] Gutwenger C, Mutzel P (2000) A linear time implementation of SPQR-trees. Marks L, ed. Internat. Sympos. Graph Drawing (Springer, Berlin, Heidelberg), 77–90.Google Scholar
• [36] Jung HA (1970) Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen. Math. Ann. 187:95–103.Crossref, Google Scholar
• [37] Kannan R (1987) Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3):415–440.Link, Google Scholar
• [38] Kawarabayashi K, Thomas R, Wollan P (2020) Quickly excluding a non-planar graph. Preprint, submitted October 23, https://arxiv.org/abs/2010.12397.Google Scholar
• [39] Khot S (2006) Ruling out PTAS for graph min‐bisection, dense k‐subgraph, and bipartite clique. SIAM J. Comput. 36(4):1025–1071.Crossref, Google Scholar
• [40] Kober SA (2023) Three perspectives on integer programming: Practical and theoretical applications, and the case of bounded subdeterminants. Unpublished PhD thesis, Technische Universität München, Germany.Google Scholar
• [41] Kolliopoulos SG, Steiner G (2002) Partially-ordered knapsack and applications to scheduling. Möhring R, Raman R, eds. Algorithms—ESA 2002 (Springer, Berlin, Heidelberg), 612–624.Crossref, Google Scholar
• [42] Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [43] Manurangsi P (2017) Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. Hatami H, McKenzie P, King V, eds. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 954–961.Google Scholar
• [44] Mohar B (1997) Face-width of embedded graphs. Math. Slovaca 47(1):35–63.Google Scholar
• [45] Mohar B (2001) Face covers and the genus problem for apex graphs. J. Combin. Theory Ser. B 82(1):102–117.Crossref, Google Scholar
• [46] Mohar B, Thomassen C (2001) Graphs on Surfaces (Johns Hopkins University Press, Baltimore).Crossref, Google Scholar
• [47] Mulmuley K, Vazirani UV, Vazirani VV (1987) Matching is as easy as matrix inversion. Proc. 19th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 345–354.Google Scholar
• [48] Nägele M, Santiago R, Zenklusen R (2022) Congruency-constrained TU problems beyond the bimodular case. Naor J, Buchbinder N, eds. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2743–2790.Google Scholar
• [49] Nägele M, Nöbel C, Santiago R, Zenklusen R (2023) Advances on strictly ∆-modular IPs. Pia AD, Kaibel V, eds. Proc. 24th Conf. Integer Programming Combin. Optim. (Springer-Verlag, Berlin, Heidelberg), 393–407.Google Scholar
• [50] Onn S (2010) Nonlinear discrete optimization. Zur. Lect. Adv. Math., Eur. Math. Soc. (European Mathematical Society (EMS), Zürich, Switzerland).Google Scholar
• [51] Oxley JG (2006) Matroid Theory, vol. 3 (Oxford University Press, Oxford, UK).Google Scholar
• [52] Paat J, Weismantel R, Weltge S (2020) Distances between optimal solutions of mixed-integer programs. Math. Programming 179(1):455–468.Crossref, Google Scholar
• [53] Papadimitriou CH (1981) On the complexity of integer programming. J. ACM 28(4):765–768.Crossref, Google Scholar
• [54] Reis V, Rothvoss T (2023) The subspace flatness conjecture and faster integer programming. IEEE 64th Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 974–988.Google Scholar
• [55] Ringel G (1965) Das Geschlecht des vollständigen paaren Graphen. Abhandlungen Aus Dem Mathematischen Seminar Der Universität Hamburg 28:139–150.Crossref, Google Scholar
• [56] Robertson N, Seymour PD (1986) Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B 41(1):92–114.Crossref, Google Scholar
• [57] Robertson N, Seymour PD (1990) Graph minors IX. Disjoint crossed paths. J. Combin. Theory Ser. B 49(1):40–77.Crossref, Google Scholar
• [58] Robertson N, Vitray RP (1990) Representativity of surface embeddings. Korte B, Promel HJ, Graham RL, eds. Paths, Flows, and VLSI-Layout (Springer-Verlag, Berlin, Heidelberg), 293–298.Google Scholar
• [59] Schrijver A (1998) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• [60] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin, Heidelberg).Google Scholar
• [61] Sevast’janov S (1978) Approximate solution of some problems of scheduling theory. Metody Diskret. Analiz. 32:66–75.Google Scholar
• [62] Sevast’janov S, Banaszczyk W (1997) To the Steinitz lemma in coordinate form. Discrete Math. 169(1–3):145–152.Crossref, Google Scholar
• [63] Seymour PD (1980) Decomposition of regular matroids. J. Combin. Theory Ser. B 28(3):305–359.Crossref, Google Scholar
• [64] Seymour P (1980) Disjoint paths in graphs. Discrete Math. 29(3):293–309.Crossref, Google Scholar
• [65] Seymour PD (1981) On minors of non-binary matroids. Combinatorica 1:387–394.Crossref, Google Scholar
• [66] Shiloach Y (1980) A polynomial solution to the undirected two paths problem. J. ACM 27(3):445–456.Crossref, Google Scholar
• [67] Steinitz E (1913) Bedingt konvergente Reihen und konvexe Systeme. J. Für Die Reine Und Angewandte Mathematik 143:128–176.Crossref, Google Scholar
• [68] Tardos E (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34(2):250–256.Link, Google Scholar
• [69] Thilikos DM, Wiederrecht S (2022) Killing a vortex. IEEE 63rd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Los Alamitos, CA), 1069–1080.Google Scholar
• [70] Thilikos DM, Wiederrecht S (2024) Killing a vortex. J. ACM 71(4):1–56.Crossref, Google Scholar
• [71] Thomassen C (1980) 2-linked graphs. Eur. J. Combin. 1(4):371–378.Crossref, Google Scholar
• [72] Tutte W (1960) An algorithm for determining whether a given binary matroid is graphic. Proc. Amer. Math. Soc. 11(6):905–917.Google Scholar
• [73] Tutte W (1965) Lectures on matroids. J. Res. Natl. Bureau Standards 69B(1–2):1–47.Crossref, Google Scholar