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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The Price of Forest Ownership: Unbounded Separation in Pairwise Agreement Budgets

Shuai Zhang, Shuhao Zhang
1 links
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

The Price of Forest Ownership: Unbounded Separation in Pairwise Agreement Budgets

Shuai Zhang, Shuhao Zhang
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Beijing Technology and Business University (CN), Beijing Forestry University (CN)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon