\documentclass[11pt]{article}
%\renewcommand{\baselinestretch}{1.5} % For Andrzej

\newcommand{\define}[1]{\textit{#1}}
\newcommand{\suchthat}[0]{\textrm{ such that }}
\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\file}[1]{{\tt \bf #1}}

\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{verbatim}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}

\title{A General Algorithm for Performing Graph Reductions}

\author{P. Boothe\\
Computer Science Dept.\\
University of Oregon\\
{\tt peter@cs.uoregon.edu} \\
\url{http://soy.dyndns.org/~peter/projects/research/reduction/}}

\begin{document}
\maketitle

\begin{abstract}
We describe and prove correct an algorithm that can implement any graph
reduction system.  Previous work non-constructively showed this algorithm's
existence, we give a constructive proof.
\end{abstract}


\section{Introduction}
Graph theory and testing graph properties have proven to be fertile
grounds for algorithms research, with applications to networks,
digital design, and even analysis of social hierarchies.  Graphs with
a particular property are often essential to guarantee a correct
design, and some algorithms that are exponential time in the general
case can be run in polynomial time on certain classes of graphs.  Many
properties are very easy to test for -- whether a graph is connected
can be solved with a simple depth first search, for example -- but
testing for other properties, such as Hamiltonian Path, has been shown
to be NP-Hard.

The ideal algorithm would take a description of the desired property
in some formal language, and a graph.  Then it would quickly respond
with true or false based on whether the graph has the desired
property.  Unfortunately, since testing for many properties is
NP-Hard, this algorithm is currently unknown and possibly nonexistant.
One way to get around this is to restrict the language so that it
cannot describe an NP-Hard property.  One such restriction is
\define{monadic second order logic}, which is a restriction of second
order logic to quantifiers over functions of arity at most one.  It
was shown in \cite{Reduction} that any property with bounded treewidth
described in this language was necessarily testable in linear time
with respect to the size of the input graph.  Despite this surprising
time bound, the language still has quite a bit of expressive power.
Many properties, including outerplanarity, 3-connectedness, partial
3-tree, planar partial 3-tree, and planar partial 2-tree can be
expressed.

The existence of a time-efficient algorithm was then proven by showing
(non-constructively) that any property describable in monadic second
order logic necessarily has a corresponding \define{graph reduction
system} and then showing (non-constructively again) that each reduction
system necessarily has a linear time algorithm for testing whether a
graph has the property corresponding to the original property.  A graph
reduction system is a set of \define{reduction rules}, which are pairs
of labeled graphs, each vertex of which is also tagged as
\define{restricted} or \define{unrestricted}, and a set of base graphs
which we refer to as \define{reducts}.  Whenever an instance of the
left graph of any of the reduction rules is found as a subgraph of our
tested graph, subject to the constraint that the restricted vertices
have the same degree in the original graph as they do in the reduction
rule, we apply the corresponding reduction rule by replacing the
subgraph with the other graph in the rule.  Once we can no longer apply
any reduction rules we test whether the reduced graph is isomorphic to
any of our reducts.  If our graph is isomorphic to a reduct, then the
graph has the desired property.  Otherwise it does not.  A sample graph
reduction system is shown in Figure~\ref{p3t}, with the restricted
nodes colored solid, and the unrestricted ones hollow.  The labeling of
the graph is implied by the positions of each node.  The definition of
a graph reduction system does not imply an ordering on reduction rules,
thus any graph with the the desired property will reduce to a valid
reduct, no matter the order in which the reduction rules are applied.

\begin{figure}[tb]
\begin{center}
\scalebox{.25}{\includegraphics{p3t_rules}}
\end{center}
\caption{A sample graph reduction system for partial 3-trees.  Solid black
vertices are restricted, solid white ones are unrestricted, and the
only reduct (not shown) is the empty graph}
\label{p3t}
\end{figure}


More formally, a graph reduction system $S$ consists of a set of reduction
rules $S_U$, and a set of irreducible reducts $S_I$.  A reduction rule $U \in
S_U$ is two graphs $G_{left} = (V_{left},E_{left})$ and $G_{right} =
(V_{right},E_{right})$ such that the size of $G_{right}$ is strictly less than
the size of $G_{left}$ for some measure of graph size.\footnote{Most systems
have $V_{right} \subset V_{left}$, but that is not required.}
Furthermore, for each $V_{left}$ we have a set $E \subseteq V_{left}$ that
we label restricted.  Whenever we see a subgraph of our input graph $G =
(V,E)$, that is isomorphic to a $G_{left}$ in rule $L$ via some mapping
$m$, and $\forall v$ such that $m(v) \in E$ it is true that $d_G(v) =
d_{G_{left}}(m(v))$ where $d_G$ is the degree function for $G$, we can
reduce our graph by reduction rule $U$ by setting 
\begin{eqnarray*}
V' & = & (V \setminus \{ v | m(v) \in E \}) \cup \{v | m(v) \in V_{right}\}  \\
E' & = & (E \setminus \{(u,v) | (m(u), m(v)) \in E_{left}) \cup \{(u,v) | (m(u), m(v) \in E_{right} \}.
\end{eqnarray*}
We then repeat our search on $G' = (V', E')$ until no chances to apply a
reduction rule can be found.  We then \define{accept} the graph it is isomorphic
to some element of $S_I$ and \define{reject} it otherwise.

Several things are surprising about these systems.  The first is that the order
in which rules are applied does not matter!  In a graph reduction system, it
does not matter what order you apply the rules in -- if a graph has the
property under test, it will be reduced to some reduct in $S_I$ no matter what
the rule order is.  The second is that these systems have enough power to test
any MSOL bounded treewidth property.  The power of these systems should not be
too surprising, however, as there is a very deep connection between graph
reduction systems and graph grammars.

Graph grammars are tools used to create graphs that have a particular property,
and graph reduction systems can be analogized to tools that parse graphs to
check for a property.  Further extending the analogy, it is sometimes useful to
think of the restricted vertices as the terminal symbols of a production
grammar, and the reducts as start expressions for the production of graphs.
Graph grammars have been written about extensively, and their relation to graph
reduction systems can be found many places, including \cite{handbook}.

\section{Algorithm}
\input{algorithm}

The goal of Algorithm~\ref{alg:general} is to take each vertex with a degree no
larger than the largest degree of any restricted vertex, and attempt to
place that vertex in each restricted place in each reduction rule.  Since
it does not matter what order we apply reductions in, we apply them greedily.
Every time it is possible to reduce the graph, we do so.  Our prof of
correctness will then follow from the fact that we never stop trying to reduce
the graph until there are no reductions possible.

For the purposes of the algorithm, it will be necessary to talk about the
\define{border nodes} of a restricted vertex.  These are exactly the
unrestricted vertices surrounding the subgraph of restricted nodes containing
that restricted vertex.

The running time of our algorithm is initially hard to see for two reasons.
Partially because it hinges upon the time it takes to perform the operations
{\tt SET} and {\tt ACCESS} on an associative array, and partially because when
we talk about the runtime of our algorithm, we talk about its parameterized
complexity\cite{parameterized}, which has the expressiveness to deal with the
two inputs separately.

Abstracting away issues of {\tt SET} and {\tt ACCESS} time, and simply
referring to $\max(t_{SET}, t_{ACCESS})$ as $t_M$, we will prove the following
theorem:

\newtheorem{thm}{Theorem}
\begin{thm}[Running Time of Algorithm~\ref{alg:general}]
Algorithm~\ref{alg:general} runs in $O(n*t_M)$ time with respect to the size of the graph under test.
\end{thm}

\begin{proof}
We begin by noting that the initial $n$ time is created by the act of
reading in the graph.  Then, we put in the queue all vertices of degree no
larger than the largest restricted vertex, which takes $O(|V|)$ time.  Then,
inside the \code{while()} loop, we note that the number of iterations of
every \code{for()} loop is bounded above by a constant with respect to the
input graph.  Therefore, we execute \code{SET} and \code{ACCESS} on $M$ at
most a constant number of times each iteration of our main loop.

Every iteration of that main loop either applies a reduction or it does not.  If the vertex under test does not complete a reduction rule, then we simply record any rules that it matched part of, and never look at it again unless its degree changes.  If it does complete a reduction rule, then that reduction rule is applied to the graph, making it smaller.  At the same time the rule is applied, all vertices whose degree has changed and is sufficiently small are put into the search queue if they were not there already.  To get our $O(n)$ bound on the number of \code{while()} loop iterations, we count the maximum number of iterations that a problematic graph could force us to go through.

Since every increase in queue size is accompanied by a corresponding decrease
in graph size, we can have at most $n$ queue size increases before the graph
has been reduced to nothing.  These increases in queue size never increase the
queue by more than a constant (again, with respect to the input graph) because
the rules are constant size with respect to the graph.  Calling the maximum
size increase $k$, we can see that the greatest number of iterations we could be
forced to do is $O(n*k) = O(n)$.  Thus, we will run through the main loop
$O(n)$ times, and each iteration takes $O(1 + t_M)$ time, for a total time
bound of $O(n*t_M)$.
\end{proof}

Various implementations of $M$ have different effects on our runtime, with the
more obvious balanced tree or hashtable approaches leading to $O(n \lg nP$ and
$O(n)$ expected time and $O(n^2)$ worst case, respectively.  Tarjan
describes in \cite{RET} a method of implementing an associative array
with $O(1)$ access time, which leads to our best case linear time bound,
but it is unlikely that this would be used in practice due to its
extremely large space requirements.

All this time, however, we have been ignoring the effects of our reduction
system on the runtime.  If we hold our input graph fixed, and only look at the
reduction system's affect on the runtime, then simply counting up the maximum
bounds of each internal \code{for()} loop we get a runtime of
$O(r*p*s^d*t_{gi}(s)$, where $r$ is the number of reduction rules, $p$ is the
maximum number of subgraphs of restricted components in a rule, $s$ is the
maximum size of these subgraphs, $d$ is the maximum degree of a restricted
vertex, and $t_{gi}$ is the time it takes to perform graph isomorphism on a
graph of the given size.  To get a runtime in terms of only two factors, we
concentrate on the maximum subgraph size and call it $k$.  The best
known graph isomorphism solutions have a running time of $O(2^k)$
where $k$ is the size of the graph being tested.  
On an intuitive level, graph reduction systems have many rules, but it is
only when the rules get big that the problem becomes really hard.  Choosing
subgraph size as our parameter allows us to do several things.  First of all,
we can ignore $r$ and $p$, then we can note that the largest $s$ or $d$ can be
is $k$.  Which makes the runtime of the algorithm $O(2^k*k^k*n*t_M)$.  Which,
as described earlier, we can make as low as $O(n)$, but will probably be
$O(n \lg n)$ in most implementations.


\section{Conclusion}

We have described and proven correct algorithm that will work for any reduction
system.  In addition, we also have an implementation that works in $O(|V|+|E|)$
expected time that can be downloaded from
\url{http://soy.dyndns.org/~peter/projects/research/reduction/linear}.  The
algorithm works and, despite an intimidating looking runtime, is useful for
testing many properties.

\section{Further Work}

Automatic discovery of reduction rules from a monadic second order logic
description remains an open problem, as does the automatic generation of
heuristics that might help with subgraph isomorphism.  Also, figuring out
whether or not an MSOL property has bounded treewidth is not always easy, and
it would be useful if that was automated as well.


\bibliographystyle{plain}
\bibliography{drp}

\input{code.tex}

\end{document}