Checking if the complement of an undirected graph is bipartite

Question

Is there any linear time algorithm that says if the complement of a given undirected graph is bipartite?

I've tried using König's theorem, with no success.

Answer 1

Let us start by formalizing the problem first. In the following we assume that all graphs are simple, finite and undirected.

Def. 1: A graph $G=(V,E)$ is bipartite if $V$ can be partitioned into two subsets $X$ and $Y$ so that every edge has one end in $X$ and one end in $Y$; such a partition $(X,Y)$ is called a bipartition of the graph, and $X$ and $Y$ its parts.

Def. 2: Let $G$ be a graph. The complement $\overline{G}$ of $G$ is the simple graph whose vertex set is $V$ and whose edges are the pairs of nonadjacent vertices of $G$.

Building the complement $\overline{G}$ of a graph $G$ is quite simple and can be done efficiently using the adjacency matrix of $G$.

We denote the matrix of ones, that is a matrix where every element is equal to $1$, by $J$. We denote the identity matrix, that is a matrix where the elements on its main diagonal are ones and all other elements are zero, by $I$.

We denote the complete graph on $n$ vertices by $K_n$. Let $A_{K_n}$ be its adjacency matrix.

Lemma 1: Let $A$ be the adjacency matrix of a graph $G$ on $n$ vertices. Then the adjacency matrix of $\overline{G}$ is given by $\overline{A}=J - I -A$.

Proof: Observe that $(v_i, v_j) \in E(G) \iff (v_i,v_j) \notin E(\overline{G})$, hence $A + \overline{A}=A_{K_n}$. Clearly, $A_{K_n}=J - I$, hence $A + \overline{A}= J -I$, therefore $\overline{A}=J-I-A$.

Doing matrix substraction with $m$ rows and $n$ columns has a runtime complexity of $O(n\cdot m)$.

Now, we have constructed the complement graph. Let us define our main problem instance.

Problem Instance: A graph $G=(V,E)$.

Question: Is $G$ bipartite?

For simplicity, we assume that our graph is connected. We are using breadth-first search for solving our problem instance. It is described here.

Checkout this nice visualisation including pseudocode of the BFS on GitHub.

We also need the following:

Lemma 2: A graph is bipartite if and only if it has no odd cycles.

Proof: Check here.

It follows that a graph containing an odd cycle is not $2$-colourable (which is essentially the same as saying the graph is not bipartite).

Now, consider the following algorithm:

INPUT: A graph G.
OUTPUT: True, if G is bipartite, False otherwise.

queue := empty queue
v_0 := Pick arbitrary v_0 from V(G)
colour v_0 green
enqueue v_0 in queue
do while queue not empty
   v_x = dequeue from queue
   for each v_y in neighbors of v_x do
     if v_y has no colour assignment:
       if colour of v_x == green:
           colour v_y red
       else
           colour v_y green
       queue.enqueue(v_y)
     else colour of v_y == colour of v_x:
       return False 
return True

Notice how each neighbour $v_y$ of any vertex $v_x$ is coloured with the same colour. If we encounter a vertex $v_y$ which already has a colour (meaning that we have visited it before) and it has the same colour as $v_x$, we have found an odd-cycle, hence $G$ is not bipartite. In the language of BFS we often speak of "search level" instead of colour.

The algorithm on a graph with $m$ edges and $n$ vertices has a runtime complexity of $O(n+m)$. Notice that this is the runtime complexity when using an adjacency list. Using an adjacency matrix, the runtime complexity is $O(n^2)$. Since we have only used an adjacency matrix in this answer, let us convert it to an adjacency list:

Denote $N(v)$ as the set of neighbours of a vertex $v$ of a graph $G$.

INPUT: Adjacency matrix A of a graph G.
OUTPUT: Adjacency list of G=(V,E).
    map := empty map
    for each v in V:
        L_v := initialize empty list of size |N(v)|
        put L_v in map with key v
    for each v_i in V:
        for each v_j in V:
            if A[v_i][v_j] == 1:
                add v_i to map.get(v_j)

MISC

If the input graph $G$ is not connected, then we need to run our algorithm for each component of $G$. Furthermore, notice that the complement of a bipartite graph does not have to be bipartite. Also, it is well know that the complement of a bipartite graph is a perfect graph, hence its clique number must be equal to its chromatic number.

Answer 2

Testing if a given graph is bipartite is easy. Informally, one just has to iterate the following for each connected component: start with any vertex in the component, color it red, then color blue the neighbors of red vertices, then color red the neighbors of blue vertices, and so on until all the edges have been used. The graph is bipartite if and only if each vertex ends up with one color. This can be done in linear time and space (it suffices to avoid coloring any vertex twice the same color).

Computing the complement of a given graph is easy. It suffices to start with the empty graph on the same set of vertices, and then add each edge $(u,v)$ that does not exist in the original graph.

Therefore, it is easy to test if the complement of a graph is bipartite.

However, making it in linear time and space is not that trivial. Indeed, if the original graph has $n$ vertices and $m$ edges, then its size is $n+m$. The complement has of the order of $n^2 - m$ edges, and so if $m$ is small, typically if $m$ is in $O(n)$, then building the complement has a $n^2$ time and space cost.

It turns out that a closely related question was posted here 6 years ago and received no satisfactory answer.

Answer 3

There is a trick to that problem : if the graph has $n$ nodes and $m$ edges, then the solution is an algorithm in $O(n^2)$, but this would be linear in the input graph's size because $m = \Theta(n^2)$.

The key idea is : if a graph is bipartite, then its complement is dense (it has more than $\frac{n^2}{4} - \varepsilon n$ edges). Indeed, the bipartite graph is a subgraph of the complete bipartite graph $K_{m,n}$ which has $mn$ edges for $(m+n)$ vertices, which (for any ratio of $m$ and $n$) has a density inferior to $\frac 1 2$ (asymptotically), so the complement of any bipartite graph has a density of at least $\frac 1 2$ (also asymptotically)

Then, the algorithm deciding "given the graph $G = (V,E)$, decide whether $G^C = (V, V^2 \setminus E)$ is bipartite" goes as follow :

• If $|E| < \frac {|V|^2} 4$, then answer "No"
• Else, compute $G^C$ explicitly, and apply the classical algorithm for the detection of bipartite graphs. That algorithm is linear in $|V| + |V^2 \setminus E| = O(|V|^2) = O(|E|)$ so is linear in the input graph's size.

(of course, the bound for answering "No" isn't exactly $\frac {|V|^2} 4$, but the exact optimal value might be annoying to compute)