Graphs (directed)

As you work on Problem 2, we will take some time to discuss a brute force approach and analyze correctness/runtime. 

• To set this up, we'll first think about a brute force approach to checking if a graph is bipartite.

• Consider this algorithm design process:

Step 1: Articulate the problem

Given a graph G = (V,E), is there a partition of the vertex set into two disjoint subsets such that every edge has an endpoint in each of the two subsets?

Step 2: Propose a solution

Let's try a "brute force" approach, where we consider every possible way of partitioning the vertex set, then check if any verify that the graph is bipartite.

• • For every partition of the vertex set into two subsets

    • Check if there is an edge with both endpoints in the same subset. If so, move on to the next partition.

    • If there were no such edges, return yes.

  • If every partition had an edge with both endpoints in the same subset, return no.

Step 3: Prove correctness

With a brute force approach, correctness typically is straightforward. Here, we directly test the definition of a bipartite graph: does there exists a partition with edges only going between endpoints in the different sets. (Or, if we think of it as a 2-coloring, edges have different colors on their endpoints.) 

Here is a more formal proof:

Claim: The brute force approach returns "yes" if and only if the input graph is bipartite.

Proof: 

(=>) Assume the approach returns "yes"; this happens precisely when it finds a partition of the vertices such that no edges have endpoints in the same vertex set. Therefore, we have satisfied the definition of a bipartite graph.

(<=) Assume the graph is bipartite. Then, by definition, there exists a partition such that no edges have endpoints in the same vertex set. There are a finite number of partitions, so the process enumerates them all. At some point, it will find this partition and return the correct answer "yes". 

Step 4: Analyze complexity

We'll analyze the time complexity of the approach. First, observe that there are 2n  ways to partition the vertex set of n vertices into vertex sets X and Y. To see this, pick an arbitrary ordering of the vertices v1,...,vn. Each vi can either be in X or Y (2 choices), so there are 2n  total ways to partition into X and Y. Let's assume that we mark each vertex with its partition label. The body of the loop checks every edge to see if both endpoints are marked with the same label. Therefore, we must walk over each edge; the time for this depends on the graph representation that we use. If we use an adjacency list, we take O(m+n) time to walk the edges; even with the assumption that we can find the endpoint marks in constant time, this will lead to an overall running time of O((m+n)2n). We can do slightly better if we use a set representation for the graph and assume that each edge has a pointer to its endpoints. In this case, we can walk the edges in O(m) time, leading to an overall running time of O(m2n).

No matter which representation we use, though, this is a terrible running time! The brute force approach gives us an upper bound on how to solve the problem, so any algorithm that does (asymptotically "a lot") better must have used deeper problem solving.

Homework (due Thursday 10/19 end of day on Gradescope)

• • Greedy Module 1 (complete before 10/12 class)

  • Ask and answer questions via Ed Discussion!