\author{Problem Author: Nathan Nguyen}
\newcommand{\utopiarelationshipsheader}{Problem M: Utopia Relationships}

\begin{frame}{\utopiarelationshipsheader{}}
  \begin{block}{Problem}
    \begin{itemize}
      \item You are given an undirected graph with up to $5\,000$ edges.
      \item Assign a non-negative integer weight to every edge so that for every vertex, the sum of the weights on adjacent edges is exactly $10\,000$.
      \item (Or declare that it's impossible.)
    \end{itemize}        
  \end{block}
\end{frame}
\begin{frame}{\utopiarelationshipsheader{}}
  \begin{block}{Solution Idea}
    \begin{itemize}
      \item From the input graph, we will create the following \emph{directed} bipartite graph $G$:
      \begin{enumerate}
        \item Duplicate the vertices into a left set $\{v_1, v_2, \ldots, v_n\}$ and a right set $\{w_1, w_2, \ldots, w_n\}$.
        \item Draw an edge from $v_i$ to $w_j$ (and from $v_j$ to $w_i$) if vertices $i$ and $j$ are neighbors in the input graph.
      \end{enumerate}
      \item Then the following are equivalent:
      \begin{enumerate}
        \item There is a solution to the Utopia Relationships problem.
        \item $G$ has a perfect matching.
      \end{enumerate}
    \end{itemize}        
  \end{block}
\end{frame}
\begin{frame}{\utopiarelationshipsheader{}}
  \begin{block}{Utopia Relationships solution implies a perfect matching}
    \begin{itemize}
    \item We prove this implication using the Hall Marriage Theorem.
    \item Let $S = \{v_{i_1}, v_{i_2}, \ldots, v_{i_a}\}$ be any subset of the ``left'' vertices.
    \item Let $T = \{w_{j_1}, w_{j_2}, \ldots, w_{j_b}\}$ be the neighbors of $S$ among the ``right'' vertices.
    \item Consider the vertices $\{i_1, i_2, \ldots, i_a\}$ in the Utopia Relationships solution. They assign $10\,000|S|$ total affection to their neighbors.
    \item This means that the vertices $\{j_1, j_2, \ldots, j_b\}$ assign at least $10\,000|S|$ affection to their neighbors (since they must reciprocate).
    \item But the total affection assigned by those vertices is $10\,000|T|$.
    \item Therefore $10\,000|S| \leq 10\,000|T|$ and $|S| \leq |T|$, and thus by the Hall Marriage Theorem, $G$ has a perfect matching.
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{\utopiarelationshipsheader{}}
  \begin{block}{Perfect matching implies Utopia Relationships solution}
    \begin{itemize}
    \item Each vertex $v_i$ is matched with some vertex $w_j$, with $j\neq i$ (since no vertex is its own neighbor on the original graph).
    \item For each such matching, add $5\,000$ affection to edge $(i,j)$ on the original graph.
    \item At the end of this process, every edge has weight $0$, $5\,000$, or $10\,000$.
    \item It is easy to see that for every vertex, the sum of the weights on adjacent edges is $10\,000$ (since each vertex appears once on the left and once on the right of the perfect matching).
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{\utopiarelationshipsheader{}}
  \begin{block}{Solution}
    \begin{itemize}
    \item Compute a perfect matching on $G$.
    \item A standard solution is to connect all vertices $\{v_i\}$ to a source, all vertices $\{w_j\}$ to a sink, set all edge capacities to $1$, and compute a maximum flow from the source to the sink. A perfect matching exists if the maximum flow is $n$.
    \item For the problem bounds given, Ford-Fulkerson is enough to solve the flow problem, as it runs in $O(n(n+m))$ time.
    \item If a perfect matching exists, convert it to a Utopia Relationships solution as described previously. Otherwise, no solution is possible.
    \end{itemize}
  \end{block}
\end{frame}
