Given a graph $G(V,E)$, we consider that there is a perfect matching $M$ in $G$. The edges in $M$ is red and the edges not in $M$ is blue. So is there a polynomial time algorithm that can find a red-blue alternating cycle in $G$?
In the form of a bipartite graph, I think such an algorithm exists. Assuming the vertices in $G$ can be divided into $A$ and $B$, which there is no edge between vertices in A or B(Properties of bipartite graphs), the specific method is as follows：
- We convert the undirected graph G into a directed graph G'：If $x$ $\in$ A, $y$ $\in$B, and $(x,y)$ is in matching, then there is an edge $(x,y)$ from $A$ to $B$ in $G'$. And If $x$ $\in$ A, $y$ $\in$B, and $(x,y)$ is not in matching, then there is an edge $(y,x)$ from $B$ to $A$ in $G'$.
- After conversion, any path in G' is an alternating path. So we can use DFS to find alternating cycle.
In the form of a bipartite weighted graph, the algorithm is also useful. We just need to make some simple changes：after conversion, we can use Bellman-Ford algorithm to find alternating path/cycle.
The problem that confuses me is : Is there a similar polynomial time algorithm that can solve the problem of non-bipartite graphs(general graph)? Going further, Is there a similar polynomial time algorithm that can solve the problem of weighted non-bipartite graphs(weighted general graph)?