Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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