Finding cycles with a single differently colored edge in a colored graph

user_11171063 0
Viewed 52

Given a general undirected graph with a Red/Blue coloring on its edges, I'd like to be able to detect all cycles that contain exactly one blue edge in the graph. Is there a known algorithm for this?

I know how to detect cycles in a general graph using a DFS approach, and I can detect the single-blue-edge cycles by backtracking and counting the number of blue edges once I've found a cycle, but this solution would result in edge-quadratic time complexity, as far as I'm aware. Is there anything better?

graph algorithm
1 Answers

To detect whether a cycle with exactly one blue edge exists, find the connected components of the subgraph comprised of the red edges. For each blue edge, test whether its endpoints lie in the same red connected component. If they do, then there is such a cycle, formed by the blue edge and the path between its endpoints in the spanning forest of edges designated by DFS as tree edges.

Conversely, suppose that there is such a cycle. The red part of the cycle ensures that the endpoints of the blue edge belong to the same component.

user_21446690
Related