The Price of Forest Ownership: Unbounded Separation in Pairwise Agreement Budgets
We study the number of additional unconditional pairwise agreement coordinates needed to strictly improve a forest-decomposed linear programming relaxation of weighted signed graph partitioning. For every k ≥ 6, we construct one instance on n = k + 3 vertices and two decompositions of its positive edges into three forests. The decompositions have identical forest edge-count multisets, the same base LP value 2k + 3/2, and the same integer optimum 2k + 2. Under a common interaction vertex-cover budget of four, one decomposition needs a single additional coordinate, whereas the other needs exactly k − 1. The ratio of the minimum strengthening budgets is therefore Θ(n), with the instance, encoding family, forest count, and structural budget fixed. The proof characterizes the entire base optimal face through an explicit rational dual certificate. Two equiprobable partitions per forest preserve the base value for every incomplete star; a negative signed cycle forces strict improvement for every complete star. We further prove a complete-star gain of at least 1/(54k) and derive a budget separation under small objective perturbations when improvement is measured against a positive threshold. The separation concerns the first strict improvement; full gap closure is proved for the easy decomposition. Exact finite-instance certificates and Lean 4 checks of the Boolean and pair-moment identities verify specified parts of the argument.
Authors
- Shuai Zhang (ORCID: https://orcid.org/0000-0001-5443-1146)
- Shuhao Zhang
Institutions
- Beijing Technology and Business University (CN)
- Beijing Forestry University (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24199785
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint