Listing all potential maximal cliques of a graph.
A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We show here that the potential maximal cliques of a graph can be generated in polynomial time in the number of minimal separators of the graph. Thus, the treewidth and the minimum fill-in are polynomially tractable for all classes of graphs with a polynomial number of minimal separators.
Introduction
The notion of treewidth was introduced at the beginning of the eighties by Robertson and
Seymour [25, 26] in the framework of their graph minor theory. A graph H is a minor of a
graph G if we can obtain H from G by using the following operations: discard a vertex, discard
an edge, merge the endpoints of an edge in a single vertex. Among the deep results obtained
by Robertson and Seymour, we can cite this one: every class of graphs closed by minoration
which does not contain all the planar graphs has bounded treewidth.
A graph is chordal or triangulated if every cycle of length greater or equal to four has a
chord, i.e. edge between two non-consecutive vertices of the cycle. A triangulation of a graph is
a chordal embedding, that is a supergraph, on the same vertex set, which is triangulated. The
treewidth problem is to nd a triangulation such that the size of the biggest clique is as small
as possible. Another closed problem is the minimum ll-in problem. Here we have to nd a
triangulation of the graph such that the number of the added edges is minimum. In both cases
we can restrict to minimal triangulations, i.e. triangulations with a set of edges minimal by
inclusion.
The treewidth and the minimum ll-in play an important role in various areas of computer
science e.g. sparse matrix factorization [27], and algorithmic graph theory [3, 14, 2, 8]. For an
extensive survey of these applications see also [5, 7].
Computing the treewidth is equivalent to nd a tree decomposition, that is a tree such that
each node of the tree is labeled by a vertex set of the graph. The labels of the nodes must
respect some constraints: every vertex of the graph must appear in some label, the endpoints
of an edge must appear in a same label, if a same vertex is in two dierent labels it must be in
all the labels on the unique path of the tree connecting the two occurrences of the vertex. The
width of the tree decomposition is then the size of the largest label minus one, and the treewidth
is the smallest width over all the tree decompositions of the graph. Many graph problems that
model real-life problems are intractable in the sense that they are NP-hard. If we deal with
a class of graphs of bounded treewidth most of these problems become polynomial and even
linear e.g. maximum independent set, hamiltonian circuit or Steiner tree. There are two ways
to solve problems when the treewidth is bounded, the rst uses dynamic programming [5, 16]
and the second is based upon reduction techniques [2, 8].
Unfortunately the computation of the treewidth and of the minimum ll-in of a graph
are NP-hard [1, 30] even for co-bipartite graphs. However, a polynomial time approximation
algorithm with O(log n) performance ratio is described in [9]. The problem of the existence
of a polynomial approximation of the treewidth within a multiplicative constant remains still
open. For any xed constant k, there exist polynomial algorithms nding a tree decomposition
of width at most k if such a decomposition exists. Arnborg et al. [1] gave the rst algorithm
that solves this problem in O(n k+2 ) time. Since numerous improvements have been done on
the domain until the linear time algorithm of Bodlaender [6]. Notice that the constant hidden
by the O notation is doubly exponential in k 2 . Some results for treewidth appeared in the
literature in connection with logic. The works by Arnborg et al. [2], Courcelle [13], Courcelle
and Mosbah [14] led to the conclusion that all the problems which are expressible in extended
monadic second order logic can be solved in linear time for graphs of bounded treewidth.
There exist several classes of graphs with unbounded treewidth for which we can solve
polynomially the problem of the treewidth and the minimum ll-in. Among them there are
the chordal bipartite graphs [19, 12], circle and circular-arc graphs [28, 23], AT-free graphs
with polynomial number of minimal separators [22]. Most of these algorithms use the fact that
these classes of graphs have a polynomial number of minimal separators. It was conjectured in
[17, 18] that the treewidth and the minimum ll-in should be tractable in polynomial time for
all the graphs having a polynomial number of minimal separators. We solve here this ESA'93
conjecture.
The crucial interplay between the minimal separators of a graph and the minimal triangulations
was pointed out by Kloks, Kratsch and M-ller in [21], these results were concluded
in Parra and Scheer [24]. Two minimal separators S and T cross if T intersects two connected
components of GnS, otherwise they are parallel. The result of [24] states that a minimal
triangulation is obtained by considering a maximal set of pairwise parallel separators and by
completing them i.e. by adding all the missing edges inside each separator. However this
characterization gives no algorithmic information about how we should construct a minimal
triangulation in order to minimize the cliquesize or the ll-in.
Trying to solve this later conjecture, we studied in [10, 11] the notion of potential maximal
clique. A vertex set K is a potential maximal clique if it appears as a maximal clique in
some minimal triangulation. In [10], we characterized a potential maximal clique in terms
of the maximal sets of neighbor separators, which are the minimal separators contained in it.
We designed an algorithm which takes as input the graph and the maximal sets of neighbor
separators and which computes the treewidth in polynomial time in the size of the input.
For all the classes mentioned above we can list the maximal sets of neighbor separators in
polynomial time, so we unied all the previous algorithms. Actually, the previous algorithms
compute the maximal sets of neighbor separators in an implicit manner. In [11], we gave a new
characterization of the potential maximal cliques avoiding the minimal separators. This allowed
us to design a new algorithm that, given a graph and its potential maximal cliques, computes
the treewidth and the minimum ll-in in polynomial time. Moreover this approach permitted
us to solve the two problems for a new class of graphs, namely the weakly triangulated graphs.
It was probably the last natural class of graphs with polynomial number of minimal separators
for which the two problems remained open.
This paper is devoted to solve the ESA'93 conjecture, that is the treewidth and the minimum
ll-in are polynomially tractable for the whole class of graphs having a polynomial number of
minimal separators. Recall that if we are able to generate all the potential maximal cliques
of any graph in polynomial time in the number of its minimal separators, then the treewidth
and the minimum ll-in are also computable in polynomial time in the number of minimal
separators. We dene the notion of active separator for a potential maximal clique which leads
to two results. First, the number of potential maximal cliques is polynomially bounded by
the number of minimal separators. Secondly, we are able to enumerate the potential maximal
cliques in polynomial time in their number. These results reinforce our conviction that the
potential maximal cliques are the pertinent objects to study when dealing with treewidth and
minimum ll-in.
Preliminaries
Throughout this paper we consider nite, simple, undirected and connected graphs.
E) be a graph. We will denote by n and m the number of vertices, respectively
the number of edges of G. For a vertex set V 0  V of G, we denote by NG (V 0 ) the neighborhood
of V 0 in GnV 0  so NG
A subset S  V is an a; b-separator for two nonadjacent vertices a; b 2 V if the removal
of S from the graph separates a and b in dierent connected components. S is a minimal
b-separator if no proper subset of S separates a and b. We say that S is a minimal separator
of G if there are two vertices a and b such that S is a minimal a; b-separator. Notice that a
minimal separator can be strictly included in another one. We denote by G the set of all
minimal separators of G.
Let G be a graph and S a minimal separator of G. We note CG (S) the set of connected
components of GnS. A component C 2 CG (S) is a full component associated to S if every vertex
of S is adjacent to some vertex of C, i.e. NG S. The following lemmas (see [15] for a
proof) provide dierent characterizations of a minimal separator:
Lemma 1 A set S of vertices of G is a minimal a; b-separator if and only if a and b are in
dierent full components of S.
G be a graph and S be an a; b-separator of G. Then S is a minimal a; b-separator
if and only if for any vertex x of S there is a path from a to b that intersects S only in x.
If C 2 C(S), we say that is a block associated to S. A block (S; C) is called
full if C is a full component associated to S.
Let now E) be a graph and G an induced subgraph of G. We will compare
the minimal separators of G and G 0 .
Lemma 3 Let G be a graph and V 0  V a vertex set of G. If S is a minimal a; b-separator
of the induced subgraph G there is a minimal a; b-separator T of G such that
Proof. Let is an a; b-separator in G. Let T be any minimal
b-separator contained in S 0 . We have to prove that S  T . Let x be any vertex of S and
suppose that x 62 T . Since S is a minimal a; b-separator of G 0 , we have a path  joining a and
b in G 0 that intersects S only in x (see lemma 2). But  is also a path of G, that avoids T ,
contradicting the fact that T is an a; b-separator. It follows that S  T . Clearly, T \ V 0  S
by construction of T , so T \
The next corollary follows directly from lemma 3.
E) be a graph and a be a vertex of G. Consider the graph G
G[V nfag]. Then for any minimal separator S 0 of G 0 , we have that S or S [ fag is a minimal
separator of G. In particular, jG j  jG 0 j.
3 Potential maximal cliques and maximal sets of neighbor
separators
The potential maximal cliques are the central object of this paper. We present in this section
some known results about the potential maximal cliques of a graph (see also [10, 11, 29]).
Denition 1 A vertex
set
of a graph G is called a potential maximal clique if there is a
minimal triangulation H of G such
that
is a maximal clique of H.
We denote by G the set of potential maximal cliques of the graph G.
A potential maximal
clique
is strongly related to the minimal separators contained
in
.
In particular, any minimal separator of G is contained in some potential maximal clique of G.
The number jG j of potential maximal cliques of G is at least jG j=n.
If K is a vertex set of G, we denote by G (K) the minimal separators of G included in K.
Denition 2 A set S of minimal separators of a graph G is called maximal set of neighbor
separators if there is a potential maximal
clique
of G such that
. We also say that
borders
in G.
We proved in [11] that the potential maximal cliques of a graph are sucient for computing
the treewidth and the minimum ll-in of that graph.
Theorem 1 Given a graph G and its potential maximal cliques G , we can compute the
treewidth and the minimum ll-in of G in O(n 2 jG j  jG
Let now K be a set of vertices of a graph G. We denote by C the connected
components of GnK. We denote by S i (K) the vertices of K adjacent to at least one vertex of
no confusion is possible we will simply speak of C i and S i . If S i
say that C i (K) is a full component associated to K. Finally, we denote by SG (K) the set of
in the graph G, i.e. SG (K) is formed by the neighborhoods, in the graph G, of the
connected components of GnK.
Consider graph E) and a vertex set X  V . We denote by GX the graph obtained
from G by completing X , i.e. by adding an edge between every pair of non-adjacent vertices of
X . If is a set of subsets of V , GX is the graph obtained by completing all
the elements of X .
Theorem 2 Let K  V be a set of vertices. K is a potential maximal clique if and only if :
1. GnK has no full components associated to K.
2. G SG (K) [K] is a clique.
Moreover, if K is a potential maximal clique, then SG (K) is the maximal set of neighbor separators
bordering K, i.e. SG
For example, in gure 1, the vertex sets fb; c; e; gg and fb; d; eg are potential maximal cliques
of the graph of gure 1a and the vertices fx; a potential maximal clique of the graph
of gure 1b.
(a) (b)
z
e
y
f
d
c
a
x

Figure

1: Potential maximal cliques
Remark 1 If K is a potential maximal clique of G, for any pair of vertices x and y of K either
x and y are adjacent in G or they are connected by a path entirely contained in some C i of
GnK except for x and y. The second case comes from the fact that if x and y are not adjacent
in G they must belong to the same S i to ensure that K becomes a clique after the completion
of SG (K). When we will refer to this property we will say that x and y are connected via the
connected component C i .
Remark 2 Consider a minimal separator S contained in a potential maximal
clique
. Let us
compare the connected components of GnS and the connected components of
Gn
(see [11] for
the proofs). The
set
nS is contained in a full component
associated to S. All the other
connected components of GnS are also connected components of
Gn
. Conversely, a connected
component C of
Gn
is either a connected component of GnS (in which case NG (C)  S) or
it is contained in
(in which case NG (C) 6 S).
Remark 3 Unlike the minimal separators, a potential maximal
clique
0 cannot be strictly
included in another potential maximal
clique
. Indeed, for any proper
subset
0 of a potential
maximal
clique
, the
dierence
0 is in a full component associated
to
Theorem 2 leads to a polynomial algorithm that, given a vertex set of a graph G, decides if
K is a potential maximal clique of G.
Corollary 2 Given a vertex set K of a graph G, we can recognize in O(nm) time if K is a
potential maximal clique of G.
Proof. We can compute in linear time the connected components C i of GnK and their neighborhoods
. We can also verify in linear time that GnK has no full components associated to
K.
For each x 2 K, we compute all the vertices y 2 K that are adjacent to x in G or connected
to x via a C i in linear time (we have to search the neighborhood of x and the connected
components C i with x 2 S i ). So we can verify in O(nm) time if K satises the conditions of
theorem 2.
4 Potential maximal cliques and active separators
Theorem 2 tells us that
if
is a potential maximal clique of a graph G,
then
is a clique in
. We will divide the minimal separators of
into two classes: those which create
edges in
, which are called actives, and the others, which are called inactives. More
precisely:
Denition 3
Let
be a potential maximal clique of a graph G and let S
be a minimal
separator of G. We say that S is an active separator
for
if
is not a clique in the graph
nfSg , obtained from G by completing all the minimal separators contained
in
, except
S. Otherwise, S is called inactive
for
.
Proposition 1
Let
be a potential maximal clique of G and S
a minimal separator,
active
for
. Let (S;
) be the block associated to S
containing
and let x; ybe two
non-adjacent vertices of
nfSg .
Then
nS is an minimal x; y-separator in
G[C
Proof. Remark that the vertices x and y, non-adjacent in
nfSg , exist by denition of an
active separator. Moreover, since
is a clique, we must have
Let us prove rst
that
nS is a x; y-separator in the graph G
G[C
that x and y are in a same connected component C xy of G 0
nS). Let
Clearly, C
is a connected component of
Gn
. Let T be the neighborhood of C in G.
By theorem 2, T is a minimal separator of G, contained
in
. By construction of T , we have
. Notice that T 6= S, otherwise S would separate C
and
, contradicting the fact that
(see remark 2). It follows that T is a minimal separator of
, dierent from S
and containing x and y. This contradicts the fact that x and y are not adjacent in
nfSg .
We can conclude
that
nS is an x; y-separator of G 0 .
We prove now
that
nS in a minimal x; y-separator of G 0 . We will show that, for any vertex
znS, there is a path  joining x and y in G 0 and such that
intersects
nS only in z. By
theorem 2, x and z are adjacent in
, so x and z are adjacent in G or they are connected
via a connected component C i of
Gn
. Notice that C i
, then C i will
be contained in some connected component D of GnS, dierent from
. According to remark
2, we would have NG (C i )  NG (D)  S, contradicting z 2 S i . In both cases we have a path  0
from x to z in G 0 , that
intersects
nS only in z.
For the same reasons, z and y are adjacent in G, or there is a connected component C j of
Gn
such that C j
and z; y This gives us a path  00 from z to y in G 0 ,
such that  00
fzg. Remark that C i 6= C j , otherwise we would have a path from x
to y in C i [ fx; yg, contradicting the fact
that
nS separates x and y in G 0 . So the paths  0
and  00 are disjoint except for z, and their concatenation is a path , joining x and y in G 0 and
intersecting
nS only in z. We conclude by lemma 2
that
nS is a minimal separator of G 0 .
By proposition 1, the set T 0
nS is a minimal separator of the subgraph of G induced by
yg. By lemma 3, there is a separator T of G such that T 0  T and T \
deduce:
Theorem 3
Let
be a potential maximal clique and S be a minimal separator, active
for
.
Let (S;
) be the block associated to S
containing
. There is a minimal separator T of G
such
that
It follows easily that the number of potential maximal cliques containing at least one active
separator is polynomially bounded in the number of minimal separators of G. More exactly
number of these potential maximal cliques is bounded by the number of blocks (S;
multiplied
by the number of minimal separators T , so by njG j 2 . Clearly, these potential maximal
cliques have a simple structure and can be computed directly from the minimal separators of
the graph.
Nevertheless, a potential maximal clique may not have active separators. For example
in gure 2, the potential maximal
clique
contains the minimal separators
and fa; c; d 0 g, but no one of them is active
for
. Let us make a
rst observation about the potential maximal cliques containing inactive minimal separators.
d' c'
d c
a
a' b'

Figure

2: Active and inactive separators
Proposition 2
Let
be a potential maximal clique and S
a minimal separator which is
inactive
for
. Let D be the full components associated to S that do not
intersect
.
Then
is a potential maximal clique of the graph Gn [ p
Proof. Let G
. The connected components of G 0
are exactly the connected
components of
Gn
, except for D neighborhoods in G 0 are the same as in
G. It follows that the set SG 0 of the neighborhoods of the connected components of G 0
is exactly
nfSg. Clearly, G 0
has no full components associated
to
. Since S is not
active
for
, we deduce
that
is a clique in G 0
. So, by theorem
2,
is a potential maximal
clique of G 0 .
5 Removing a vertex
E) be a graph and a be a vertex of G. We denote by G 0 the graph obtained from
G by removing a, i.e. G We will show here how to obtain the potential maximal
cliques of G using the minimal separators of G and G 0 and the potential maximal cliques of G 0 .
By corollary 1, we know that G has at least as many minimal separators as G 0 : for any minimal
separator S of G 0 , either S is a minimal separator of G, or S [ fag is a minimal separator of
G. It will follow that the potential maximal cliques of a graph can be computed in polynomial
time in the size of the graph and the number of its minimal separators.
Proposition 3
Let
be a potential maximal clique of G such that a.
Then=
nfag
is either a potential maximal clique of G 0 or a minimal separator of G.
Proof. Let be the connected components of
Gn
and S i be the neighborhood of
C i in G. We denote as usual by
the set of all the S i 's. Remark that the connected
components of G 0
nfag) are exactly C neighborhoods in G 0 are respectively
nfag.
Since
is a clique in G SG
(by theorem 2), it follows
nfag
is a clique in G 0
0 has no full components associated
to
then
0 is a potential
maximal clique of G 0 , according to theorem 2. Suppose now that C 1 is a full component
associated
to
0 in G 0 . Since C 1 is not a full component associated
to
in G, it follows that
Thus,
0 is a minimal separator of G, by theorem 2.
Lemma 4 Let G be a graph and ~
G be any induced subgraph of G. Consider a potential maximal
clique
of ~
G. Suppose that for any connected component C of Gn ~
G, its neighborhood NG (C)
is strictly contained
in
.
Then
is also a potential maximal clique of G.
Proof. Let C be any connected component of Gn ~
G. We denote by ~
V the set of vertices of ~
G.
We want to prove
that
is a potential maximal clique of the graph ~
[C]. Indeed, the
connected components of ~
are the connected components of ~
Gn
plus C. The set S ~
of their neighborhoods consists in fNG (C)g [ S ~
. Since NG (C) is strictly contained
in
~
has no full components associated
to
.
Obviously
is a clique in ~
so
is a
potential maximal clique of ~
G 0 .
The result follows by an easy induction on the number of connected components of Gn ~
G.
Proposition 4
Let
be a potential maximal clique of G such that a. Let C a be the
connected component of
Gn
containing a and let S be the minimal separator
of
such that
If
is not a potential maximal clique of G active
for
. Moreover,
S is not a minimal separator of G 0 .
Proof. Suppose that S is not active
for
. Let D the full components associated to S
in G that do not
intersect
. One of them, say D 1 , is C a . Let G 00 be the graph obtained from G
by removing the vertices of D . According to proposition
2,
is a potential maximal
clique of G 00 . Notice that G 00 is also an induced graph of G 0 . Any connected component C of
contained in some D i , and its neighborhood in G 0 is included in
strictly contained
in
. It follows from lemma 4
that
is a potential maximal clique
of G 0 , contradicting our hypothesis. We deduce that, in the graph G, S is an active separator
for
.
It remains to show that S is not a minimal separator of G 0 . We prove that if S is a minimal
separator of G 0 ,
then
would be a potential maximal clique of G 0 . Let C a be the
connected components of
Gn
and let S neighborhoods in G. Then the
connected components of G 0
are
q , with C 0
C a . Their neighborhoods
in G 0 are respectively S
q , with S 0
In particular, G 0
has no full
component associated
to
and SG 0 contains every element of
, except possibly S.
Suppose that S is a minimal separator of G 0 and let D be a full component associated to S in
dierent from
. By remark 2, D is also a connected component of G 0
, so
is an element of SG 0 . Therefore,
so
is a clique in the graph G 0
We can conclude by theorem 2
that
is a potential maximal clique of G 0 , contradicting our
choice
of
. It follows that S is not a minimal separator of G 0 .
The following theorem, that comes directly from propositions 3 and 4 and theorem 3, shows
us how to obtain the potential maximal cliques of G from the potential maximal cliques of G 0
and the minimal separators of G.
Theorem 4
Let
be a potential maximal clique of G and let G Gnfag. Then one of the
following cases holds:
1.
where
0 is a potential maximal clique of G 0 .
2.
where
0 is a potential maximal clique of G 0 .
3.
is a minimal separator of G.
4.
is a minimal separator of G, C is a connected component of
GnS and T is a minimal separator of G. Moreover, S does not contain a and S is not a
minimal separator of G 0 .
Corollary 3 Let G be a graph, a be a vertex of G and G Gnfag. The number jG j of
potential maximal cliques of G is polynomially bounded in the number jG 0 j of potential maximal
cliques of G 0 , the number jG j of minimal separators of G and the size n of G.
More precisely, jG j  jG
Proof. We will count the potential maximal cliques of the graph G corresponding to each case
of theorem 4.
Notice that for a potential maximal
clique
0 of G 0 , only one
ofand
can be a
potential maximal clique of G: indeed, a potential maximal clique of a graph cannot be strictly
included in another one (see remark 3). So the number of potential maximal cliques of type 1
and 2 of G is bounded by jG 0 j.
The number of potential maximal cliques of type 3 is clearly bounded by jG j.
Let us count now the number of potential maximal cliques of type 4, that can be written as
C). By lemma 3, for any minimal separator S 0 of G 0 , we have that S 0 or S 0 [ fag is a
minimal separator of G. Clearly, the number of minimal separators of G of type S 0 or S 0 [ fag
with is at least jG 0 j. Our minimal separator S does not contain a and is not a
minimal separator of G 0 , so S is not of type S 0 or S 0 [ fag, with S 0 2 G 0 . It follows that the
number of minimal separators S that we can choose is at most jG j jG 0 j. For each minimal
separator S, we have at most n connected components C of GnS and at most jG j separators
T , so the number of potential maximal cliques of type 4 is at most n(jG j jG 0 j)j G j.
Let now a 1 ; a be an arbitrary ordering of the vertices of G. We denote by G i the
graph has a single vertex. By corollary 3 we have that
for any j. Notice that
in particular each graph G i has at most jG j minimal separators. Clearly,
the graph G 1 has a unique potential maximal clique. It follows directly that the graph G has
at most njG cliques.
Proposition 5 The number of the potential maximal cliques of a graph is polynomially bounded
in the number of its minimal separators and in the size of the graph.
More precisely, a graph G has at most njG cliques.
We give now an algorithm computing the potential maximal cliques of a graph. We suppose
that we have a function
IS_PMC(
G), that returns TRUE
if
is a potential maximal clique
of G, FALSE otherwise.
function ONE_MORE_V ERTEX
Input: the graphs G, G 0 and a vertex a such that G
the potential maximal cliques G 0 of G 0 , the minimal separators G 0 , G of G 0 and G.
Output: the potential maximal cliques G of G.
begin
for each
p.m.c.
if
IS_PMC(
f
else
if
IS_PMC(
f
end_if
end_if
end_for
for each minimal separator S 2 G
end_if
if (a 62 S and S 62 G 0 ) then
for each T 2 G
for each full component C associated to S in G
end_if
end_for
end_for
end_if
end_for
return G

Table

1: Computing the p.m.c.'s of G from the p.m.c.'s of G
The function ONE_MORE_V ERTEX of table 1 computes the potential maximal cliques
of a graph G from the potential maximal cliques of a graph G Gnfag. This function is based
theorem 4. The main program, presented in table 2, successively computes the potential
maximal cliques of the graphs G Notice that we can compute the vertex
ordering such that each of the graphs G i is connected.
Theorem 5 The potential maximal cliques of a graph can be listed in polynomial time in its
size and the number of its minimal separators.
More exactly, the potential maximal cliques of a graph are computable in O(n 2 mjG
Proof. Let us analyze the complexity of the algorithm. The sets of vertex sets, like G and G ,
will be represented by trees, in such manner that the adjunction of a new element and testing
that a vertex set belongs to our set will be done in linear time (see for example [20]). We also
know by corollary 2 that a call of the function IS_PMC takes O(nm) time.
We start with the cost of one execution of the function ONE_MORE_V ERTEX .
The cost of the rst for loop is at most j 0
G jnm. But we can strongly reduce this complexity,
using a dierent test for verifying
that
respectively
are potential maximal cliques
main program
Input: a graph G
Output: the potential maximal cliques G of G
begin
let an g be the vertices of G
compute G i+1
end_for

Table

2: Algorithm computing the potential maximal cliques
of G. Suppose that we want to check if a potential maximal
clique
0 of G 0 is also a potential
maximal clique of G. Any connected component C 0 of G 0
0 is contained in some connected
component C of
Gn
and we have NG 0 (C)  NG (C).
Since
0 is a clique in the graph G S G
0 is a clique in the graph G
Therefore, all we have to check is that
Gn
0 has no full
connected components associated
to
0 , which can be done in linear time. Suppose now
thatis a potential maximal clique of G 0 and let us verify
if
[fag is a potential maximal clique
of G. Clearly, the connected components of
Gn
are the same as the connected components
of G 0
. The neighborhood NG (C) of a connected component of
Gn
is either NG 0 (C) or
It follows that
Gn
0 has no full components associated
to
and that any two
vertices x; y0 are adjacent in G SG
. It remains to check that, in the graph G SG
, a is
adjacent to any vertex x0 . This test can be done in linear time: by searching NG (a) and
the connected components C i of
Gn
with a 2 S i , we compute the vertices
of
0 adjacent to a
in G or connected to a via C i . We conclude that the cost of the rst for loop is O(mjG 0 j),
In the second for loop, computing the potential maximal cliques of type 3, i.e. of type
costs O(nmjG time. This is due to the cost of the G calls to function IS_PMC.
Remark that here we could also test in linear time
if
fag is a potential maximal clique
of G. Since S  NG (C) for some connected component of
Gn
(see proof of proposition 3), we
only have to test that
Gn
has no full components associated
to
and that a is adjacent in
G SG
to every x 2 S. Anyway, this will not change the global complexity of the algorithm.
The call to function IS_PMC in the inner loop is done njG j(j G j jG 0 times. Indeed,
we have shown in the proof of corollary 3 that the number of minimal separators S 2 G such
that a 62 S and S 62 G 0 is at most jG j jG 0 j. The number of iteration of the second and
third loop are clearly jG j and respectively n. So the cost of all the calls to function IS_PMC
will be O(n 2 mjG j(j G j jG 0 j).
one execution of the the function ONE_MORE_V ERTEX takes at most O(nmjG
We can compute now the complexity of the main program. Computing the minimal separators
of a graph G can be done in O(n 3 jG time, using the algorithm of Berry, Bordat
and Cogis [4]. If we do this calculus one time for each graph G i , this would take O(n 4 jG j).
But notice that each graph G i is an induced subgraph of G. Consequently, for each minimal
separator S i of G i , there is a minimal separator S of G such that S g. We
can compute rst the minimal separators of the input graph G, in O(n 3 jG time. For computing
the minimal separators of a graph G i , we will take each S 2 G and we will verify if
is a minimal separator of G i . A verication of type can be done
in linear time: it is sucient to test that G i nS i has at least two full components associated to
Therefore, computing the minimal separators of all the graphs G i will not
exceed O(n 3 jG steps.
Remember that the i-th call of the function ONE_MORE_V ERTEX costs at most
time. Using the fact that for all i, jG i j  jG j,
it follows that the n calls of the function ONE_MORE_VERTEX will take O(n 2 mjG
steps.
We conclude that the global complexity of the algorithm is O(n 2 mjG j 2 ).
We deduce directly from theorem 1, proposition 5 and theorem 5:
Theorem 6 The treewidth and the minimum ll-in of a graph can be computed in polynomial
time in the size of the graph and the number of its minimal separators. The complexity of the
algorithm is O(n 3 jG
6 Conclusion
The notion of potential maximal clique seems to be very useful for the study of the treewidth and
the minimum ll-in problems. We proved in [11] that the potential maximal cliques are sucient
for computing the treewidth and the minimum ll-in of a graph. In this paper, we enumerate
the potential maximal cliques in polynomial time in the number of minimum separators of the
input graph. In particular, this gives a polynomial algorithm computing the treewidth and the
minimum ll-in for all the graphs with polynomial number of minimal separators.
A class of graphs may have an exponential number of minimal separators and consequently
an exponential number of potential maximal cliques. Notice that there is no such class of
graphs for which the treewidth problem has been solved in polynomial time, except the graphs
of bounded treewidth. For example, the problem is still open for the planar graphs. We think
that a polynomial number of well-chosen potential maximal cliques could permit to compute
or at least approximate the treewidth for classes of graphs with many minimal separators.



--R

Complexity of
An algebraic theory of graph reduction.
time algorithms for NP-hard problems restricted to partial k-trees
Generating all the minimal separators of a graph.
A tourist guide through treewidth.
A linear-time algorithm for nding tree-decompositions of small treewidth
Algorithmic techniques and results.
Reduction algorithms for constructing solutions of graphs with small treewidth.
Approximating treewidth


Algorithms for maximum matching and minimum
The monadic second-order logic of graphs III: Treewidth
Monadic second-order evaluations on tree-decomposable graphs
Algorithmic Graph Theory and Perfect Graphs.
Dynamic algorithms for graphs of bounded treewidth.
Computing treewidth and minimum
Erratum to the ESA'93 proceedings.
Treewidth of chordal bipartite graphs.
Listing all minimal separators of a graph.
Approximating the bandwidth for asteroidal
On treewidth and minimum


Graphs minors.
Graphs minors.
Triangulating graphs and the elimination process.
Treewidth of circular-arc graphs
Aspects algorithmiques des triangulations minimales des graphes.
Computing the minimum
--TR
Complexity of finding embeddings in a <italic>k</>-tree
time algorithms for NP-hard problems restricted to partial <italic>k</>-trees
The multifrontal method for sparse matrix solution
Monadic second-order evaluations on tree-decomposable graphs
An algebraic theory of graph reduction
Approximating treewidth, pathwidth, frontsize, and shortest elimination tree
Treewidth of Circular-Arc Graphs
Treewidth of chordal bipartite graphs
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
On treewidth and minimum fill-in of asteroidal triple-free graphs
Characterizations and algorithmic applications of chordal graph embeddings
Listing all Minimal Separators of a Graph
All structured programs have small tree width and good register allocation
Minimum fill-in on circle and circular-arc graphs
Linear-time register allocation for a fixed number of registers
Treewidth
Dynamic Algorithms for Graphs of Bounded Treewidth
Algorithms for Maximum Matching and Minimum Fill-in on Chordal Bipartite Graphs
Reduction Algorithms for Constructing Solutions in Graphs with Small Treewidth
Generating All the Minimal Separators of a Graph
Computing Treewidth and Minimum Fill-In
Approximating the Bandwidth for Asteroidal Triple-Free Graphs
Minimal Triangulations for Graphs with "Few" Minimal Separators

--CTR
V. Bouchitt , D. Kratsch , H. Mller , I. Todinca, On treewidth approximations, Discrete Applied Mathematics, v.136 n.2-3, p.183-196, 15 February 2004
treewidth;potential maximal cliques;graph algorithms;minimal separators