Cycle basis

Every graph has a cycle basis in which every cycle is an induced cycle. In a 3-vertex-connected graph, there always exists a basis consisting of peripheral cycles, cycles whose removal does not separate the remaining graph.[4][5] In any graph other than one formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.

If ${\displaystyle T}$ is a spanning tree or spanning forest of a given graph ${\displaystyle G}$, and ${\displaystyle e}$ is an edge that does not belong to ${\displaystyle T}$, then the fundamental cycle ${\displaystyle C_{e}}$ defined by ${\displaystyle e}$ is the simple cycle consisting of ${\displaystyle e}$ together with the path in ${\displaystyle T}$ connecting the endpoints of ${\displaystyle e}$. There are exactly ${\displaystyle m-n+c}$ fundamental cycles, one for each edge that does not belong to ${\displaystyle T}$. Each of them is linearly independent from the remaining cycles, because it includes an edge ${\displaystyle e}$ that is not present in any other fundamental cycle. Therefore, the fundamental cycles form a basis for the cycle space.[1][2] A cycle basis constructed in this way is called a fundamental cycle basis or strongly fundamental cycle basis.[3]

It is also possible to characterize fundamental cycle bases without specifying the tree for which they are fundamental. There exists a tree for which a given cycle basis is fundamental if and only if each cycle contains an edge that is not included in any other basis cycle, that is, each cycle is independent of others. It follows that a collection of cycles is a fundamental cycle basis of ${\displaystyle G}$ if and only if it has the independence property and has the correct number of cycles to be a basis of ${\displaystyle G}$.[6]

A cycle basis is called weakly fundamental if its cycles can be placed into a linear ordering such that each cycle includes at least one edge that is not included in any earlier cycle. A fundamental cycle basis is automatically weakly fundamental (for any edge ordering).[3][7] If every cycle basis of a graph is weakly fundamental, the same is true for every minor of the graph. Based on this property, the class of graphs (and multigraphs) for which every cycle basis is weakly fundamental can be characterized by five forbidden minors: the graph of the square pyramid, the multigraph formed by doubling all edges of a four-vertex cycle, two multigraphs formed by doubling two edges of a tetrahedron, and the multigraph formed by tripling the edges of a triangle.[8]

If a connected finite planar graph is embedded into the plane, each face of the embedding is bounded by a cycle of edges. One face is necessarily unbounded (it includes points arbitrarily far from the vertices of the graph) and the remaining faces are bounded. By Euler's formula for planar graphs, there are exactly ${\displaystyle m-n+1}$ bounded faces. The symmetric difference of any set of face cycles is the boundary of the corresponding set of faces, and different sets of bounded faces have different boundaries, so it is not possible to represent the same set as a symmetric difference of face cycles in more than one way; this means that the set of face cycles is linearly independent. As a linearly independent set of enough cycles, it necessarily forms a cycle basis.[9] It is always a weakly fundamental cycle basis, and is fundamental if and only if the embedding of the graph is outerplanar.

For graphs properly embedded onto other surfaces so that all faces of the embedding are topological disks, it is not in general true that there exists a cycle basis using only face cycles. The face cycles of these embeddings generate a proper subset of all Eulerian subgraphs. The homology group ${\displaystyle H_{2}(S,\mathbb {Z} _{2})}$ of the given surface ${\displaystyle S}$ characterizes the Eulerian subgraphs that cannot be represented as the boundary of a set of faces. Mac Lane's planarity criterion uses this idea to characterize the planar graphs in terms of the cycle bases: a finite undirected graph is planar if and only if it has a sparse cycle basis or 2-basis,[3] a basis in which each edge of the graph participates in at most two basis cycles. In a planar graph, the cycle basis formed by the set of bounded faces is necessarily sparse, and conversely, a sparse cycle basis of any graph necessarily forms the set of bounded faces of a planar embedding of its graph.[9][10]

The cycle space of a graph may be interpreted using the theory of homology as the homology group ${\displaystyle H_{1}(G,\mathbb {Z} _{2})}$ of a simplicial complex with a point for each vertex of the graph and a line segment for each edge of the graph. This construction may be generalized to the homology group ${\displaystyle H_{1}(G,R)}$ over an arbitrary ring ${\displaystyle R}$. An important special case is the ring of integers, for which the homology group ${\displaystyle H_{1}(G,\mathbb {Z} )}$ is a free abelian group, a subgroup of the free abelian group generated by the edges of the graph. Less abstractly, this group can be constructed by assigning an arbitrary orientation to the edges of the given graph; then the elements of ${\displaystyle H_{1}(G,\mathbb {Z} )}$ are labelings of the edges of the graph by integers with the property that, at each vertex, the sum of the incoming edge labels equals the sum of the outgoing edge labels. The group operation is addition of these vectors of labels. An integral cycle basis is a set of simple cycles that generates this group.[3]

In any vector space, and more generally in any matroid, a minimum weight basis may be found by a greedy algorithm that considers potential basis elements one at a time, in sorted order by their weights, and that includes an element in the basis when it is linearly independent of the previously chosen basis elements. Testing for linear independence can be done by Gaussian elimination. However, an undirected graph may have an exponentially large set of simple cycles, so it would be computationally infeasible to generate and test all such cycles.

Horton (1987) provided the first polynomial time algorithm for finding a minimum weight basis, in graphs for which every edge weight is positive. His algorithm uses this generate-and-test approach, but restricts the generated cycles to a small set of ${\displaystyle O(mn)}$ cycles, called Horton cycles. A Horton cycle is a fundamental cycle of a shortest path tree of the given graph. There are at most n different shortest path trees (one for each starting vertex) and each has fewer than m fundamental cycles, giving the bound on the total number of Horton cycles. As Horton showed, every cycle in the minimum weight cycle basis is a Horton cycle.[13] Using Dijkstra's algorithm to find each shortest path tree and then using Gaussian elimination to perform the testing steps of the greedy basis algorithm leads to a polynomial time algorithm for the minimum weight cycle basis. Subsequent researchers have developed improved algorithms for this problem,[14][15][16][17] reducing the worst-case time complexity for finding a minimum weight cycle basis in a graph with ${\displaystyle m}$ edges and ${\displaystyle n}$ vertices to ${\displaystyle O(m^{2}n/\log n)}$.[18]

Finding the fundamental basis with the minimum possible weight is closely related to the problem of finding a spanning tree that minimizes the average of the pairwise distances; both are NP-hard.[19] Finding a minimum weight weakly fundamental basis is also NP-hard,[7] and approximating it is MAXSNP-hard.[20] If negative weights and negatively weighted cycles are allowed, then finding a minimum cycle basis (without restriction) is also NP-hard, as it can be used to find a Hamiltonian cycle: if a graph is Hamiltonian, and all edges are given weight −1, then a minimum weight cycle basis necessarily includes at least one Hamiltonian cycle.

The minimum weight cycle basis for a planar graph is not necessarily the same as the basis formed by its bounded faces: it can include cycles that are not faces, and some faces may not be included as cycles in the minimum weight cycle basis. However, there exists a minimum weight cycle basis in which no two cycles cross each other: for every two cycles in the basis, either the cycles enclose disjoint subsets of the bounded faces, or one of the two cycles encloses the other one. This set of cycles corresponds, in the dual graph of the given planar graph, to a set of cuts that form a Gomory–Hu tree of the dual graph, the minimum weight basis of its cut space.[21] Based on this duality, an implicit representation of the minimum weight cycle basis in a planar graph can be constructed in time ${\displaystyle O(n\log ^{3}n)}$.[22]