A Complete Anytime Algorithm for Treewidth
Vibhav Gogate and Rina Dechter
School of Information and Computer Science,
University of California, Irvine, CA 92967
{vgogate,dechter}@ics.uci.edu
Abstract
In this paper, we present a Branch and Bound
algorithm called QuickBB for computing the
treewidth of an undirected graph. This al-
gorithm performs a search in the space of
perfect elimination ordering of vertices of
the graph. The algorithm uses novel prun-
ing and propagation techniques which are
derived from the theory of graph minors
and graph isomorphism. We present a new
algorithm called minor-min-width for com-
puting a lower bound on treewidth that is
used within the branch and bound algo-
rithm and which improves over earlier avail-
able lower bounds. Empirical evaluation of
QuickBB on randomly generated graphs and
benchmarks in Graph Coloring and Bayesian
Networks shows that it is consistently bet-
ter than complete algorithms like Quick-
Tree [Shoikhet and Geiger, 1997] in terms of
cpu time. QuickBB also has good anytime
performance, being able to generate a bet-
ter upper bound on treewidth of some graphs
whose optimal treewidth could not be com-
puted up to now.
1 Introduction
Given an undirected graph G and an integer k the
problem whether the treewidth of G is at most k is
known to be NP-complete [Arnborg et al., 1987]. In
this paper, we develop a complete anytime algorithm
based on branch and bound search to solve the
optimization version of this problem. In other words,
we are interested in the smallest such k. The problem
can also be rephrased as f i nding a triangulation or
tree-decomposition T of G such that the treewidth of
T is same as G.
A solution to this problem is important because
many algorithms that solve NP-hard problems
in Artif i cial Intelligence, Operations Research,
Circuit Design etc. are exponential only in the
treewidth. Examples of such algorithm are Bucket
elimination [Dechter, 1999] and junction-tree elimina-
tion [Lauritzen and Spiegelhalter, 1988] for Bayesian
Networks and Constraint Networks. These algo-
rithms operate in two steps: (1) constructing a
good tree-decomposition and (2) solving the prob-
lem on this tree-decomposition, with the second
step generally exponential in the treewidth of the
tree-decomposition computed in step 1. In this
paper, we present a complete anytime algorithm
called QuickBB for computing a tree-decomposition
of a graph that can feed into any algorithm like
Bucket elimination [Dechter, 1999] that requires a
tree-decomposition.
The majority of recent literature on
the treewidth problem is devoted to f i nd-
ing constant factor approximation algo-
rithms [Amir, 2001, Becker and Geiger, 2001]. Other
heuristic algorithms include popular triangulation
heuristics like min-degree, max-cardinality search
and min-f i ll. These heuristics have no performance
guarantees and the approximation computed by them
can be exponentially bad. We discuss these heuristics
in the Section 3.
It is well known that the speed of a branch and
bound algorithm depends upon the quality of the
lower bound used. In this paper, we have developed
a new lower bound called minor-min-width that
is shown to produce a better lower bound than
max-cardinality search developed recently by Brian
Lucena [Lucena, 2003]. We implemented a branch
and bound algorithm using minor-min-width as
lower bound. However this implementation did not
terminate on some graphs having 20 vertices in 2
days of cpu time. Some analysis revealed that this
naive algorithm can be improved with some clever
modif i cations along two directions: (1) Reducing the
branching factor at each state, (2) Using pruning and