# What is the best way to find an induced cycle basis of a graph?

My question is essentially what comes in the subject line: what is the best way to find an induced cycle basis of a graph (i.e., a cycle basis of the graph in which each cycle is an induced subgraph of the original graph)?

I can think of the following naive approach: Let $T$ be any spanning forest of $G$. Now repeat operation (a) until there are no two edges $e_1 = (u_1, v_1)$ and $e_2 = (u_2, v_2)$ so that $e_1, e_2 \in E(G) \setminus E(T)$ and the path in $T$ from $u_1$ to $v_1$ contains the path in $T$ from $u_2$ to $v_2$. Operation (a) adds edge $e_2$ to $T$ and removes one of the other edges in the path from $u_2$ to $v_2$ in $T$. Finally, construct the cycle basis of $G$ according to the resulting $T$.

Now, there are several things that I am interested in:

1. I believe the correctness of the algorithm above is intuitive but I might be wrong. Have I missed something?
2. Even if correct, the above algorithm is obviously very inefficient. Is there an efficient way to implement that idea?
3. Are there other efficient methods of finding an induced cycle basis of a graph?
4. Among different algorithms for doing that, are there any time/space trade-off that I should consider? I am willing to spend a little more on computation if it means smaller memory footprint.
5. The above algorithm only works for undirected graphs. What about directed ones?
• Minimal cycle cover is NP-hard...
– R B
Apr 20, 2015 at 14:26
• I don't have any weights and, if I understand correctly, the NP-hardness only comes when you have negative weights. That is, even with positive arbitrary weights, it's still in polynomial time. Apr 20, 2015 at 14:45