← 研踪 PaperTrailarXiv:2611.19447 · v1
Cogirth-Strength Ratios and Matroid Rank Reduction
首次提交 2026-11-14 23:05
版本更新 2026-11-14 23:05
雷达观测 2026-11-17 12:06
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-14 23:05 · 最新观测版本
Cogirth-Strength Ratios and Matroid Rank Reduction
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.
查看此版本解读 →查看此版本原文 ↗