Given a weighted graph G=(V,E,w), where w:E→R_≥ 0, find an integral cycle basis B minimizing its total weight ∑_C∈B∑_e∈ Cw(e). Here an integral cycle basis is a basis of the integer cycle lattice of G, equivalently, a cycle basis whose cycle vectors form a Z-basis of that lattice. Determine the computational complexity of this optimization problem and characterize the graphs for which minimum cycle bases are integral for every edge-weight function.

Minimum forward and integral cycle basis problems

The problem family concerns minimum cycle bases under directed, integral, forward, weakly fundamental, and fundamental restrictions. The latest work claims several structural characterizations and complexity classifications, while explicitly stopping short of a complete classification of every variant.

Known results

Minimum-weight weakly fundamental bases are NP-hard to find, with MAXSNP-hard approximation in the cited literature.
Minimum-weight fundamental bases are NP-hard; unrestricted minimum cycle-basis minimization has polynomial algorithms such as Horton's algorithm.
Integral bases are characterized by cycle matrices with determinant $\pm 1$ ; weakly fundamental and strictly fundamental bases have corresponding triangular or identity-matrix characterizations.

September 2, 2026 development

The reported work gives criteria for weakly fundamental and fundamental forward bases, a polynomial algorithm when minimum-weight fundamental bases exist, APX-hardness for weakly fundamental bases, and a minor-closed characterization of opt-in graphs, including $K_n$ opt-in exactly when $n \le 7$ . These are substantial claimed advances, but the supplied evidence is an abstract and does not verify a complete resolution of all tracked problems.

Current status (as of September 2026): Several structural and complexity questions have claimed results, but the full collection of minimum forward and integral cycle-basis problems remains only partially classified and the new claims are unverified.

Minimum forward and integral cycle basis problems

Primary source

Additional references

Progress summary

Solutions 0