Find all the smallest cycles in a graph

[brandimarte]

Having a "list" of all smallest cycles would allow for an unambiguous search of Kekule structures.

[brandimarte]

Implement the algorithm from Keith Paton: "An algorithm for finding a fundamental set of cycles of a graph", Communications of the ACM (1969).

[brandimarte]

First attempt on 87777f6, but the implemented algorithms returns a basis set which is not necessarily the one given by the smallest cycles.

[brandimarte]

Just realized the basisCyclesPaton is buggy when running it for the nonacene example.

[brandimarte]

The problem of finding an optimal spanning tree T_{mim} in a graph, such that the length of the corresponding fundamental cycle set is minimal, is proven to be a NP-complete problem by N. Deo et al (ACM Trans. Math. Software 8, 1982). Still, since our problem is less general due to the constrains given by the carbon bonds, it might be possible to come with an efficient solution.

[brandimarte]

Although the problem of finding T_{min} (last comment above) has being proved to be NP-complete (and more recently that it is also APX-hard, G. Galbiati et al, Discrete Appl. Math. 159, 2011), apparently the problem of finding the shortest cycle basis of a graph can be solved in polynomial time (J. Horton, SIAM J. Comput. 16, 1987; T. Kavitha et al, Algorithmica 52, 2008). I'll check those latter proposals, which I guess should not rely on finding a minimum spanning tree.