Checking if a Graph is Bipartite

Recall, that a graph $g = (V, E)$ is bipartite if its node set $V$ can be partitioned into two disjoint and non-empty sets $V1$ and $V2$ such that every edge in the graph connects a node in $V1$ and a node in $V2$. When this condition holds, we call the pair $(V1, V2)$ a bipartition of the node set $V$ of $g$.

We have seen in lecture and the handouts a brute-force algorithm for determining if a graph is bipartite. The pseudo-code for such an algorithm is:

We know how to implement such an algorithm in Python. One such implementation is:

def is_bipartite(g):
    """
    Check if graph, g, is bipartite.

    Arguments:
    g -- undirected graph

    Returns:
    True if g is bipartite, False otherwise.
    """
    V = set(g.keys())
    half = len(V) / 2

    # Check all possible partitions, where each partition has at least one node and no node
    # is in both partitions.
    for i in range(1, half+1):
        for candidate in itertools.combinations(V, i):
            # Create two candidate sets, V1 and V2
            V1 = set(candidate)
            V2 = V - V1

            # Check all edges in the graph to ensure they don't connect nodes in the same set
            bipartite = True
            for u in g:
                for v in g[u]:
                    edge = set([u, v])
                    if edge.issubset(V1) or edge.issubset(V2):
                        # Found an edge connecting nodes in same set, stop checking this partition
                        bipartite = False
                        break

                if not bipartite:
                    # Already know this partition is not a bipartition, stop checking it
                    break

            if bipartite:
                # The current partition is a bipartition, the graph is bipartite
                return True

    # No bipartition was found, the graph is not bipartite
    return False

Transform and Conquer

We know that the brute-force algorithm will work, but it is incredibly inefficient. Have we seen any other algorithms that might help us to determine if a graph is bipartite?

As with all transform and conquer solutions, in order to answer "yes", we must also answer the following questions:

1. How can we transform the "is bipartite" problem into another problem?
2. How do we solve that problem?
3. How do we interpret the results of that problem to solve the "is bipartite" problem?

Does this transformation help us? Why or why not?

Let's Be More Clever (a.k.a. finally - I don't have to use brute force in lab!)

How can we solve the "is bipartite" problem (and/or the transformed problem) in a more clever way? Do we need to exhaustively search all partitions to determine if a graph is bipartite? What can we do instead?

Exercise 1 - Algorithm

Come up with an English-language description of an algorithm to solve the "is bipartite" problem that is better than brute force.

Exercise 2 - Correctness

Is your algorithm correct? How do you convince yourself and others of this?

Exercise 3 - Pseudo-code

Develop pseudo-code for your algorithm to determine whether a graph is bipartite.

Exercise 4 - Efficiency

Analyze the running time of your algorithm from Exercise 3 using big-O notation. Is it better than brute-force?

Exercise 5 - Implementation

Implement your algorithm developed in exercise 3. Use your algorithm to assert that:

g1 = { 'A' : set(['C', 'D', 'E']),
       'B' : set(['C', 'D']),
       'C' : set(['A', 'B']),
       'D' : set(['A', 'B']),
       'E' : set(['A']) }

is bipartite.

That

g2 = { 'A' : set(['C', 'D', 'E', 'B']),
       'B' : set(['C', 'D', 'A']),
       'C' : set(['A', 'B']),
       'D' : set(['A', 'B']),
       'E' : set(['A']) }

is not bipartite.

and that

g3 = { 'A' : set(['C', 'D', 'E']),
       'B' : set(['C', 'D']),
       'C' : set(['A', 'B']),
       'D' : set(['A', 'B']),
       'E' : set(['A']),
       'F' : set(['Z', 'X']),
       'X' : set(['F', 'Z']),
       'Z' : set(['F', 'X']),}

is not bipartite.

Exercise 6 - Running Time

Compare the running time of your new algorithm with the brute-force algorithm given above. Does the running time of your algorithm match your big-O analysis from Exercise 4?

---

Submit your code

At the end of lab, submit your group's Python code here.