0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – fade2black Aug 6 '17 at 16:32
  • $\begingroup$ @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 $\endgroup$ – Ron.K Aug 6 '17 at 16:42
  • $\begingroup$ 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)$. $\endgroup$ – fade2black Aug 6 '17 at 16:49
  • $\begingroup$ @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. $\endgroup$ – Ron.K Aug 6 '17 at 16:53
  • $\begingroup$ 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)$? $\endgroup$ – fade2black Aug 6 '17 at 17:42
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Thanks a lot! but I wonder why an edge will be visited at most twice, since it can take a part in more than one cycle. Can you please explain your decision? since from reading what you have written I think you have understood the algorithm completely. $\endgroup$ – Ron.K Aug 6 '17 at 19:52
  • $\begingroup$ You move forward along a path by visiting edges, and then you backtrack - you are visiting the same edges again. $\endgroup$ – fade2black Aug 6 '17 at 20:03
  • $\begingroup$ pastebin.com/rCj3xbTW - added the pseudo code of my algorithm here. It might not be perfect, but it presents the general idea of my algorithm and how it should work. $\endgroup$ – Ron.K Aug 7 '17 at 5:40
  • $\begingroup$ @Ron.K Your question should be self-contained. You could add it to your OP. It is fine as long as it is a pseudocode and not in a specific language. $\endgroup$ – fade2black Aug 7 '17 at 6:00
  • $\begingroup$ @Ron.K not link, the code itself. it must be self-contained. If your external link disappears then none will be able to see your pseudocode. $\endgroup$ – fade2black Aug 7 '17 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.