1988/01/01 by S. Rao Kosaraju, Gregory F. Sullivan · 60 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Formal Methods in Verification #Graph Labeling and Dimension Problems #Computer science #Polynomial #Time complexity #Theoretical computer science #Mathematics #Algorithm
paper · doi:10.1145/62212.62251
openalex publication_date 1988/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Consider a digraph which has labels on its edges which are k-dimensional vectors. In this paper we show it is possible in polynomial time to determine if such a digraph contains a zero cycle, i.e., a cycle whose edge labels sum to the zero vector component-wise. This solves the open problem of finding cycles in dynamic graphs which was posed by Iwano and Steiglitz. Our solution has a time complexity of O(|V| log(|V|)Z) where Z is the complexity of a linear programming problem. For the important cases of two and three dimensions we present O(Z) time algorithms. The linear programming problems we solve have at most 2|E| variables and O(|E| + |V| + k) constraints.