I know how to find odd length cycles(a bipartite graph cannot have odd cycles) but I cannot manage to make an algorithm when considering even length cycles.
3
-
$\begingroup$ Should the cycle be vertex-disjoint or edge-disjoint? $\endgroup$– GassaJul 4, 2018 at 11:31
-
$\begingroup$ Is your graph bipartite? $\endgroup$– Yuval FilmusJul 4, 2018 at 15:47
-
$\begingroup$ Do you want a simple cycle? Can the cycle repeat vertices or not? $\endgroup$– D.W. ♦Nov 20, 2020 at 19:26
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Construct a new graph $G'$ with the same set of vertices, and with an edge $(u,v)$ iff there is a path of length 2 from $u$ to $v$ in the original graph. Then, check whether $G'$ has any cycles of any length. A cycle in $G'$ corresponds to an even-length cycle in the original graph, and vice versa, so this provides a correct algorithm. The running time is $O(|V||E|)$.
-
$\begingroup$ This doesn't work if the cycle needs to be simple (as it is usually the case). If $G$ is a triangle then $G' = G$, yet $G$ contains no even simple cycles. If the cycles do not need to be simple then the problem is equivalent to deciding whether there is a cycle $C$ (of any length) in $G$. If $C$ is even we are done, otherwise $C \circ C$ will be an even cycle. $\endgroup$– StevenNov 20, 2020 at 12:44
-
$\begingroup$
$\endgroup$
2
if you have no limits to complexity, try this:
For each node v in the graph:
1)Apply the bfs from v
2)Take the visit three and for each leaves u check to see if there is an edge (u,v) in the graphs, if this is true then there is a cycle that hold v and you can count it as an even lenght cycle if and only if u has odd depth
Repeat for each node in the graph and get the number of even lenght cycle whit a complexity of O(|V||E|) where V is the set of nodes and E is the set of edge in the graphs.
Hope this help!
-
$\begingroup$ Sorry but there is a mistake in my answer, considers u as any node in the tree having depth greater than 1, now i think it can work. $\endgroup$– lorenzoJul 12, 2018 at 17:28
-
1$\begingroup$ Please don't use answers to try to add addendums. Instead, revise/edit your existing answer using the 'edit' / 'suggest an improvement' link under the answer. $\endgroup$– D.W. ♦Jul 12, 2018 at 19:12
$\begingroup$
$\endgroup$
Do a BFS from any node, say r, construct the BFS tree.
For each edge ({u, v}) in the graph that isn't a tree edge, check whether u.level + v.level is even or odd.
If it's odd then the graph has an even cycle.
If it's even, then the graph has an odd cycle.
Proof:
BFS yields the shortest path between nodes r,u and r,v.
The levels of the BFS tree are equal to the distances from r.
If there is an edge between u and v that isn't a tree edge, then (r->v, v->u, u->r) forms a cycle of the length = 1 + length(r->v) + length(r->u)
We need to check whether this length is even or not.
Complexity:
O(V + E) + O(E) = O(V + E)
