Cycle basis

The symmetric difference of two cycles is an Eulerian subgraph

In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles.

A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree. Alternatively, if the edges of the graph have positive weights, the minimum weight cycle basis may be constructed in polynomial time.

In planar graphs, the set of bounded cycles of an embedding of the graph forms a cycle basis. The minimum weight cycle basis of a planar graph corresponds to the Gomory–Hu tree of the dual graph.

Definitions

A spanning subgraph of a given graph G has the same set of vertices as G itself but, possibly, fewer edges. A graph G, or one of its subgraphs, is said to be Eulerian if each of its vertices has even degree (its number of incident edges). Every simple cycle in a graph is an Eulerian subgraph, but there may be others. The cycle space of a graph is the collection of its Eulerian subgraphs. It forms a vector space over the two-element finite field. The vector addition operation is the symmetric difference of two or more subgraphs, which forms another subgraph consisting of the edges that appear an odd number of times in the arguments to the symmetric difference operation. ^[1]

A cycle basis is a basis of this vector space in which each basis vector represents a simple cycle. It consists of a set of cycles that can be combined, using symmetric differences, to form every Eulerian subgraph, and that is minimal with this property. Every cycle basis of a given graph has the same number of cycles, which equals the dimension of its cycle space. This number is called the circuit rank of the graph, and it equals ${\displaystyle m-n+c}$ where ${\displaystyle m}$ is the number of edges in the graph, ${\displaystyle n}$ is the number of vertices, and ${\displaystyle c}$ is the number of connected components. ^[2]

Special cycle bases

Several special types of cycle bases have been studied, including the fundamental cycle bases, weakly fundamental cycle bases, sparse (or 2-) cycle bases, and integral cycle bases. ^[3]

Induced cycles

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.

Fundamental cycles

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]

Weakly fundamental cycles

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]

Face cycles

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]}

Integral bases

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]

Minimum weight

If the edges of a graph are given real number weights, the weight of a subgraph may be computed as the sum of the weights of its edges. The minimum weight basis of the cycle space is necessarily a cycle basis: by Veblen's theorem, ^[11] every Eulerian subgraph that is not itself a simple cycle can be decomposed into multiple simple cycles, which necessarily have smaller weight.

By standard properties of bases in vector spaces and matroids, the minimum weight cycle basis not only minimizes the sum of the weights of its cycles, it also minimizes any other monotonic combination of the cycle weights. For instance, it is the cycle basis that minimizes the weight of its longest cycle. ^[12]

Polynomial time algorithms

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]

NP-hardness

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.

In planar graphs

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]

Applications

Cycle bases have been used for solving periodic scheduling problems, such as the problem of determining the schedule for a public transportation system. In this application, the cycles of a cycle basis correspond to variables in an integer program for solving the problem. ^[23]

In the theory of structural rigidity and kinematics, cycle bases are used to guide the process of setting up a system of non-redundant equations that can be solved to predict the rigidity or motion of a structure. In this application, minimum or near-minimum weight cycle bases lead to simpler systems of equations. ^[24]

In distributed computing, cycle bases have been used to analyze the number of steps needed for an algorithm to stabilize. ^[25]

In bioinformatics, cycle bases have been used to determine haplotype information from genome sequence data. ^[26] Cycle bases have also been used to analyze the tertiary structure of RNA. ^[27]

The minimum weight cycle basis of a nearest neighbor graph of points sampled from a three-dimensional surface can be used to obtain a reconstruction of the surface. ^[28]

In cheminformatics, the minimal cycle basis of a molecular graph is referred to as the smallest set of smallest rings. ^{[29] [30] [31]}

References

1. Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
2. Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN   9781584885054 .
3. Liebchen, Christian; Rizzi, Romeo (2007), "Classes of cycle bases", Discrete Applied Mathematics, 155 (3): 337–355, doi: 10.1016/j.dam.2006.06.007 , MR   2303157 .
4. Diestel (2012), pp. 32, 65.
5. Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR   0158387 . See in particular Theorem 2.5.
6. Cribb, D. W.; Ringeisen, R. D.; Shier, D. R. (1981), "On cycle bases of a graph", Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981), Congressus Numerantium, vol. 32, pp. 221–229, MR   0681883 .
7. Rizzi, Romeo (2009), "Minimum weakly fundamental cycle bases are hard to find", Algorithmica , 53 (3): 402–424, doi:10.1007/s00453-007-9112-8, MR   2482112, S2CID   12675654 .
8. Hartvigsen, David; Zemel, Eitan (1989), "Is every cycle basis fundamental?", Journal of Graph Theory , 13 (1): 117–137, doi:10.1002/jgt.3190130115, MR   0982873 .
9. Diestel (2012), pp. 105–106.
10. Mac Lane, S. (1937), "A combinatorial condition for planar graphs" (PDF), Fundamenta Mathematicae , 28: 22–32, doi: 10.4064/fm-28-1-22-32 .
11. Veblen, Oswald (1912), "An application of modular equations in analysis situs", Annals of Mathematics , Second Series, 14 (1): 86–94, doi:10.2307/1967604, JSTOR   1967604 .
12. Chickering, David M.; Geiger, Dan; Heckerman, David (1995), "On finding a cycle basis with a shortest maximal cycle", Information Processing Letters, 54 (1): 55–58, CiteSeerX   10.1.1.650.8218 , doi:10.1016/0020-0190(94)00231-M, MR   1332422 .
13. Horton, J. D. (1987), "A polynomial-time algorithm to find the shortest cycle basis of a graph", SIAM Journal on Computing , 16 (2): 358–366, doi:10.1137/0216026 .
14. Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2004), "Minimum cycle bases for network graphs", Algorithmica, 40 (1): 51–62, doi:10.1007/s00453-004-1098-x, MR   2071255, S2CID   9386078 .
15. Mehlhorn, Kurt; Michail, Dimitrios (2006), "Implementing minimum cycle basis algorithms", ACM Journal of Experimental Algorithmics, 11: 2.5, CiteSeerX   10.1.1.60.1087 , doi:10.1145/1187436.1216582, S2CID   6198296 .
16. Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (2008), "An ${\displaystyle {\tilde {O}}(m^{2}n)}$ algorithm for minimum cycle basis of graphs", Algorithmica , 52 (3): 333–349, doi: 10.1007/s00453-007-9064-z , MR   2452919 .
17. Kavitha, Telikepalli; Liebchen, Christian; Mehlhorn, Kurt; Michail, Dimitrios; Rizzi, Romeo; Ueckerdt, Torsten; Zweig, Katharina A. (2009), "Cycle bases in graphs: Characterization, algorithms, complexity, and applications", Computer Science Review, 3 (4): 199–243, doi:10.1016/j.cosrev.2009.08.001 .
18. Amaldi, Edoardo; Iuliano, Claudio; Rizzi, Romeo (2010), "Efficient deterministic algorithms for finding a minimum cycle basis in undirected graphs", Integer Programming and Combinatorial Optimization: 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6080, Springer, pp. 397–410, Bibcode:2010LNCS.6080..397A, doi:10.1007/978-3-642-13036-6_30, ISBN   978-3-642-13035-9, MR   2661113 .
19. Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (1982), "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software , 8 (1): 26–42, doi: 10.1145/355984.355988 , MR   0661120, S2CID   2260051 .
20. Galbiati, Giulia; Amaldi, Edoardo (2004), "On the approximability of the minimum fundamental cycle basis problem", Approximation and Online Algorithms: First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2909, Berlin: Springer, pp. 151–164, doi:10.1007/978-3-540-24592-6_12, ISBN   978-3-540-21079-5, MR   2089904 .
21. Hartvigsen, David; Mardon, Russell (1994), "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs", SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi:10.1137/S0895480190177042, MR   1285579 .
22. Borradaile, Glencora; Eppstein, David; Nayyeri, Amir; Wulff-Nilsen, Christian (2016), "All-pairs minimum cuts in near-linear time for surface-embedded graphs", Proc. 32nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Schloss Dagstuhl, pp. 22:1–22:16, arXiv: 1411.7055 , doi: 10.4230/LIPIcs.SoCG.2016.22 , S2CID   215762172 .
23. Liebchen, Christian (2007), "Periodic Timetable Optimization in Public Transport", Operations Research Proceedings 2006, vol. 2006, pp. 29–36, doi:10.1007/978-3-540-69995-8_5, ISBN   978-3-540-69994-1 .
24. Cassell, A. C.; De Henderson, J. C.; Kaveh, A. (1974), "Cycle bases for the flexibility analysis of structures", International Journal for Numerical Methods in Engineering, 8 (3): 521–528, Bibcode:1974IJNME...8..521C, doi:10.1002/nme.1620080308 .
25. Boulinier, Christian; Petit, Franck; Villain, Vincent (2004), "When graph theory helps self-stabilization", Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (PODC '04), New York, NY, USA: ACM, pp. 150–159, CiteSeerX   10.1.1.79.2190 , doi:10.1145/1011767.1011790, ISBN   978-1581138023, S2CID   14936510 .
26. Aguiar, Derek; Istrail, Sorin (2012), "HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data", Journal of Computational Biology, 19 (6): 577–590, doi:10.1089/cmb.2012.0084, PMC   3375639 , PMID   22697235 .
27. Lemieux, Sébastien; Major, François (2006), "Automated extraction and classification of RNA tertiary structure cyclic motifs", Nucleic Acids Research, 34 (8): 2340–2346, doi:10.1093/nar/gkl120, PMC   1458283 , PMID   16679452 .
28. Gotsman, Craig; Kaligosi, Kanela; Mehlhorn, Kurt; Michail, Dimitrios; Pyrga, Evangelia (2007), "Cycle bases of graphs and sampled manifolds", Computer Aided Geometric Design, 24 (8–9): 464–480, CiteSeerX   10.1.1.298.9661 , doi:10.1016/j.cagd.2006.07.001, MR   2359763 .
29. May, John W.; Steinbeck, Christoph (2014), "Efficient ring perception for the Chemistry Development Kit", Journal of Cheminformatics , 6 (3): 3, doi: 10.1186/1758-2946-6-3 , PMC   3922685 , PMID   24479757
30. Downs, G.M.; Gillet, V.J.; Holliday, J.D.; Lynch, M.F. (1989), "A review of ring perception algorithms for chemical graphs", J. Chem. Inf. Comput. Sci. , 29 (3): 172–187, doi:10.1021/ci00063a007
31. Zamora, A. (1979), "An algorithm for finding the smallest set of smallest rings", J. Chem. Inf. Comput. Sci. , 16 (1): 40–43, doi:10.1021/ci60005a013