Many intractable computational problems on graphs admit tractable algorithms
when applied to trees or forests. Tree decomposition extracts a tree structure
from a graph by grouping nodes into bags, where each bag corresponds to a
single node in of the tree. The corresponding operation on hypergraphs is that
of a generalized hypertree decomposition [
Past research has focused on obtaining a \good" tree decomposition for the
given graph, where goodness is typically measured by means of the width|the
maximal cardinality of a bag. Nevertheless, nding a tree decomposition of a
minimal width is NP-hard [
In this paper, we describe our ongoing e ort on the task of enumerating all
(or a subset of) the tree decompositions of a graph. Such algorithms have been
proposed in the past for small graphs (representing database queries), without
complexity guarantees [
Graphs. The graphs in this work are undirected. For a graph g, the set of nodes is denoted by V(g), and the set of edges (where an edge is a set fu; vg of distinct nodes) is denoted by E(g).
Tree Decomposition. A tree decomposition d of a graph g is a pair (t; ), where t is a tree and : V(t) ! 2V(g) is a function that maps every node of t into a set of nodes of g, so that (a) [v2V(t) (v) = V(g), (b) for every edge e 2 E(g) there is a node v 2 V(t) such that e (v), and (c) for all u; v; w 2 V(t), if v is on the path between u and w, then (v) contains (u) \ (w). For a tree decomposition d = (t; ) and a node v of t, the set (v) is called a bag of d, and we denote by bags(d) the set f (v) j v 2 V(t)g. Two tree decompositions d1 and d2 are bag equivalent if bags(d1) = bags(d2).
When enumerating tree decompositions, we wish to avoid the generation of decompositions that are clearly useless. As an extreme example, if the input graph is already a tree, then usual applications are not interested in any of the tree decompositions (e.g., putting all nodes in a single bag) besides the original tree itself. In a common algorithm over a tree decomposition, the bags are the parts where an expensive (e.g., exponential-time) algorithm is applied. In such cases, it will be bene cial to split a bag, or remove it altogether, if possible. This leads to the notion of a proper tree decomposition. Formally, a tree decomposition d of a graph g is said to be proper if there does not exist any tree decomposition d0 of g such that (a) every bag of d0 is contained in some bag of d, and (b) bags(d) 6 bags(d0). In particular, a proper tree decomposition cannot be improved by removing or splitting a bag. For illustration, a chordal graph (e.g., a tree) may have exponentially many tree decompositions, but only a single tree decomposition up to bag equivalence.
Chordality and Triangulation. Let g be a graph. For a cycle c in g, a chord
of c is an edge e 2 E(g) that connects two nodes that are non-adjacent in c. We
say that g is chordal if every cycle of g of length greater than three has a chord.
A triangulation of a graph g is a graph h such that V(g) = V(h), E(g) E(h),
and h is chordal. A minimal triangulation of g is a triangulation h of g with the
following property: for every graph h0 with V(g) = V(h0), if E(g) E(h0) ( E(h),
then h0 is non-chordal (i.e., h0 is not a triangulation of g). In particular, if g is
already chordal then g is the only minimal triangulation of itself.
Enumeration Algorithms. Our goal is to devise e cient algorithms for
enumerating (proper) tree decompositions. Polynomial running time is an
inadequate yardstick of e ciency for this problem, since it may be the case that the
number of tree decompositions is exponential. Johnson et al. [
We now describe some of the results we established so far in our ongoing research. In search of an algorithm for enumerating tree decompositions, we started by looking at the problem of enumerating minimal triangulations. Later, we will discuss the connection between the two problems. The rst result states that we can enumerate the minimal triangulations in incremental polynomial time. Theorem 1. There is an algorithm that, given an input graph g, enumerates the minimal triangulations of g in incremental polynomial time.
The proof of Theorem 1 builds on the algorithm of Berry et al. [
The next result states the relationship between proper tree decompositions
and minimal triangulations. This result is obtained by combining known results
by Heggernes [
Proposition 1. Let g be a graph. There is a bijection M between the minimal triangulations of g and the bag-equivalence classes of the proper tree decompositions of g. The function M maps a minimal triangulation h of g to the proper tree decompositions of g that have the maximal cliques of h as bags.
Note that a maximal clique is a clique that is not properly contained in any
other clique. Let g be a graph, and let h be a triangulation of g. Let G be the
graph that has the maximal cliques of h as its node set, and an edge between
every two nodes, weighted by the size of the intersection of its incidents. The tree
decompositions that h maps to in Proposition 1 correspond to the
maximumweight spanning trees of G [
Corollary 1. There is an algorithm that, given an input graph g, enumerates the proper tree decompositions of g in incremental polynomial time. 4
So far, we have established an algorithm with complexity guarantees for
enumerating the minimal triangulations (and the proper tree decompositions) of
a graph. In the next steps, we plan to investigate the implementation of our
algorithm, in two aspects. The rst is that of e ciency : we plan to nd
techniques for optimizing and parallelising the computation (e.g., in the spirit of
previous algorithms of a similar nature [