{"id":"arxiv/2609.02317","url":"https://arxiv.org/abs/2609.02317","tags":["math.OC","cs.DM"],"score":0,"title":"Characterizations and Complexity of Minimum Forward and Integer Cycle Bases","domain":"math.OC","source":"arxiv","authors":["Gabor Riccardi","Niels Lindner"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-02","reactions":{}}