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

Question

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?

Answer 1

Did you try searching Google scholar for "induced cycle basis"? There is not much, but the following reference seems to be relevant. It characterizes the graphs for which the set of all induced cycles forms a cycle basis, which I think is more restrictive than your question (you are allowing a proper subset of these cycles in your basis).

McKee, Terry A. (2000), Induced cycle structure and outerplanarity, Discrete Math. 223 (1–3): 387–392.

In any case I believe the following approach will work for your problem. Separately, within each biconnected component, do the following steps:

1. Start with an induced cycle
2. Repeatedly find an "ear" in an ear decomposition: a simple path that starts and ends in previously chosen cycles, and with each interior vertex not belonging to previous cycles. Choose the ear to be as short as possible (breaking ties by the distance between the path endpoints among edges in previous cycles) so that there is no shortcut edge from an interior vertex back to the set of previous cycles.
3. Connect the endpoints of the ear by a shortest path through the edges used in previous cycles, and add the resulting cycle to the decomposition.

By using shortest paths to choose each ear and to complete each ear to a cycle, the resulting cycles are all necessarily induced. They form a weakly fundamental set of cycles (each uses an edge not part of previous cycles) so they are independent, and they have the correct number of cycles to span the cycle space of the graph, so they are a cycle basis. But unlike your approach (?) they are not a fundamental cycle basis: they do not come from a spanning tree of the graph.