WorksComputer Science
Cogirth-Strength Ratios and Matroid Rank Reduction
Abstract
In the rank- reduction problem, we are given a matroid with nonnegative element weights and seek a minimum-weight set of elements whose deletion lowers the rank by at least . For graphic matroids, this is the minimum -cut problem. Chekuri, Quanrud, and Xu developed a tree-packing algorithm for minimum -cut, which relies on the fact that the minimum cut of a graph is at most twice its strength, the value of a maximum fractional packing of spanning trees. We generalize this approach from graphs to matroids. The matroid analogue of the minimum cut is the cogirth, the minimum weight of a cocircuit, and the analogue of graph strength is matroid strength, the value of a maximum fractional packing of bases. We show that if every matroid in a deletion-closed class has cogirth at most times its strength, then for every , the natural linear programming relaxation of rank- reduction is within a factor of of the optimum. As a result, repeatedly deleting a minimum-weight cocircuit gives a -approximation, and an optimal solution can be found deterministically in time on elements. For graphs, and our framework specializes to the tree-packing approach. As applications, we bound the cogirth-strength ratio for two broad classes, and both bounds are tight. For quasi-graphic matroids, which include graphic, bicircular, frame, and lifted-graphic matroids, the ratio is at most for all weights, giving a -approximation and an exact -time algorithm. For -count matroids of hypergraphs with and edge size at most , the ratio is at most under unit weights. This gives a -approximation and an exact -time algorithm for unweighted rank- reduction.
Introduction
Let be a matroid on a ground set with nonnegative element weights . In the rank- reduction problem, studied by Joret and Vetta [17], we seek a minimum-weight set of elements whose deletion lowers the rank of by at least . We write for its optimum. For the graphic matroid of a connected graph, deleting a set of edges lowers the rank by exactly when it leaves components, so rank- reduction is the minimum -cut problem. For , it suffices to consider cocircuits, the inclusionwise minimal sets whose deletion lowers the rank. The minimum weight of a cocircuit is the weighted cogirth , the matroid analogue of the minimum cut.
A set lowers the rank by at least if and only if it contains at least elements of every base. Writing for the set of bases of and , this leads to the base-hitting LP
which generalizes the LP formulation of minimum -cut [6]. Its dual is
For , the upper bounds are redundant, so we may take , and (2) asks for a maximum fractional packing of bases in which each element has capacity . Its optimum is the weighted strength [4, 19]. Since such a packing is also feasible for (2) for every , we have .
In this paper we focus on the cogirth–strength ratio , which is the integrality gap of (1) for . For unit weights we drop the subscript and write . In graphs, the theorem of Nash-Williams and Tutte [24, 30] implies that the minimum cut is at most twice the strength, and this fact underlies the tree-packing approach to minimum -cut [6]. For general matroids, the ratio can be arbitrarily large.1 We ask which matroids have bounded cogirth–strength ratio, and what a bounded ratio implies for rank- reduction when .
Previous work. As a special case of rank reduction, the minimum -cut problem has been studied extensively [14, 26, 29, 16, 22, 15]. Two lines of work are most relevant to us. The first is the LP-based tree-packing approach of Chekuri, Quanrud, and Xu [6], which bounds the integrality gap of the spanning-tree relaxation of -cut and derives an exact enumeration algorithm from an optimal fractional tree packing. Our framework generalizes this approach from spanning trees to bases of matroids. The second is the series of works built on Karger’s random contraction algorithm [18, 20, 15], which very recently inspired a random deletion algorithm of Chandrasekaran, Chekuri, and Zhu [5]: it enumerates all -approximate minimum circuits of an -element regular matroid in randomized time.
Beyond graphic matroids, Joret and Vetta [17] showed that rank reduction is polynomial-time solvable for partition matroids but NP-hard for intersections of two partition matroids. Other works have focused on cut problems for specific matroid classes. For a hypergraph and integers , the -count matroid has as independent sets the edge sets such that for every nonempty , where is the set of vertices met by . Narayanan, Roy, and Patkar [23] studied approximation algorithms for hypergraph cut problems, and Fukunaga [12] gave an exact algorithm for hypergraph -cut when both and the maximum hyperedge size are fixed. Király [21] proved that the unweighted cogirth of can be computed in polynomial time without any bound on the hyperedge size. Cong, Xu, and Zhao [8] recently proved that computing the unweighted cogirth of the two-dimensional rigidity matroid of a simple graph, which is its -count matroid, is NP-hard. Geelen and Kapadia [13] gave randomized fixed-parameter tractable algorithms for computing the girth and the cogirth of rank- perturbed graphic matroids, and Cong, Xu, and Zhao [7] derandomized the cogirth algorithm. The relationship between cogirth and base packing has also been studied independently: Bailey, Newman, and Stevens [1] investigated matroids whose cogirth equals their integral base-packing number, and noted the difficulty of recognizing this equality in polynomial time for general matroids.
These results show that rank reduction behaves very differently across matroid classes, and most algorithms exploit structure specific to one class. It is natural to ask whether a single condition yields approximation guarantees and exact algorithms for many classes at once. We show that a bounded cogirth–strength ratio is such a condition.
Our contributions. Throughout, matroid has elements and is given by an independence oracle. Our first result shows that the integrality gap for controls the integrality gap for every . If for every positive-rank restriction of , then for every , and deleting a minimum-weight cocircuit times attains this bound (Theorem 1). Adapting the enumeration algorithm of Chekuri, Quanrud, and Xu [6], with bases in place of spanning trees and flats in place of graph components, we compute an optimal solution deterministically in time, and implement the greedy -approximation in time (Theorem 2). Neither algorithm needs to know . As a by-product, we decide in polynomial time whether the cogirth of a matroid equals its integral base-packing number, which resolves the recognition problem noted by Bailey, Newman, and Stevens [1].
We then bound the cogirth–strength ratio for two deletion-closed classes.
Quasi-graphic matroids, which include graphic, bicircular, frame, and lifted-graphic matroids [3], have weighted ratio at most 2 (Theorem 5). This gives a 2-approximation and an exact -time algorithm for weighted rank- reduction.
For , the count matroid of a hypergraph with edges of size at most has ratio at most under unit weights (Theorem 4). This gives a -approximation and an exact -time algorithm for unweighted rank- reduction.
Both bounds are tight. The one for count matroids follows from the subadditivity of the unweighted ratio under matroid union (Theorem 3).
Preliminaries
We assume familiarity with matroid theory and follow the notation of [25]. For a matroid on ground set , we write for its rank function, for its rank, and for its set of bases. For , we write , , and for the matroids obtained by deleting , contracting , and restricting to , respectively. The closure of is the set of elements whose addition to does not increase the rank. A flat is a set equal to its closure, and a hyperplane is a flat of rank . A cocircuit is a minimal set whose deletion decreases the rank. Cocircuits are exactly the complements of hyperplanes. For and , we write .
Let be weights; on minors of , denotes the restricted weights. The weighted cogirth is the minimum weight of a cocircuit. The weighted strength is the minimum of over all flats of rank less than ; by the base-packing theorem, it equals the optimum of (2) for (see § 3.1). Unless stated otherwise, all matroids considered are loopless and of positive rank. For unit weights we drop the subscript , and the cogirth–strength ratio is . For weights with , we write , and the weighted cogirth–strength ratio is the supremum of over all such weights.
Let be matroids on disjoint ground sets , respectively. Their direct sum is the matroid on with independent sets .
Lemma 1. Let and let . Then and .
Proof. The cocircuits of are exactly the cocircuits of the summands , giving .
Every flat of has the form , where is a flat of , and for all . If , then
Equality holds when attains for a minimizing and for . Hence . □
In particular, whenever , since any attaining has cogirth at least .
Rank- reduction
Throughout this section, let , and let be an -element matroid of rank at least with element weights . Rank- reduction asks for a minimum-weight set whose deletion lowers the rank by at least . A set is a -cocycle if is a flat and .
Every rank- reduction set contains the -cocycle . Hence rank- reduction is the minimum-weight -cocycle problem. We write for its optimum.
The base-hitting LP and its gap
We bound the integrality gap of (1) by following the greedy algorithm that repeatedly deletes a minimum-weight cocircuit. Recall that [27 Section 42.4]. Deleting a cocircuit lowers the rank by exactly one, so together with any rank- reducing set of is a rank- reducing set of . The next lemma is the fractional counterpart: deleting and lowering the target by one decreases the LP optimum by at least .
Lemma 2. Let be a cocircuit of . Then , with the convention .
Proof. The case is immediate, so assume . Put , let be any feasible solution to the rank- LP (1) on , and set . Extend by zero on . Since and , we have coordinatewise, so both and lie in .
Since is a cocircuit, is a hyperplane, so every base of extends to a base of by adding any . Choosing with gives and hence , so is feasible for the rank- LP on .
Moreover, every base of meets the cocircuit , so . Together with and , this gives
so is feasible for the rank-one LP on . Since vanishes on , the objective values of and sum to , giving . Minimizing over feasible proves the lemma.
Theorem 1. Suppose satisfies for every positive-rank restriction of . Repeatedly deleting a minimum-weight cocircuit for steps produces a -cocycle with , where is the optimum of (1).
Proof. Put . For , let be a minimum-weight cocircuit of and put . The sets form a chain of flats of with ranks , so is a -cocycle. Since , Lemma 2 gives
If every member of a deletion-closed class satisfies , then the weighted LP gap on that class is at most .
Enumeration from the LP gap
The next theorem adapts the LP enumeration of Chekuri, Quanrud, and Xu [6], with bases in place of spanning trees and flats in place of graph components.
Theorem 2. Given an independence oracle for , a minimum-weight -cocycle is computable deterministically in time, where is not part of the input.
Proof. Assume . First we compute and an optimal dual solution of (2). Separation over the base constraints of (1) computes a minimum--weight base and reports a violation exactly when its -weight is below , i.e., there exists a base of with . So Schrijver’s optimization–separation theorem [27] recovers an optimal dual supported on at most base constraints. Since the dual LP has constraints, we may choose an optimal basic feasible solution with at most positive variables. Let and . Then , and by strong duality, . Since , we obtain .
Fix any -cocycle , so . Sampling with probability , dual feasibility gives
so some has .
Every -cocycle meets every base in at least elements. Fix and with . We list all -cocycles with as follows. For such an , the flat contains , so is a flat of disjoint from with
Conversely, for every such flat , the set is a flat of of rank at most , and its complement is a -cocycle with . Every flat of rank at most is the closure of an independent set of size at most , so computing the closures of all such sets in lists all such in time.
For , list the -cocycles with for some , let be the minimum weight found so far, and halt once . By the averaging bound, every -cocycle is listed by threshold . Hence, when the algorithm halts, every -cocycle of weight at most has been listed, so . Moreover, a minimum-weight -cocycle is listed by threshold , after which , so the algorithm halts by . Threshold costs , and summing up to gives time. □
Suppose for every positive-rank restriction of . Then by Theorem 1, so Theorem 2 solves rank- reduction exactly in time. Moreover, each step of the greedy algorithm in Theorem 1 needs a minimum-weight cocircuit of some restriction , which Theorem 2 with finds in time since . Hence the greedy -approximation runs in time. Neither algorithm needs to know .
For unit weights, the case also decides in polynomial time whether equals the maximum number of disjoint bases of , which is by Edmonds’ base packing theorem [9]; this resolves the recognition problem noted by Bailey, Newman, and Stevens [1]. Since , equality holds only if is an integer and . In that case every minimum cocircuit has , so the averaging bound in the proof of Theorem 2 shows that meets some in exactly one element. Hence it suffices to run the enumeration with threshold , which takes polynomial time, and compare the minimum found with .
Matroid union
For matroids on a common ground set , their matroid union is a matroid on with independent sets .
Theorem 3. Let be matroids on the same ground set , and put . Then
Proof. Put . We first prove . If , this follows from . Assume , and write for the rank functions of . For , choose attaining the matroid-union rank formula [25 Theorem 12.3.1]. The strength formula gives , also when the left side is zero. Since ,
Taking to be a flat of with gives , so . Every base of spans each : otherwise, an element outside its -closure could be added to its -part in a union decomposition. Thus every cocircuit of meets every base of and hence contains a cocircuit of , giving . Combining the two bounds yields .
Write . Restriction commutes with matroid union, so applying the theorem to the positive-rank restrictions of the summands gives . Thus the greedy algorithm of Theorem 1 gives a -approximation for unweighted rank reduction on the union.
Lower-range count matroids
Throughout this section, fix integers , , and , and let be a hypergraph. For , let be the set of vertices met by . Recall that the -count matroid has as its independent sets those satisfying for every nonempty . We write for the complete -uniform hypergraph on vertices, and .
Theorem 4. If has edge size at most , then . Moreover, as .
Since lower-range count matroids are closed under deletion, Theorem 1 and Theorem 2, with unit weights, give a -approximation for every feasible rank loss and exact rank- reduction in time.
By the maps-and-trees decomposition [28 Theorem 1.7 and Proposition 4.3], is the matroid union of copies of the hypergraphic matroid and copies of , the transversal matroid of the edge–vertex incidence bipartite graph:
By Theorem 3, the upper bound reduces to bounding the ratios of and by .
The upper bound
For , we translate the known hypergraph partition bound into a cogirth–strength bound.
Proposition 1. If has edge size at most , then .
Proof. Write , , and . Since , we have . For a partition of , let be the set of edges meeting more than one part, and set . By the hypergraphic rank formula of Frank, Király, and Kriesell [11], for every . In particular, , with equality if and only if .
Suppose first that , so . We show that . For any with , choose a partition attaining . Since , subtracting from numerator and denominator shows
Conversely, let be a partition attaining , and put . Since , we have , and taking gives
Hence . By a result of Baïou and Barahona [2], there is a bipartition of with . Deleting lowers the rank of to at most , so .
Having established the bound when , we now consider general . Choose a partition attaining , and for each let be the subhypergraph of edges contained in . Since for each , the sets contribute at most to the rank, and each edge in contributes at most one. Equality implies that for every , every edge in is a coloop, and is the direct sum of these coloops and the restrictions with . Each such has and hence , so by the first case, while each coloop has cogirth–strength ratio . Hence, Lemma 1 gives
For , the bound follows from the transversal-matroid rank formula.
Proposition 2. If has edge size at most , then .
Proof. Write and . The defect form of Hall’s theorem gives the standard transversal-matroid rank formula [27 Theorem 22.2]. Let attain the minimum for . Then , otherwise some subset would yield a smaller value in the rank formula for . Hence , so every element of is a coloop. If such an element exists, then . We may therefore assume and .
Take with , and let attain the minimum in the rank formula for . Put . Then . Applying the rank formula for to gives . Deleting all edges incident to any vertex in reduces the rank, so is at most the minimum number of edges incident to a vertex in . Since no edge of meets , and each edge of meets at most vertices of , averaging gives
where the last inequality follows from . Minimizing over such proves the proposition.
Propositions 1 and 2, together with (3) and Theorem 3, prove the upper bound in Theorem 4. We defer the matching lower bound to Appendix § 7: the complete -uniform hypergraphs satisfy as . Adding vertex-disjoint single-edge components to , which contribute coloops, yields count matroids of hypergraphs with edge size at most whose rank- integrality gap also tends to . Hence the LP gap bound is sharp for every fixed .
Although our unweighted analysis does not generalize directly to the weighted case, it is natural to ask whether a bound independent of the weights still holds for all lower-range count matroids of bounded edge size. However, no such bound exists. In fact, the weighted cogirth–strength ratio, and hence the weighted integrality gap of (1), is unbounded even for -count matroids of simple graphs, whose bases are disjoint unions of two spanning trees.
For any integer , form a simple graph from a grid with rows and columns by adding a vertex adjacent to both ends of every row. Give the edges between and weight 1 and call them light; give all other edges weight and call them heavy. We claim that the heavy edges together with any light edges decompose into two edge-disjoint spanning trees. Indeed, color the horizontal edges and the edges between and red, and color the vertical edges blue; this partitions the heavy edges into a red spanning tree of size and a blue forest of size with components . Adding any light edges to the red tree creates edge-disjoint cycles, each formed by and one chosen row. Assign these rows bijectively to , and in the row assigned to , recolor blue the red edge entering from (or from if ). This breaks each red cycle while linking the blue components along , into a spanning tree, proving the claim. Figure 1 illustrates the construction and the decomposition for .
Figure 1. The construction for , with columns , from left to right. Selecting the light edges in the first and third rows gives two edge-disjoint spanning trees and , whose union consists of all heavy edges and the two selected light edges.
Thus the heavy edges plus any light edges form a base of , so , and since there are heavy edges, every base uses at least light edges. Hence . Meanwhile, since every base uses at least of the light edges, , and splitting the light edges into two sets of size gives two bases within capacity , so and .
Quasi-graphic matroids
Quasi-graphic matroids include all frame and lifted-graphic matroids [3]. In particular, for a graph , both the graphic matroid and the bicircular matroid are quasi-graphic. We use the tripartition description of Bowler, Funk, and Slilaty [3].
Let be a graph. A theta subgraph of consists of two distinct vertices together with three internally disjoint paths between them. A proper tripartition of the cycles of is a partition of its cycles into balanced, lift-type, and frame-type cycles such that
no theta subgraph has exactly two of its three cycles in , and
every cycle in shares a vertex with every cycle in .
A subgraph is balanced if all its cycles lie in ; in particular, an acyclic subgraph is balanced. For , consider the spanning subgraph . Let be its number of components, let be its number of balanced components, counting isolated vertices, and let if contains a cycle in and otherwise.
The associated quasi-graphic matroid has rank function [3 Lemma 2.6]
Theorem 5. Every quasi-graphic matroid satisfies .
Proof. Fix weights with . By Lemma 1 we may assume that is connected. If is graphic, Nash–Williams–Tutte [24, 30] gives the bound directly. Otherwise, the connected-framework reduction of Bowler, Funk, and Slilaty [3] gives a connected graph and a proper tripartition representing . Its framework contains an unbalanced cycle, so . Put and .
We prove that for every with . Taking the minimum of over then gives .
For , let be the edges with both endpoints in , let , and let be the edges with exactly one endpoint in . Let be the vertex sets of the components of . For each component set . Each edge of lies in at most two of these sets. An edge within one component, including a loop, lies in one , while an edge joining two components lies in two.
Deleting leaves as a separated component carrying exactly . If this component is balanced, the rank drops: a surviving frame-type cycle makes the first line of the rank formula at most , and otherwise the second line gives the same bound. In the latter case there are at least two components when , while leaves a connected balanced graph of rank .
Suppose contains no frame-type cycle and is unbalanced. It contains a lift-type cycle, which meets every frame-type cycle. Deleting therefore destroys all frame-type cycles: none remains inside , outside it, or across its boundary. Moreover, , since otherwise would
::: have full rank. The surviving graph has at least two components, so the second line of the rank formula gives rank at most .
If contains a frame-type cycle, charge its balanced components, whose number is . Otherwise charge all components, where . Every charged contains a cocircuit.
In all cases, at least components are charged, and each charged has weight at least . The multiplicity bound gives
as required.
The constant 2 is asymptotically sharp already for graphic matroids: the graphic matroid of has and , so .
The quasi-graphic rank formula remains valid after deleting edges, so quasi-graphic matroids form a deletion-closed class. With Theorem 5, Theorem 1 and Theorem 2 give a 2-approximation and an exact -time algorithm for weighted rank- reduction.
Acknowledgements Supported by the National Natural Science Foundation of China under grant 62372093 and by the CCF-Huawei Populus Grove Fund – Theoretical Computer Science Special Project CCF-HuaweiLK2025003.
We thank Benjamin Moseley for hosting Chao at the CMU Tepper School of Business, where part of this work was carried out.
AI disclosure The quasi-graphic result in § 6 was discovered by Fable 5, and the manuscript was prepared with assistance from AI tools. The authors take full responsibility for the correctness and content of the paper, including material generated with AI assistance.
Sharpness for lower-range count matroids
Throughout this appendix, fix integers and . For a hypergraph , , and , write . A vertex subpartition of is a collection of pairwise disjoint nonempty subsets of , including the empty collection ().
Lemma 3. Let be a hypergraph such that is loopless. For every ,
where ranges over all vertex subpartitions of .
Proof. By the count-matroid rank formula [10 Section 13.5.2],
where ranges over collections of pairwise disjoint nonempty subsets of , including the empty collection. Starting from a minimizing collection , merging any two parts with into leaves unchanged and changes by . Repeating until the supports are pairwise disjoint produces a vertex subpartition . Each is nonempty since is loopless. Since for each , we have , so the value of is at most .
Conversely, let be independent in and let be a vertex subpartition. Since is loopless, every edge of is nonempty, so are pairwise disjoint. Moreover, for every : this holds by independence of when , and because when . Therefore
and taking the maximum over gives the reverse inequality.
Proposition 3. For , as .
Proof. Write , and put , , , and . We prove, for all sufficiently large , that , , and .
For a nonempty vertex subpartition other than , put and . Since the sets are pairwise disjoint and nonempty, and , discrete convexity of yields . Indeed, the sum is maximized by concentrating the vertices into as few parts as possible, with at least two nonempty parts. Consequently, . Moreover, since and , we have . By Lemma 3, the corresponding rank certificate has value . The empty certificate has value , which also satisfies , since .
Choose large enough that . The full-block certificate has value , proving . Deleting at most edges decreases any other certificate by at most , while the full-block value stays . Thus . Deleting the edges at one vertex leaves rank at most , giving the upper bound.
Averaging a base under the vertex permutations gives a fractional base packing of total weight , and the empty flat gives the reverse inequality. Since and for , the ratio tends to .
For the graph lower bound, take and put . If has , every nontrivial cut of has size at least . Nash–Williams–Tutte [24, 30] gives edge-disjoint spanning trees. Minimum degree at least gives at least edges, leaving at least edges outside these trees. Add one distinct unused edge to each of trees. The resulting trees and spanning unicyclic graphs form an independent set of size by (3). Thus and . Since the empty flat gives ,
For , Proposition 3 gives the lower bound .
The LP gap bound is sharp for every fixed . Let be the complete-uniform examples above, using complete graphs when , and add coloops to obtain . Adding vertex-disjoint single-edge components realizes as the count matroid of a hypergraph with edge size at most . Averaging a base under vertex permutations gives , while . Every rank- reducing set in lowers the rank of , and deleting all added coloops together with a minimum cocircuit is feasible. Hence
Also . Indeed, assigning one to the coloops and using an optimal rank-one solution on proves the upper bound. If a feasible solution assigns total to the coloops, its other coordinates meet each base of to extent at least . Its total cost is therefore at least , since . Dividing the displayed bounds by proves that .
References
- [1]Robert F. Bailey, Mike Newman, and Brett Stevens. A note on packing spanning trees in graphs and bases in matroids. Australas. J. Combin., 59:24–38, 2014.
- [2]Mourad Baïou and Francisco Barahona. Packing hypertrees and the k-cut problem in hypergraphs. In Learning and Intelligent Optimization, volume 13621 of Lecture Notes in Computer Science, pages 521–534, Cham, 2022. Springer International Publishing.DOI
- [3]Nathan Bowler, Daryl Funk, and Daniel Slilaty. Describing quasi-graphic matroids, 2025. Version 4, incorporating corrections.
- [4]Paul A. Catlin, Jerrold W. Grossman, Arthur M. Hobbs, and Hong-Jian Lai. Fractional arboricity, strength, and principal partitions in graphs and matroids. Discrete Applied Mathematics, 40(3):285–302, 1992.DOI
- [5]Karthekeyan Chandrasekaran, Chandra Chekuri, and Weihao Zhu. Random deletion for circuits in regular matroids. arXiv:2610.33918, 2026.arxiv.org/abs/2610.33918
- [6]Chandra Chekuri, Kent Quanrud, and Chao Xu. LP Relaxation and Tree Packing for Minimum k-Cut. SIAM Journal on Discrete Mathematics, 34(2):1334–1353, 2020.DOI
- [7]Yu Cong, Chao Xu, and Yajie Zhao. Derandomizing Karger’s contraction algorithm for matroids. arXiv:2608.16298, 2026.arxiv.org/abs/2608.16298
- [8]Yu Cong, Chao Xu, and Yajie Zhao. Destroying rigidity in the plane. arXiv:2610.38396, 2026.arxiv.org/abs/2610.38396
- [9]Jack Edmonds. Lehman’s switching game and a theorem of Tutte and Nash-Williams. Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics, 69B(1–2):73–77, 1965.
- [10]András Frank. Connections in Combinatorial Optimization. Oxford University Press, 2011.DOI
- [11]András Frank, Tamás Király, and Matthias Kriesell. On decomposing a hypergraph into k connected sub-hypergraphs. Discrete Applied Mathematics, 131(2):373–383, 2003.DOI
- [12]Takuro Fukunaga. Computing minimum multiway cuts in hypergraphs. Discrete Optimization, 10(4):371–382, 2013.DOI
- [13]Jim Geelen and Rohan Kapadia. Computing Girth and Cogirth in Perturbed Graphic Matroids. Combinatorica, 38(1):167–191, feb 2018.arxiv.org/abs/1504.07647
- [14]Olivier Goldschmidt and Dorit S. Hochbaum. A polynomial algorithm for the k-cut problem for fixed k. Mathematics of Operations Research, 19(1):24–37, 1994.DOI
- [15]Anupam Gupta, David G. Harris, Euiwoong Lee, and Jason Li. Optimal bounds for the k-cut problem. Journal of the ACM, 69(1):1–18, 2022.arxiv.org/abs/2005.08301
- [16]Anupam Gupta, Euiwoong Lee, and Jason Li. Faster exact and approximate algorithms for k-cut. In 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 113–123, 2018.arxiv.org/abs/1807.08144
- [17]Gwenaël Joret and Adrian Vetta. Reducing the rank of a matroid. Discrete Mathematics & Theoretical Computer Science, 17(2):143–156, sep 2015.
- [18]David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 21–30, 1993.DOI
- [19]David R. Karger. Random sampling and greedy sparsification for matroid optimization problems. Mathematical Programming, 82(1-2):41–81, 1998.DOI
- [20]David R. Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601–640, 1996.DOI
- [21]Tamás Király. Computing the minimum cut in hypergraphic matroids. Technical Report QP-2009-05, Egerváry Research Group, Budapest, 2009. www.cs.elte.hu/egres.
- [22]Jason Li. Faster minimum k-cut of a simple graph. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1056–1077. IEEE, 2019.arxiv.org/abs/1910.02665
- [23]H. Narayanan, Subir K. Roy, and Sachin B. Patkar. Approximation algorithms for min-k-overlap problems using the principal lattice of partitions approach. Journal of Algorithms, 21(2):306–330, 1996.
- [24]C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, s1-36(1):445–450, 1961.
- [25]James G. Oxley. Matroid Theory. Oxford graduate texts in mathematics. Oxford University Press, 2006.
- [26]Huzur Saran and Vijay V. Vazirani. Finding k cuts within twice the optimal. SIAM Journal on Computing, 24(1):101–108, 1995.
- [27]Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Number 24 in Algorithms and combinatorics. Springer, Berlin Heidelberg, 2003.
- [28]Ileana Streinu and Louis Theran. Sparse hypergraphs and pebble game algorithms. European Journal of Combinatorics, 30(8):1944–1964, 2009.arxiv.org/abs/math/0703921
- [29]Mikkel Thorup. Minimum k-way cuts via deterministic greedy tree packing. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 159–166, 2008.DOI
- [30]W. T. Tutte. On the problem of decomposing a graph into n connected factors. Journal of the London Mathematical Society, s1-36(1):221–230, 1961.DOI
