Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems
Hieu Truong Xuan, Khanh To Van
cs.AI
Quick verdict
SAT reformulations of minimum-span antibandwidth (MSABL) and cyclic (MSCABL) beat CPLEX-MIP/Gurobi; CPLEX-CP stays ahead under no-hole constraints.
Summary
This paper recasts the Antibandwidth and Cyclic Antibandwidth problems as minimum-span variants: given a required (cyclic) distance k, find the smallest label domain {1,...,λ} admitting a feasible labeling. The authors build a SAT framework that decomposes each problem into a monotone sequence of feasibility decisions and study two strategies: parallel solving of multiple candidate spans, and incremental solving, which progressively restricts the label domain for the linear case only. On 24 sparse Harwell-Boeing graphs, with five scaling coefficients and against CPLEX-CP, CPLEX-MIP and Gurobi on identical hardware (1800-second limit), the incremental solver reportedly performs best on the linear variant, solving all 120 instances and proving 112 optimal spans versus 88 for CPLEX-CP, while the parallel solver performs best on the cyclic variant (107 optimal spans, best average rank 1.88); both clearly beat CPLEX-MIP and Gurobi, and the gap between the two SAT strategies is itself not statistically significant (p = 0.063). Under the no-hole constraint CPLEX-CP leads on solved instances and average rank while SAT keeps the best solution quality. Limitations include the use of only 24 sparse Harwell-Boeing graphs, a weak lower bound (k itself), a possible advantage from running eight parallel SAT processes, and minor numerical inconsistencies between aggregate and detailed tables; no code release is mentioned.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 2
● low 3
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- MSABL/MSCABL are new complementary minimum-span formulations of the (cyclic) antibandwidth problems whose decision versions are monotone in the largest label λ (Proposition 3).
- A unified SAT framework with parallel span search solves both variants, and an incremental solver for MSABL reuses one instance by adding domain-forbidding clauses (Appendix B shows incrementality fails for the cyclic case).
- On the base model the SAT approaches improve on state-of-the-art optimization-based approaches, discovering better spans and proving optimality for many more instances (e.g., 112 vs 88 optimal for MSABL; 107 vs 88 for MSCABL).
- Under the no-hole constraint the SAT approaches remain competitive with CPLEX-CP while significantly outperforming CPLEX-MIP and Gurobi, especially for MSCABL.
Strengths
Genuine problem-definition contribution with proofs
Section 3 and Appendix A prove the decision problem is monotone in the largest label λ (Proposition 3), and Appendix C carefully shows cyclic distance is not translation-invariant — a subtle correctness point justifying the {1,…,λ} domain and the necessity of (MAX-LABEL) for MSCABL (Section 3.4.2, with a worked 24-label/edge example).
Bidirectional parallel search is cleanly specified
Algorithm 1 maintains spaninvalid/spanvalid bounds, prunes with CancelGreater/CancelSmaller, and guarantees optimality when the BFS queue over [LB, UB] empties; Algorithm 2 exploits clause-only domain restriction (justified in Appendix B) so learned clauses carry across iterations.
Broad, statistically supported evaluation
Honest treatment of where SAT loses
Weaknesses
Weak lower bound and narrow benchmark
Parallel-vs-sequential confound
Internal count inconsistencies
No mechanism analysis of the no-hole reversal
Reproducibility is limited
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Peer Review: Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems (arXiv 2609.20091)
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the minimum span antibandwidth problem?
It is the mirror of the classical antibandwidth problem: instead of fixing the label set and maximizing the minimum distance between labels of adjacent vertices, you fix a required minimum distance k and ask for the smallest span λ−1 such that a labeling f : V → {1,…,λ} exists with every edge's endpoints at distance at least k. This paper (arXiv 2609.20091) introduces it as MSABL, plus the cyclic variant MSCABL where distances wrap around the label cycle.
How does the paper's SAT approach work?
Feasibility for a fixed largest label λ is monotone: if a labeling exists for λ, one exists for every larger λ. The framework therefore solves a sequence of SAT decision instances over candidate spans — either many spans in parallel with pruning of dominated candidates, or, for the linear (non-cyclic) case, a single incrementally built instance where forbidding the top labels only requires adding unit clauses, so learned clauses are reused.
How does it compare with CPLEX and Gurobi?
On 24 Harwell-Boeing sparse-matrix graphs with five distance scalings, both SAT strategies clearly beat CPLEX-MIP and Gurobi in optimal and best-known spans. Against CPLEX-CP the SAT approaches win on the base models (112 vs 88 proven optima for the linear variant; 107 vs 88 for the cyclic one), but under the added no-hole constraint CPLEX-CP is ahead on solved instances and average rank while SAT keeps the best solution quality.
Is code or data available?
The paper does not mention a code release. The instances are public (Harwell-Boeing Sparse Matrix Collection), solvers used are commercial (CaDiCaL 2.2.x, CPLEX 22.2, Gurobi 13.0.2), and encodings are described algorithmically, so an independent reimplementation is possible but nontrivial.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1-6 and C1 are described in text but not visually verifiable from the extraction
- Wilcoxon table column layout appears partially mangled in extraction, so test arithmetic could not be fully verified
- The no-hole SAT encoding is not shown in the extracted text; review of that model relies on reported results only
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.