Enumerating a type of two-color cycle

Question

I'd be grateful for some pointers to get me started on this.

We have an undirected simple graph $G = (V, E)$. Each edge is colored either blue or red.

I am interested in simple cycles (no repeated vertices or edges other than the starting and ending vertices) that have exactly one blue edge (and the rest of the edges red). Specifically, I want to enumerate these types of cycles in increasing order of length. Do there exist efficient algorithms for this task, or is there a simple reduction to a known problem? What if we restrict $G$ to be planar?

Thanks in advance.

Answer 1

If your graph is $G=(V,E)$ and $B\subseteq E$ are the blue edges, then you can run an appropriate cycle enumeration algorithm on $G-(B\setminus\{ b_i \})$ for each $b_i\in B$. This ensures that at most one blue edge occurs in the graph. Perhaps the selected algorithm can be adapted to start with the edge $b_i$, ensuring that only graphs with exactly one blue edge are enumerated.

Google reveals many such algorithms. I'm not sure which one suits your needs. No efficient algorithms exist, as along the way you would find Hamiltonian paths, which is an NP-complete problem.