Cycle decomposition (graph theory)

A cycle decomposition of a graph. The edges are partitioned into two sets (blue and orange) where each set forms a cycle.

For the notation used to express permutations, see Cycle decomposition (group theory).

In graph theory, a cycle decomposition is a decomposition (a partitioning of a graph's edges) into cycles. Every vertex in a graph that has a cycle decomposition must have even degree.

Cycle decomposition of K_n and K_n − I

Brian Alspach and Heather Gavlas established necessary and sufficient conditions for the existence of a decomposition of a complete graph of even order minus a 1-factor (a perfect matching) into even cycles and a complete graph of odd order into odd cycles. ^[1] Their proof relies on Cayley graphs, in particular, circulant graphs, and many of their decompositions come from the action of a permutation on a fixed subgraph.

They proved that for positive even integers ${\displaystyle m}$ and ${\displaystyle n}$ with ${\displaystyle 4\leq m\leq n}$, the graph ${\displaystyle K_{n}-I}$ (where ${\displaystyle I}$ is a 1-factor) can be decomposed into cycles of length ${\displaystyle m}$ if and only if the number of edges in ${\displaystyle K_{n}-I}$ is a multiple of ${\displaystyle m}$. Also, for positive odd integers ${\displaystyle m}$ and ${\displaystyle n}$ with ${\displaystyle 3\leq m\leq n}$, the graph ${\displaystyle K_{n}}$ can be decomposed into cycles of length ${\displaystyle m}$ if and only if the number of edges in ${\displaystyle K_{n}}$ is a multiple of ${\displaystyle m}$.

Computational complexity

The problem of decomposing an Eulerian graph into a minimum number of edge-disjoint cycles is NP-complete, as is the corresponding problem of decomposing into a maximum number of cycles. ^[2]

An Eulerian graph has a unique number of cycles in all of its cycle decompositions if and only if no two edge-disjoint cycles in the graph share more than two vertices. This property can be decided in polynomial time: there exists an algorithm running in time ${\displaystyle {\mathcal {O}}(n(n+m))}$ that determines whether the cycle number of a given Eulerian graph is unique, where ${\displaystyle n}$ is the number of vertices and ${\displaystyle m}$ is the number of edges. ^[2]

Algorithms

Several approaches have been developed for finding optimal cycle decompositions. For the Maximum Eulerian Cycle Decomposition problem, column generation techniques can be applied to an integer linear programming model with an exponential number of variables. ^[3]

Heuristic approaches include greedy algorithms that iteratively find minimum-sized cycles starting from random vertices, and ILP-based heuristics that solve restricted versions of the integer programming model using only a subset of possible cycles. These methods provide practical solutions for large instances where exact algorithms become computationally infeasible. ^[3]

Applications

Network analysis

Cycle decompositions can be applied to Markov processes on finite state spaces for analyzing directed networks. Given an ergodic Markov chain with transition matrix ${\displaystyle P}$ and stationary distribution ${\displaystyle \pi }$, the probability flow can be decomposed into cycles with positive weights. A stochastic decomposition approach yields a unique cycle decomposition where the weight ${\displaystyle w(\gamma )}$ of each cycle ${\displaystyle \gamma }$ equals the mean number of times a random walk passes through that cycle per time step. ^[4]

This approach can reveal modular structures in directed networks based on information flow rather than link density alone, providing insights that traditional methods may miss. ^[4]

Genome rearrangement

In comparative genomics, cycle decompositions of breakpoint graphs are used to compute genome rearrangement distances. The Maximum Breakpoint Graph Decomposition problem can be reduced to the Maximum Eulerian Cycle Decomposition problem in polynomial time. ^[3]

References

1. Alspach, Brian (2001). "Cycle Decompositions of ${\displaystyle K_{n}}$ and ${\displaystyle K_{n}{-}I}$ ". Journal of Combinatorial Theory, Series B. 81: 77–99. doi: 10.1006/jctb.2000.1996 .
2. Heinrich, Irene; Streicher, Manuel (2019). "Cycle decompositions and constructive characterizations". Electronic Journal of Graph Theory and Applications. 7 (2): 411–428. doi: 10.5614/ejgta.2019.7.2.15 .
3. Pinheiro, Pedro Olímpio; Alexandrino, Alexsandro Oliveira; Oliveira, Andre Rodrigues; de Souza, Cid Carvalho; Dias, Zanoni (2021). Algorithms for the Maximum Eulerian Cycle Decomposition Problem (PDF). LIII Simpósio Brasileiro de Pesquisa Operacional. João Pessoa, Brazil.
4. Djurdjevac Conrad, Nataša; Banisch, Ralf; Schütte, Christof (2015). "Modularity of directed networks: Cycle decomposition approach". Journal of Computational Dynamics. 2 (1): 1–24. arXiv: 1407.8039 . doi:10.3934/jcd.2015.2.1.

• Bondy, J.A.; Murty, U.S.R. (2008), "2.4 Decompositions and coverings", Graph Theory, Springer, ISBN   978-1-84628-969-9 .