跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

In the rank-pp 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 pp. For graphic matroids, this is the minimum (p+1)(p+1)-cut problem. Chekuri, Quanrud, and Xu developed a tree-packing algorithm for minimum kk-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 dd times its strength, then for every pp, the natural linear programming relaxation of rank-pp reduction is within a factor of dd of the optimum. As a result, repeatedly deleting a minimum-weight cocircuit gives a dd-approximation, and an optimal solution can be found deterministically in n(2d−1)p+O(1)n^{(2d-1)p+O(1)} time on nn elements. For graphs, d=2d=2 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 22 for all weights, giving a 22-approximation and an exact n3p+O(1)n^{3p+O(1)}-time algorithm. For (k,ℓ)(k,\ell)-count matroids of hypergraphs with 0≤ℓ≤k0\le \ell\le k and edge size at most ss, the ratio is at most ksks under unit weights. This gives a ksks-approximation and an exact n(2ks−1)p+O(1)n^{(2ks-1)p+O(1)}-time algorithm for unweighted rank-pp reduction.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-14 23:05 · 最新观测版本

Cogirth-Strength Ratios and Matroid Rank Reduction

In the rank-pp 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 pp. For graphic matroids, this is the minimum (p+1)(p+1)-cut problem. Chekuri, Quanrud, and Xu developed a tree-packing algorithm for minimum kk-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 dd times its strength, then for every pp, the natural linear programming relaxation of rank-pp reduction is within a factor of dd of the optimum. As a result, repeatedly deleting a minimum-weight cocircuit gives a dd-approximation, and an optimal solution can be found deterministically in n(2d−1)p+O(1)n^{(2d-1)p+O(1)} time on nn elements. For graphs, d=2d=2 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 22 for all weights, giving a 22-approximation and an exact n3p+O(1)n^{3p+O(1)}-time algorithm. For (k,ℓ)(k,\ell)-count matroids of hypergraphs with 0≤ℓ≤k0\le \ell\le k and edge size at most ss, the ratio is at most ksks under unit weights. This gives a ksks-approximation and an exact n(2ks−1)p+O(1)n^{(2ks-1)p+O(1)}-time algorithm for unweighted rank-pp reduction.

查看此版本解读 →查看此版本原文 ↗