most recent 30 from http://mathoverflow.net 2013-05-25T00:58:41Z http://mathoverflow.net/feeds/question/31105 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/31105/enumerating-a-type-of-two-color-cycle Andrew 2010-07-08T19:54:59Z 2010-07-09T11:08:43Z

<p>I'd be grateful for some pointers to get me started on this.</p> <p>We have an undirected simple graph $G = (V, E)$. Each edge is colored either blue or red.</p> <p>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?</p> <p>Thanks in advance.</p>

http://mathoverflow.net/questions/31105/enumerating-a-type-of-two-color-cycle/31110#31110 supercooldave 2010-07-08T20:21:28Z 2010-07-08T20:46:48Z

<p>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. </p> <p>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.</p>