# Homework 4

Due Wednesday, January 29 at 5:00 PM. Please refer to the homework policy here.

1. A graph $G = (V,E)$ is bipartite if the vertices $V$ can be partitioned into two subsets $L$ and $R$, such that every edge has one vertex in $L$ and the other in $R$. Describe and analyze an efficient algorithm that determines whether a given unidrected graph is bipartite.
2. Suppose we are given a directed acyclic graph $G$ with a unique source $s$ and a unique sink $t$. A vertex $v \notin \{s,t\}$ is called an $(s,t)$-cut vertex if every path from $s$ to $t$ passes through $v$, or equivalently, if deleting $v$ makes $t$ unreachable from $s$. Describe and analyze an algorithm to find every $(s,t)$-cut vertex in $G$.