On The Minimum-Weight Forward (Weakly) Fundamental Cycle Basis Problem in Directed Graphs
accepted for publication
- The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs have to follow the given direction. We study the existence, structure, and computational complexity of minimum-weight forward cycle bases in directed graphs. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases, showing that this holds if and only if every block is either strongly connected or a single arc. We further provide an easily verifiable characterization of when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique and computable in polynomial time, and nonexistence can likewise be certified efficiently. Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is NP-hard via a polynomial-time reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights.
| Author: | Gabor Riccardi, Niels LindnerORCiD |
|---|---|
| Document Type: | In Proceedings |
| Parent Title (English): | International Network Optimization Conference 2026 (INOC 2026) |
| Year of first publication: | 2026 |

