Question

The time complexity to test whether a graph is bipartite or not is said to be _______ using depth first search.

(a) O(n^3)

(b) linear time

(c) O(1)

(d) O(nlogn)

This question was posed to me in class test.

The above asked question is from Bipartite Graphs topic in section Graphs of Discrete Mathematics

Answer 1

Right choice is (b) linear time

The best explanation: It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) in linear time i.e, O(n) using depth first search. In case of the intersection of n line segments or other simple shapes in the Euclidean graph, it is possible to test whether the graph is bipartite and it will return either a two-coloring or an odd cycle in time O(nlogn), even though the graph itself has up to O(n^2) edges.