\documentclass{amsart}

\DeclareMathOperator{\idom}{idom}
\DeclareMathOperator{\sdom}{sdom}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\begin{document}

\author{Nick Belov}
\author{James Betti}
\author{Nuray Kutlu}
\title{Math 640 Project 4\\ Dominators of Directed Graphs}
\maketitle

\section{Defining the Problem}

\begin{definition}[Domination Relation]
  Let \( G = (V, E) \) be a directed graph with some designated source vertex \( S. \) It is assumed that every vertex in \( G \) is reachable starting from \( S. \) For distinct vertices \( v \) and \( w, \) \( v \) is said to be \emph{dominated} by \( w \) if every path from \( S \) to \( v \) contains \( w. \)
\end{definition}
\begin{definition}[Immediate Dominator]
  A vertex \( w \) is an \emph{immediate dominator} of \( v \) if \( w \) dominates \( v \) and every other dominator of \( v \) dominates \( w. \)
  A vertex \( w \) is an \emph{immediate dominator} of \( v \) if \( w \) dominates \( v \) and every other dominator of \( v \) dominates \( w. \)
\end{definition}
\begin{theorem}[]
  Every vertex except for \( S \) has a unique immediate dominator.
\end{theorem}
The immediate dominator of a vertex \( v \) will be denoted \( \idom(v). \)

\begin{definition}[Dominator Tree]
  The \emph{dominator tree} of a directed graph \( G \) is a directed tree \( T \) such that:
  \begin{itemize}
    \item The root of \( T \) is the source vertex \( S \).
    \item Each vertex \( v \) in \( G \) is a child of its immediate dominator \( \idom(v) \).
  \end{itemize}
\end{definition}
The dominator tree of a directed graph entirely captures the domination relationships in the graph. In paticular, the dominators of a fixed vertex \( v \) are exactly the ancestors of \( v \) in the dominator tree!

In our project, we implemented two algorithms for computing the dominator tree of a directed graph. The first being a naïve algorithm that runs in \( O(\lvert E \rvert \cdot \lvert V \rvert) \) and the second being the much more efficient Lengauer-Tarjan algorithm that runs in \(O(\lvert E \rvert \log \lvert V \rvert)\).
\section{Maple Implementation}

Our implementation provides two Maple procedures:

\begin{description}
\item[\texttt{constructDominator}] a straightforward enumeration method that follows the definition of dominance and runs in $O(|V|\,|E|)$ time;
\item[\texttt{constructDominatorC}] an optimized version that mirrors the Lengauer--Tarjan approach.
\end{description}

Both procedures expect a digraph encoded as a triple $[n,E,S]$ where
\begin{itemize}
  \item $n$ is the number of vertices (labeled $1,\dots,n$),
  \item $E = \{[u_1,v_1],\dots,[u_m,v_m]\}$ is the edge set represented as a Maple \emph{set} of two--element lists $[u,v]$ (edge $u\to v$),
  \item $S$ is the designated source vertex. Both functions assume that every vertex is reachable from $S$.
\end{itemize}

Each function returns a list of length $n$. The $i$th entry of this list is $\idom(i)$, the label of the immediate dominator of vertex $i$. For the root $S$ the entry is $0$. In order to ensure correctness of the fast algorithm we tested both functions against small random digraphs to ensure that they produce the same output.

\section{A Slow Algorithm}
There is an easy \( O(\lvert E \rvert \cdot \lvert V \rvert) \) solution using depth-first search (DFS). A DFS is performed to check which vertices are reachable from \( r. \) Then for each vertex \( v \):
\begin{itemize}
\item remove \( v \) from the graph;
\item perform DFS starting from \( r \) to determine which vertices are now reachable;
\item the vertices no longer reachable are dominated by \( v. \)
\end{itemize}
In particular the dominators of each non-root vertex \( v \) can be determined, which can be checked to find \( \idom(v). \)

\section{A Fast Algorithm}

A complete description and justification of the Lengauer-Tarjan algorithm, which achieves an $O(\lvert E \rvert \log \lvert V \rvert)$ time complexity, can be found in the original paper. Here, we highlight some of the main aspects of the algorithm.

First, it is helpful to relabel the vertices in DFS order.

\begin{definition}[Semidominator]
Given a vertex $w$ in a directed graph labeled according to DFS order, the \emph{semidominator} of $w$ is defined as:
\begin{multline*}
  \sdom(w) = \\ \min \{ v \mid \text{there is a path } v = v_0, v_1, \dots, v_k = w \text{ with } v_i > w \text{ for } 1 \leq i < k \}.
\end{multline*}
\end{definition}

Lengauer and Tarjan proved the following relationship:

\begin{theorem}[]
Let $u$ be the vertex with minimum $\sdom(u)$ among all vertices $u$ such that there is a path $\sdom(w) \rightarrow u \rightsquigarrow w$. Then the immediate dominator of $w$ satisfies:
\[
\idom(w) = \begin{cases}
\sdom(w), & \text{if } \sdom(w) = \sdom(u), \\
\idom(u), & \text{otherwise.}
\end{cases}
\]
\end{theorem}

This theorem enables us to efficiently compute the immediate dominators if we already know the semidominators.

To actually compute the semi-dominators, Lengauer and Tarjan used a union-find data structure with path compression which is the final ingredient in the algorithm.

\bibliography{dominator}
\bibliographystyle{amsplain}

\end{document}
