Characterizations and Complexity of Minimum Forward and Integer Cycle Bases
Abstract
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 must follow the given direction. Several open questions remain regarding the complexity of the minimum cycle basis problem, in particular the minimum-weight integral cycle basis problem, and the minimum-weight weakly and strictly fundamental forward cycle basis problems. In this paper, we address these open questions. First, we study the existence, structure, and computational complexity of minimum-weight forward cycle bases. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases. We further provide a characterization 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. 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 APX-hard via an L-reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights. Second, we introduce opt-in graphs, i.e., the family of graphs for which minimum cycle bases are integral for any weight function. We show that this family is minor-closed and hence, by the Robertson-Seymour theorem, is characterized by a finite set of forbidden minors, so that the opt-in recognition problem is solvable in polynomial time. Lastly, we present an algorithm to check whether a graph is opt-in, and if not, to identify which of its minors belong to the set of forbidden minors. Applying this algorithm, we show that the complete graph Kn is opt-in if and only if n ≤ 7.
Related
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- The exponent 1/4 in three complexity bounds: integer bases, continued fractions, and the (3/2)n steering word
- Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors
- Characterizations in terms of Generalized Inverses
- Characterizations of Toeplitz operators on the annulus
BibTeX
@misc{riccardi2026characterizations,
title = {{Characterizations and Complexity of Minimum Forward and Integer Cycle Bases}},
author = {Gabor Riccardi and Niels Lindner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02317},
eprint = {2609.02317},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02317},
}
RIS
TY - UNPB
TI - Characterizations and Complexity of Minimum Forward and Integer Cycle Bases
AU - Gabor Riccardi
AU - Niels Lindner
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02317
UR - https://arxiv.org/abs/2609.02317
AB - 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 must follow the given direction. Several open questions remain regarding the complexity of the minimum cycle basis problem, in particular the minimum-weight integral cycle basis problem, and the minimum-weight weakly and strictly fundamental forward cycle basis problems. In this paper, we address these open questions. First, we study the existence, structure, and computational complexity of minimum-weight forward cycle bases. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases. We further provide a characterization 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. 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 APX-hard via an L-reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights. Second, we introduce opt-in graphs, i.e., the family of graphs for which minimum cycle bases are integral for any weight function. We show that this family is minor-closed and hence, by the Robertson-Seymour theorem, is characterized by a finite set of forbidden minors, so that the opt-in recognition problem is solvable in polynomial time. Lastly, we present an algorithm to check whether a graph is opt-in, and if not, to identify which of its minors belong to the set of forbidden minors. Applying this algorithm, we show that the complete graph K_n is opt-in if and only if n ≤ 7.
ER -