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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.