This is my first post. I've a big doubt regarding Graphs, I'm working on a program to generate them using different efficient algorithms, starting from "Horton" (1978, 1st polynomial time approach).
Horton states that a greedy approach can generate the Minimal Cycle Basis:
1. For each vertex, generate a Shortest Path Tree based on that vertex and analyze it against all edges to search for cycles. Thus creating a Cycle Space of at most mxn cycles (m:n. of edges; n: n. of vertices).
2. Sort all found cycles by weight in non-increasing order.
3. Start adding them one-by-one into a set (MCB), checking if the "candidate" cycle is linearly independent with the set (discarding it if doesn't). This, until MCB has "v" cycles (v = #vertices - #nodes + 1).
According to Horton, the resulting Cycle Space ( should contain a MCB (Minimum Cycle Basis). I've found this is true for most cases, but I found a particular one for which the resulting MCB is not consistent (i.e. The Symmetric Difference of the cycles in the MCB do not generate the original graph).
MCB NOT consistent (MCB generated using Horton's algorithm -- the edge (3,5) is not included in any cycle, I guess because its weight is "avoided" by all Shortest Paths)
MCB consistent (Potential MCB that will cover all edges)
Can someone explain to me if I got the procedure wrong or is it the graph that doesn't admit a MCB?
Thank you in advance!
First of all, after Step 1, there must definitely be cycles containing edge $35$. For every pair of vertex $u$ and edge $vw$, the cycle we create consists of the shortest path from $u$ to $v$, the edge $vw$, and the shortest path from $w$ to $u$, assuming that the resulting cycle is simple (the two shortest paths have no vertex in common except for $u$).
In particular, for every edge $vw$, there will be at least one cycle in the Horton set which contains that edge: the shortest cycle containing $vw$. (Just take any other vertex on that cycle as $u$: if the shortest paths $u$ to $v$ and $u$ to $w$ had another vertex $u'$ in common, the cycle starting and stopping at $u'$ would be shorter.)
In your example graph:
For edge $35$, if we take $u = 1$ and $vw = 35$, then the cycle we create consists of the edges $(14, 43, 35, 51)$.
Second, at least one cycle containing edge $35$ (or any other given edge) must survive Step 3: the first cycle we consider that includes edge $35$ must be linearly independent from the others.
In this example, after Step 1, I get
We include the first three cycles, which are linearly independent, exclude the fourth cycle (since it's in the span of the first two cycles), include the fifth cycle, and exclude the sixth cycle (since it's in the span of the first and fifth).
Regarding the linear independence of cycles: you need to be careful here, since just using straightforward incidence vectors will not work. You have two options: