# DFS - Checking if a graph is bipartite

I wonder what will be the complexity of this algorithm of mine and why, used to check whether a graph (given in the form of neighbors list) is bipartite or not using DFS.

The algorithm works as following:

We will use edges classification, and look for back edges.

If we found one, it means there is a circle in the graph.

We will now check whether the cycle is odd cycle or not, using the the pi attribute added to each vertex, counting the number of edges participating in the cycle.

If the cycle is an odd one, return false. Else, continue the process.

Initially I thought the complexity will be O(|V| + |E|) as |V| stands for the number of vertices in the graph, and |E| stands for the number of edges in the graph, but I am afraid it might take O(|V| + |E|^2), and I wonder which option is correct and why (it may not be any of the above as well). Amortized or expected run times may also be different, and I wonder how can I check them as well. Please help me figure!

pseudo code

DFS(G=(V,E))
// π[u] – Parent of u in the DFS tree
1 for each vertex u ∈ V {
2 color[u] ← WHITE
3 π[u]← NULL
4 time ← 0}
5 for each vertex u ∈ V {
6 if color[u] = WHITE
7 DFS-VISIT(u)}


and for the DFS-Visit:

DFS-Visit(u)
// white vertex u has just been discovered
1 color[u] ← GRAY
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] { // going over all edges {u, v}
5 if color[v] = WHITE {
6 π[v] ← u
7 DFS-VISIT(v) }
8 else if color[v] = GRAY // there is a cycle in the graph
9 CheckIfOddCycle (u, v);
10 color[u] ← BLACK
// change the color of vertex u to black as we finished going over it
11 f[u] ← time ← time+1


and as for deciding what type of cycle is it:

CheckIfOddCycle(u, v)
1 int count  ← 1;
2 vertex p = u;
3 while (p! = v) {
4 p ← π[p]
5 count++ }
6 if count is an odd number {
7 S.O.P (“The graph is not bipartite!”);
8 stop the search, as the result is now concluded!


Thanks!

• Could you explain why you think it might take $O(|V| + |E|^2)$? What is "pi" attribute? How do you decide if a cycle odd or even? – fade2black Aug 6 '17 at 16:32
• @fade2black Of course! well, given a vertex v, v.pi is an attribute of a reference to the parent of the vertex v, u, in the DFS tree. I decide whether a cycle is off by counting the number of edges in the cycle. Each time I go back using the pi attribute I add 1 to my count of the number of edges in the cycle found. If the number is odd, then the cycle is odd. As for the explanation of why I am afraid it might take O(|V|+|E|^2), I am afraid that in the worst case I might go over all the edges in the graph each time I find a circle, or maybe O(|V|*|E|). I am really confused about the worst case – Ron.K Aug 6 '17 at 16:42
• While doing DFS/BFS you mark visited nodes and when you find a back-edge you can check if a cycle is even or odd using a single if-statement in $O(1)$. This algorithm is well known and related to graph coloring (just don't want to give a spoiler). Since it is DFS/BFS its time complexity is $O(V+E)$. – fade2black Aug 6 '17 at 16:49
• @fade2black Indeed! But I wonder how can it be done using a single if statement, and what is the complexity in the worst case of the algorithm I purposed. I mean, I know there are ways to check if a graph is bipartite in O(|V|+|E|) time using BFS and vertex coloring, but I wonder if the one I suggested is one as well, and how can I decide it. – Ron.K Aug 6 '17 at 16:53
• I cannot say anything since it is not clear HOW you count the length of cycles using pi attribute. Do you increment a counter and pass it every time you call DFS? For example $dfs(counter + 1)$? – fade2black Aug 6 '17 at 17:42

While your algorithm is visiting a node $v$, if it detects a back edge $(v,u)$ then it backtracks until it reaches $u$, using the parent information stored in pi, counts the number of edges, and then decides if it is bipartite or not. In this case your edges and nodes are visited at most two times (once when you move forward and once when you backtrack) which is still linear, i.e. is $O(V + E)$.
As for average and amortized case analysis I have never done such a thorough analysis of dfs but my guess is both are $O(V+E)$.