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:
- I believe the correctness of the algorithm above is intuitive but I might be wrong. Have I missed something?
- Even if correct, the above algorithm is obviously very inefficient. Is there an efficient way to implement that idea?
- Are there other efficient methods of finding an induced cycle basis of a graph?
- 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.
- The above algorithm only works for undirected graphs. What about directed ones?