\documentclass{article}
\input{6046preamble}


\begin{document}
\pset{5-3}{Dan Ports}{No collab}{Recitation \#8}

\paragraph{Algorithm}
We will determine if a graph is bipartite by attempting to two-color it. We take as input a set $V$ of vertices and a set $E$ of edges. Assume w/o loss of generality that the graph is connected (if it is not, we can divide the graph into its connected components in $\Theta(\abs{E})$ time and test whether each of the components is bipartite).
\paragraph{}
 First, we construct an adjacency list A, which is an array of linked lists, one for each vertex. For each vertex $v\in V$, $A_v$ is a list of pointers to all edges in $E$ whose source endpoint is $v$. Generating these adjacency lists takes time $\Theta(\abs{E})$, and it allows us to obtain the list $A_v$ of edges leading from $v$ in time $\Theta(\abs{A_v})$.
\paragraph{}
We will augment the list of vertices to associate a color field with each vertex. Each vertex can be assigned one of two colors -- which we will arbitrarily choose to be red and blue -- or be uncolored. We first select some arbitrary vertex $u$ and arbitrarily color it red. We then perform a modified breadth-first search. We modify the algorithm slightly so that whenever we dequeue a vertex $u$, we check the color of each vertex $v$ in the adjacency list $A_u$. If $v$ is uncolored, then it has not been previously visited, and we color it the opposite of $u$ (and add it to the queue, as the normal BFS algorithm does). If $v$ is already colored, then we compare the colors of $u$ and $v$. If they are identical, we immediately declare the graph non-bipartite and return. Otherwise, we continue the BFS. When the BFS finishes, if the algorithm has not already terminated (by finding the graph non-bipartite), we declare the graph to be bipartite and return.
\paragraph{Proof of correctness}
We will show that for either result, the algorithm is correct. Suppose the algorithm returns bipartite. Then it has constructed a two-coloring for the graph. We know this is true, because at every set of the BFS we verified that any two adjacent vertices have different colors. Thus, the graph is indeed bipartite. 
\paragraph{}
If the algorithm returns non-bipartite, we know that it found two adjacent nodes $u$ and $v$ that were colored the same color. We will show that this means there is no possible two-coloring of the graph. Because both $u$ and $v$ were already colored, they were previously dequeued and colored by the algorithm. Call the starting node $s$. Because $u$ and $v$ have the same color, the paths $s \rightarrow u$ and $s \rightarrow v$ must either both have even length or both have odd length. So the path $u \rightarrow s \rightarrow v$ has length equal to their sum, which will be even. Then, since $u$ and $v$ are adjacent, the path $u \rightarrow s \rightarrow v \rightarrow u$ has length one greater, and thus has odd length. This means that the graph contains an odd cycle. From 6.042, we know that there is no way to two-color a graph that contains an odd cycle (trivial proof omitted). So if the algorithm returns non-bipartite, the graph is non-bipartite. Thus the algorithm always returns the correct result.
\paragraph{Runtime analysis}
Generating the adjacency list requires time $\Theta(\abs{E})$. Our modifications to the BFS procedure do not change the runtime. Each adjacency list is scanned at most once, so scanning the adjacency lists requires $O(\sum_{v \in V}{\abs{A_v}}) = O(\abs{E})$, and the overhead for initializing the vertices is $O(\abs{V})$. So the total runtime of the algorithm is $O(\abs{V}+\abs{E}) = O(\abs{E})$, since we are given the assumption that $\abs{E} = \Omega(\abs{V})$.
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: