Computing the atom graph of a graph and the union
join graph of a hypergraph

arXiv:1607.02911v1 [] 11 Jul 2016

Anne Berry∗

Geneviève Simonet§

January 19, 2018

Abstract
The atom graph of a graph is the graph whose vertices are the atoms obtained
by clique minimal separator decomposition of this graph, and whose edges are the
edges of all possible atom trees of this graph. We provide two efficient algorithms for
computing this atom graph, with a complexity in O(min(nα log n, nm, n(n+m)) time,
which is no more than the complexity of computing the atoms in the general case. We
extend our results to α-acyclic hypergraphs. We introduce the notion of union join
graph, which is the union of all possible join trees; we apply our algorithms for atom
graphs to efficiently compute union join graphs.
Keywords: clique separator decomposition, atom tree, atom graph, clique tree,
clique graph, α-acyclic hypergraph.

1

Introduction

Decomposition by clique minimal separators (into subgraphs called atoms) was introduced
by Tarjan [29] in 1985 as a useful hole- and antihole-preserving decomposition. It turns out
that this decomposition is unique when clique minimal separators are used [24].
This decomposition has given rise to recent interest, both in the general case [4, 5, 15, 24]
and for special graph classes [2, 6, 10, 11, 12, 13]. Applications have arisen in the fields of
databases [26], text mining [7] and biology [22, 23].
Recently, [5] introduced the concept of atom tree, which organizes the atoms of the
clique minimal separator decomposition into a tree as a generalization of the clique tree for
chordal graphs: the nodes are the atoms, and the edges correspond to the clique minimal
separators of the graph. However, as is the case for the clique tree, the atom tree is not
∗
§

LIMOS UMR CNRS 6158, Ensemble Scientifique des Cézeaux, F-63 173 Aubière, France, berry@isima.fr
LIRMM, 161 Rue Ada, F-34392 Montpellier, France, genevieve.simonet@univ-montp2.fr

1

uniquely defined. This can be a problem for instance with the promising use of an atom
tree as a visualization tool.
In this paper, we focus on the atom graph, whose vertices are the atoms, and whose
edges are those of all possible atom trees.
Atom graphs have been used in several papers.
In the general case, the notion of atom graph was introduced in 2007 in [23] in the
context of visualizing biological clusters. An efficient construction algorithm was proposed
in 2010 in [3].
In the case of chordal graphs, the atoms are the maximal cliques and the atom trees are
the clique trees. A related graph which has been extensively studied in this context is the
clique graph (see e.g. [1, 28]), which is the intersection graph of the maximal cliques. The
weighted clique graph of a chordal graph has been used to construct a clique tree [8, 18]: any
maximum weight spanning tree is a clique tree, and vice-versa. Thus, except for some very
special cases, the atom graph is a proper subgraph of the clique graph. In the context of
efficiently constructing a clique tree, in 1991 [8] studied the family of all possible clique trees,
an object very close to the atom graph of a chordal graph. In 1995, [17] used the weighted
atom graph of a chordal graph, but misguidedly called this object the ’clique graph’. In
2012 in [19], this object is further studied and called the ’reduced clique graph’.
Our first goal in this paper is to propose efficient algorithms to compute the atom graph,
both in the general case and in the case of chordal graphs.
Given a graph, all known algorithms for computing the decomposition into atoms first
compute a minimal triangulation of the graph [4, 5, 24], with the exception of some special
graph classes [2, 6]. A minimal triangulation can be computed in O(min(nα log n, nm, n(n+
m))) time where α is the real number such that O(nα ) is the best known time complexity
for matrix multiplication and m is the number of edges of the complement of G [5, 20, 27].
From this minimal triangulation, an atom tree can be computed in O(min(nα , nm, n(n+t)))
time [5, 15, 24], where t is the number of 2-pairs of the minimal triangulation, and thus
t ≤ m. As a result, an atom tree can be computed in O(min(nα log n, nm, n(n + m))) time.
To compute the atom graph efficiently, we present two different approaches. One takes
as input an atom tree as well as the inclusion relation between the separators represented by
its edges, and the other takes as input the weighted intersection graph of the atoms. In both
cases, we provide an O(n2 ) algorithm to compute the atom graph from the input. Our global
complexity when taking the graph itself as input comes to O(min(nα log n, nm, n(n + m)))
time.
We then go on to remark that the atoms of a graph G = (V, E) can be seen as the
hyperedges of an α-acyclic hypergraph, whose vertex set is V , since G has an atom tree that
is a join tree of this hypergraph. However, the atoms of a graph are pairwise non-inclusive,
which is not a requirement for α-acyclic hypergraphs, where a hyperedge can be included
in another. Fortunately, our algorithms also work in this more general context.
We introduce the notion of union join graph, which is the union of all join trees, and
provide algorithms to compute this object efficiently.
2

The paper is organized as follows: Section 2 provides some necessary preliminaries.
Section 3 discusses useful properties of the atom graph. Section 4 presents our algorithms
to compute the atom graph. Section 5 defines the atom hypergraph and relates it to αacyclic hypergraphs. Section 6 discusses how to compute the union join graph of an α-acyclic
hypergraph. We conclude in Section 7.

2

Preliminaries

The graphs considered in this paper are finite and undirected. For a graph G = (V, E),
n = |V | and m = |E|. For any subset X of V , G(X) denotes the subgraph of G induced
by S. For any vertex v of G, NG (v) denotes the neighborhood of v in G: NG (v) = {w ∈
V | vw ∈ E}. We will omit the subscripts when there is no ambiguity. A clique of G is a
set of pairwise adjacent vertices of G, and G is complete if V is a clique of G. The union of
two graphs G1 = (V, E1 ) and G2 = (V, E2 ) is G1 ∪ G2 = (V, E1 ∪ E2 ).
G denotes the complement of G, and m denotes its number of edges. α is the real number
such that O(nα ) is the best known time complexity for matrix multiplication. For any set
V , P(V ) is the power set of V . For any subset A of P(V ), the intersection graph of A is
the graph (A, E) where E is the set of pairs of A whose intersection is non-empty. For each
graph G, K(G) denotes the set of maximal cliques of G and the clique graph of G, is the
intersection graph of K(G). If X and Y are nodes of a tree T , PT (X, Y ) denotes the path
in T between X and Y .
Separation. Let S be a subset of vertices of a connected graph G = (V, E). S is a separator
of G if G(V \ S) is disconnected. For any vertices a and b in V \ S, S is an ab-separator of G
if a and b are in different connected components of G(V \ S). S is a minimal ab-separator if
it is an inclusion-minimal ab-separator, and a minimal separator if there is some pair {a, b}
of vertices such that S is a minimal ab-separator. Given a minimal separator S, C is a full
component of S if C is a connected component of G(V \ S) and NG (C) = S. S is a minimal
separator if S has at least 2 full components, and S is a minimal ab-separator if a and b lie
in 2 different full components of S. Given three subsets S, A and B of V , S is a (minimal)
AB-separator of G if it is a (minimal) ab-separator of G for each a ∈ A and each b ∈ B.
A 2-pair of a connected graph G is a pair {x, y} of non-adjacent vertices such that every
chordless path between x and y is of length 2, or equivalently such that N(x) ∩ N(y) is a
minimal xy-separator of G. The number of 2-pairs of a graph is denoted t, with t ≤ m.
If G is disconnected then a (minimal) (ab-)separator of G is a (minimal) (ab-)separator
of one of its connected components. Thus the set of minimal separators of a graph is the
union of the sets of minimal separators of its connected components, and so it is for its set
of 2-pairs.
Chordal graphs. A graph is chordal, or triangulated, if it has no chordless cycle of length
at least 4. A graph is chordal if and only if all its minimal separators are cliques [16]. A
chordal graph has at most n maximal cliques and the sum of their sizes is bounded by n+m.
A connected graph is chordal if and only if it has a clique tree [14, 18].
3

Definition 2.1 Let G = (V, E) be a connected chordal graph. A clique tree of G is a tree
T = (K(G), ET ) such that for each vertex x of G, the set Kx of nodes of T containing x
induces a subtree of T .
Characterization 2.2 [8] Let G = (V, E) be a connected chordal graph, let T be a clique
tree of G, and let S ⊆ V ; then S is a minimal separator of G if and only if there is an edge
XY of T such that S = X ∩ Y .
If G is a disconnected chordal graph, we associate with G a forest whose connected
components are clique trees of the connected components of G. A clique tree (forest) can
be computed in linear time [8].
Atoms. Atoms are the subgraphs obtained by applying the decomposition by clique minimal separators (see [4] for a survey).
Characterization 2.3 [24] An atom of a graph G = (V, E) is an inclusion-maximal subset
of V inducing a connected subgraph of G with no clique separator.
We will denote the set of atoms of G by A(G).
Property 2.4 The atoms of a chordal graph are its maximal cliques.
Property 2.5 [24] The intersection of two distinct atoms is a clique.
Notation 2.6 For a graph G = (V, E), G+ denotes the graph whose vertex set is V and
whose edges are the pairs of V that are contained in a common atom of G (this graph is
denoted G∗ in [24]).
Property 2.7 [24] For a graph G, G+ is chordal, its maximal cliques are the atoms of G
and for each clique S of G and each pair {a, b} of V \ S, S is an ab-separator (resp. minimal
ab-separator) of G if and only if S is an ab-separator (resp. minimal ab-separator) of G+ .
It follows that a graph has at most n atoms.
Atom trees.
To represent the atoms of a graph, [5] extend the notion of clique tree of a connected
chordal graph to the notion of atom tree of a connected graph:
Definition 2.8 [5] Let G = (V, E) be a connected graph. An atom tree of G is a tree
T = (A(G), ET ) such that for each vertex x of G, the set Ax of nodes of T containing x
induces a subtree of T .

4

•4

A = {1, 2, 3, 4, 5, 6}
5•

3

•
2•

1

6•

B = {1, 2, 3, 7}
•7
C

•

D

10
•
E

9•

•
11
{1, 2, 3}

B

A
{1}
D
{1}

13
•
F

{1, 7}

•
12
{1, 2, 3}

C

E

•8

A

F
{10, 11}

B

{1, 7}

{1}
{1}

D
E

C

F
{10, 11}

Figure 1: A graph G and two atom trees of G.
Note that an atom tree is not a decomposition tree of clique separator decomposition as
defined in [3, 29], thouh this deomposition is called ‘atom tree’ in [3].
An atom tree of a connected graph G can be computed in O(min(nα log n, nm, n(n+m)))
time [5, 15].
The edges of an atom tree of a graph correspond to its clique minimal separators.
Characterization 2.9 [5] Let G = (V, E) be a connected graph, let T be an atom tree of
G, and let S ⊆ V ; then S is a clique minimal separator of G if and only if there is an edge
AB of T such that S = A ∩ B.
Property 2.10 For a connected graph G, the atom trees of G are the clique trees of the
chordal graph G+ (G+ is defined in Notation 2.6).
Example 2.11 Figure 1 shows a graph G and two of its atom trees. The atoms of G
are A = {1, 2, 3, 4, 5, 6}, B = {1, 2, 3, 7}, C = {1, 7, 8}, D = {1, 9}, E = {1, 10, 11} and
F = {10, 11, 12, 13}. Each edge XY of each atom tree is labeled with the associated clique
minimal separator X ∩ Y of G. G has 15 atom trees, which are all the trees obtained from
the forest (A(G), {AB, BC, EF }) by adding 2 edges not containing the node F .
The following properties will be used to compute complexity bounds.
5

Property 2.12 Let G be a connected graph and let A and B be distinct atoms of G. Then
G(A \ B) is connected and A ∩ B ⊆ NG (A \ B).
Proof: By Property 2.5 A ∩ B is a clique of G. A \ B is connected since otherwise
A ∩ B would be a clique separator of G(A). Similarly A ∩ B ⊆ NG (A \ B) since otherwise
A∩NG (A\B) would be a clique ab-separator of G(A) for any a in A\B (which is non-empty
by definition of atoms) and any b in (A ∩ B) \ NG (A \ B). ✷

Property 2.13 The sum of the sizes of the atoms of a graph is bounded by n + m.
Proof: It is sufficient to prove it in the case of a connected graph G. Let T be an atom
tree of G, and let us show by induction on |A| that for each connected subset A of nodes of
T , ΣX∈A |X| ≤ nA + mA , where nA and mA are the numbers of vertices and edges of the
subgraph of G induced by VA = ∪X∈A X. It trivially holds if |A| = 1. We assume that it
holds if |A| = k. Let us show that it holds if |A| = k + 1. Let X1 be a leaf of T (A), let X2 be
the neighbor of X1 in T (A), let S = X1 ∩X2 and let A2 = A\{X1 }. By induction hypothesis
ΣX∈A2 |X| ≤ nA2 +mA2 . As T is an atom tree of G, VA is the disjoint union of X1 \S and VA2 ,
so nA = |X1 \S|+nA2 . By Property 2.12 S ⊆ NG (X1 \S), so mA ≥ |S|+mA2 .. It follows that
ΣX∈A |X| = |X1 |+ΣX∈A2 |X| ≤ (|X1 \S|+|S|)+(nA2 +mA2 ) = (|X1 \S|+nA2 )+(|S|+mA2 ) ≤
nA + mA . ✷

Property 2.14 The sum of the sizes of the sets X ∩ Y for each edge XY of an atom tree
T of a graph is bounded by n + m, and these sets can be computed from T in O(m) time.
Proof: Let T = (A(G), ET ) be an atom tree of G. We consider a rooted directed tree
Tr = (A(G), U) obtained from T by choosing an arbitrary root. Thus ΣXY ∈ET |X ∩ Y | =
Σ(X,Y )∈U |X ∩ Y | ≤ Σ(X,Y )∈U |Y | ≤ ΣY ∈A(G) |Y | ≤ n + m by Property 2.13.
These sets can be computed by searching T and computing X ∩ Y in O(|Y |) time when
reaching Y from its neighbor X, and therefore in O(m) time.by Property 2.13. ✷
α-acyclic hypergraphs. A simple hypergraph, or hypergraph for short, is a structure
H = (V, E), where V is its vertex set and E is a set of non-empty subsets of V , called the
hyperedges of H, whose union is equal to V . A hypergraph is a clutter if the elements of
E are pairwise non-inclusive. Its line graph, denoted by L(H), is the intersection graph
of E. Its 2-section graph, denoted by 2SEC(H), is the graph whose vertex set is V and
whose edges are the pairs of V that are contained in a hyperedge of H. H is connected if
L(H) is connected, or equivalently if 2SEC(H) is connected. We denote by p the number
of hyperedges of a hypergraph. Let (v1 , . . . , vn ) be an ordering of V and let (X1 , . . . , Xp )
be an ordering of E. The incidence matrix of H w.r.t. these orderings is the n × p matrix
M = (mi,j ) such that for each i ∈ [1, n] and each j ∈ [1, p], mi,j = 1 if vi ∈ Xj and 0
otherwise.
6

A join tree of H is a tree T whose node set is E and such that for each vertex x of H,
the set Ex of nodes of T containing x induces a subtree of T , or equivalently, such that for
each pair {X, Y } of E, X ∩ Y is a subset of each node of PT (X, Y ). H is α-acyclic if it has
a join tree.
Property 2.15 Let H = (V, E) be an α-acyclic hypergraph, and let G be the 2-section graph
2SEC(H). Then G is chordal and if moreover H is a clutter then E = K(G) (i.e. the set
E of hyperedges of H is equal to the set K(G) of maximal cliques of G).
It follows that the number of hyperedges of a clutter is bounded by the number of its
vertices since a chordal graph has at most n maximal cliques. The number of hyperedges of
an α-acyclic hypergraph which is not a clutter may be exponential in the number of vertices.
A join tree of a connected α-acyclic hypergraph H = (V, E) can be defined from its
weighted line graph, where weights are defined as follows. The set associated with a pair
{X, Y } of E is X ∩Y , and its weight, denoted by w(XY ), is |X ∩Y |. Let K be a graph whose
node set is E. The weight of K is the sum of the weights of its edges. When considered as
a weighted graph, K is denoted by Kw . Thus Lw (H) denotes the weighted line graph of H.
Characterization 2.16 [9] Let H = (V, E) be an α-acyclic (resp. connected α-acyclic)
hypergraph. Then the join trees of H are the maximum weight spanning trees of the weighted
complete graph on E (resp. of Lw (H)).
In particular the atom trees of a connected graph G are the maximum weight spanning
trees of the weighted intersection graph of the atoms of G, which is proved in the case of
chordal graph in [8] (and extends to any connected graph through the chordal graph G+ by
Property 2.10).

3

Atom graphs

Atom graphs were used in [23] and formally introduced in [3].
Definition 3.1 [3] The atom graph of a graph G, denoted by AG(G), is the graph (A(G), E ′),
where A(G) is the set of atoms and E ′ the set of pairs {A, B} of A(G) such that A ∩ B is
a clique minimal (A \ (B \ A)-separator of G.
Example 3.2 Figure 2 shows the atom graph of the graph G from Figure 1.
In the definition of the atom graph, the word ‘clique’ can be removed by Property 2.5
and the word ‘minimal’ can be removed by Property 2.12, which implies that for each pairs
{A, B} of A(G), each one of A \ B and B \ A is a subset of a full component of A ∩ B.

7

{1, 2, 3}

B

A

{1, 7}
C

D
E

F
{10, 11}

Figure 2: The atom graph of G (the edge labels that are equal to {1} are omitted).
Characterization 3.3 Let G be a connected graph and let A and B be distinct atoms of
G. Then AB is an edge of AG(G) if and only if A ∩ B is an ab-separator of G for some
a ∈ A \ B and some b ∈ B \ A.
The following property immediately follows from Properties 2.4 and 2.7.
Property 3.4 For a connected graph G, the atom graph of G is the atom graph of the
chordal graph G+ (G+ is defined in Notation 2.6).
Characterizations 3.5 and 3.6 below give relationships between the atom graph and the atom
trees. They are both proved for chordal graphs in [17] and also apply to any connected graph
through the chordal graph G+ by Properties 2.4, 2.10 and 3.4.
Characterization 3.5 The atom graph of a connected graph G is the union of all the atom
trees of G.
Characterization 3.6 The atom trees of a connected graph G are the maximum weight
spanning trees of the weighted atom graph of G.
To compute the edges of the atom graph from an atom tree, we will use the following
characterization from [19] for chordal graphs, which also applies to any connected graph
through the chordal graph G+ by Properties 2.4, 2.10 and 3.4.
Characterization 3.7 Let G be a connected graph, let A and B be distinct atoms of G and
let T be an atom tree of G. Then AB is an edge of AG(G) if and only if there is an edge
A′ B ′ on the path PT (A, B) from A to B in the tree T such that A ∩ B = A′ ∩ B ′ .

4

Computing the atom graph

We know that given a connected graph G, an atom tree of G (and therefore the atoms of G)
can be computed in linear time if G is chordal and in O(min(nα log n, nm, n(n + m))) time
8

otherwise. To compute the set of edges of the atom graph of G, a naive algorithm consists in
computing for each pair {A, B} of atoms of G the connected components of G(V \ (A ∩ B))
and determining whether A \ B and B \ A are in different components, which can be done
in O(m) time for each pair {A, B} and therefore in O(n2 m) time globally.
We will improve upon this to obtain a time which is no worse than that of computing
an atom tree.
Our first algorithm starts with an atom tree and the inclusion relation between the
separators represented by the edges, and adds all the extra edges required to construct
the atom graph. Our second algorithm starts with the weighted intersection graph of the
atoms and repeatedly determines the edges of weight k which belong to the atom graph in
decreasing order of k. Both algorithms run in O(n2 ) time given these inputs. When only
the graph is given as input, we obtain a complexity of O(min(nα log n, nm, n(n + m))) time,
as will be detailed in this section.
We introduce the following parameters which will be used in this section and in Section 6:
p denotes the number of atoms of G, s the sum of their sizes and for each atom tree T of G,
s△ (T ) denotes the sum of the symmetrical difference X△Y = (X \ Y ) ∪ (Y \ X) for each
edge XY of T .
Notation 4.1 For each connected graph G, p = |A(G)|, s = ΣX∈A(G) |X|, and for each
atom tree T = (A(G), ET ) of G s△ (T ) = ΣXY ∈ET |X△Y |.
Note that p ≤ n since G has at most n atoms and that s ≤ n + m since the sum of the
sizes of the atoms of G is bounded by n + m by Property 2.13. The parameters p, s and
s△ (T ) are introduced for two reasons. First, they will be used to extend the complexity
results of this section to the context of α-acyclic hypergraphs in Section 6 with appropriate
extensions of the definitions of these parameters. Second, it can lead to a better complexity
for graph classes for which these parameters have specific bounds.
As will be detailed in Section 4.1, we will also need the edge-inclusion relation sub, which
for an atom tree tests for inclusion the separators represented by two edges.
Definition 4.2 Let T = (A, ET ) be tree, with A a subset of P (V ) for some set V . We call
subset relation of T the relation sub in ET defined by : ∀XY, X ′ Y ′ ∈ ET sub(XY, X ′ Y ′ ) ⇔
X ∩ Y ⊆ X ′ ∩ Y ′.
We will show in Sections 4.1 and 4.2 the following complexity result:
Theorem 4.3 The atom graph of a connected graph G can be computed :
a) in O(n2 ) time from either an atom tree of G and its subset relation or the weighted
intersection graph of the atoms of G,
b) in O(min(nα , nm, n(n + m+ ))) time from an atom tree of G,
c) in O(min(nα , nm)) time from the set of atoms of G,
d) in O(min(nα log n, nm, n(n + m))) time from G,
where m+ denotes the number of edges of G+ (G+ is defined in Notation 2.6).
9

For a chordal graph H, the atom graph can thus be computed in O(min(nα , nm, n(n +
m))) time, since in that case G+ = G and an atom tree (clique tree) of G be computed in
linear time.
Other approaches are possible, but with no improvement of the time complexity. For
instance, as the atom trees of a graph G are obtained from the atom trees of a minimal
triangulation H of G by merging the maximal cliques of H into the atoms of G [5], the atom
graph of G is obtained from the atom graph of H by merging the same maximal cliques of
H.
The different items of Theorem 4.3 are detailed in the following results: item a) follows
from Theorem 4.6 and Corollary 4.14, iten b) follows from item c) and Theorem 4.9, item
c) follows from item a) and Proposition 4.15, and iten d) follows from item b) and from the
fact that an atom tree of G can be computed in O(min(nα log n, nm, n(n + m))) time.

4.1

Algorithm Forest Join

Our first algorithm, Forest Join, is based on Characterization 4.4. Given an atom tree T ,
a minimal separator S is represented by one or several edges of T . If we remove these
edges, we obtain a forest. Let us now furthermore shrink this forest by removing the nodes
which do not contain S. Any edge between two nodes of different trees of the resulting
forest will correspond to an edge of the atom graph which also represents S, and all the S
representatives are thus encountered.
To implement this remarkable property, our algorithm processes the edges of the atom
tree one by one, and computes the relevent nodes and edges with the help of relation sub.
Characterization 4.4 Let G be a connected graph, let T be an atom tree of G and let S
be a minimal separator of G. Then the edges of AG(G) associated with S are the pairs of
nodes of T whose endpoints are in different connected components of T (AS ) − ES , where
AS is the set of nodes of T containing S and ES is the set of edges of T associated with S.
Proof: Let {X, Y } be a pair of nodes of T . Let us show that XY is an edge of AG(G)
associated with S if and only if X and Y are in different connected components of T (AS ) −
ES , i.e. by Characterization 3.7 and the fact that T (AS ) is connected, that there is an edge
X ′ Y ′ of PT (X, Y ) such that S = X ∩ Y = X ′ ∩ Y ′ if and only if PT (X, Y ) is a path in T (AS )
having an edge X ′ Y ′ in ES .
⇒: as S = X ∩ Y PT (X, Y ) is a path in T (AS ), and as S = X ′ ∩ Y ′ , X ′ Y ′ is in ES .
⇐: as X and Y are in AS , S ⊆ X ∩ Y . Hence S ⊆ X ∩ Y ⊆ X ′ ∩ Y ′ = S, and therefore
S = X ∩ Y = X ′ ∩ Y ′. ✷
Algorithm Forest Join computes the edges of the atom graph of G according to Characterization 4.4. Given an atom tree T of G and its subset relation sub, it scans the edges
of T and for each edge AB, it computes the set of edges of the atom graph associated with
the minimal separator S associated with AB if it has not be computed yet, i.e. if AB does
not belong to the set of edges computed so far.
10

It calls Algorithm Components which computes the connected components of the forest
T (AS ) − ES defined in Characterization 4.4. The relation sub enables us to compute these
components at no extra cost than a simple tree search: T (AS ) is the subtree of T whose
edges XY are associated with supersets of S, i.e. satisfy sub(AB, XY ), and ES is the set
of edges XY of T associated with S, i.e. such that sub(AB, XY ) and sub(XY, AB).
In Algorithm Components, k is the current number of connected components, C1 , . . . , Ck
are the current components, Queue contains the nodes of T that are reached but not processed yet and for each reached node X, numComp(X) is the index i of the component Ci
containing X and pred(X) is the node of T it has been reached from (and which should not
be processed again).
Algorithm Forest Join
input : An atom tree T = (A, ET ) of a connected graph G and its subset relation
sub.
output: The atom graph of G.
E ′ ← ∅;
foreach AB ∈ ET do
if AB ∈
/ E ′ then
// the edges associated with A ∩ B are not in E ′ yet
CompSet ← Components(T, AB, sub);
foreach {C, C ′ } ⊆ CompSet do
foreach X ∈ C do
foreach Y ∈ C ′ do
Add XY to E ′ ;
return (A, E ′);

Example 4.5 Figure 3 shows an atom tree T of the graph G from Figure 1 and an execution
of Algorithm Forest Join on T and its subset relation. It shows the forest T (AS ) − ES ) for
S = {1}, where the edges of the atom graph associated with S are represented by dotted
lines. For each clique minimal separator S different from {1}, as AS is of size 2, AG(G)
has a unique edge associated with S which is also an edge of T . So AG(G) is obtained from
T by adding the edges associated with {1} that are not already present in T .

Theorem 4.6 Given an atom tree of a connected graph G and its subset relation, Algorithm
Forest Join computes the atom graph of G in O(p2 ) time, and therefore in O(n2 ) time.
Proof: The correctness follows from Characterization 4.4. Let us prove the time complexity. As Algorithm Components runs in O(p) time and is called less than p times, it globally
costs O(p2 ) time. As an edge XY is added to E ′ at most once (when processing the first
edge of T associated with X ∩ Y ), the number of edge additions to E ′ is bounded by p2 .
11

Algorithm Components
input : An atom tree T of an connected graph, an edge AB of T and the subset
relation sub of T .
output: The set of connected component of T (AS ) − ES , where S = A ∩ B, AS is
the set of nodes of T containing S and ES is the set of edges of T associated
with S.
k ← 1; C1 ← {A}; numComp(A) ← 1; Queue ← {A};
while Queue 6= ∅ do
Remove a node X from Queue;
foreach Y ∈ NT (X) do
if (Y 6= pred(X)) ∧ sub(AB, XY ) then
if sub(XY, AB) then
// XY associated with S, begin a new component
k ← k + 1; Ck ← ∅; i ← k;
else
i ← numComp(X);
Add Y to Ci ; numComp(Y ) ← i;
pred(Y ) ← X; Add Y to Queue;
return {C1 , . . . , Ck };
Hence Algorithm Forest Join runs in O(p2 ) time, and therefore in O(n2 ) time since G has
at most n atoms (p ≤ n). ✷
To evaluate the time complexity of computing the atom graph of G from an atom tree
T of G using Algorithm Forest Join, we need the time complexity of computing the subset
relation of T .
Proposition 4.7 Given an atom tree of a connected graph, its subset relation can be computed in O(min(nα , ps)) time, and therefore in O(min(nα , nm)) time.
{1, 2, 3}

B

A
{1}
D
{1}

{1, 7}
C

E
T

F
{10, 11}

B
A

B
C

D

A

C

D

F

E

E

S = {1}

AG(G)

Figure 3: An execution of Algorithm Forest Join.
12

Proof: It follows from the proof of Property 2.14 that the sets X ∩ Y for each edge of T
can be computed in O(s) time. and that the sum of their sizes is bounded by s. As the
inclusion of X ∩ Y in X ′ ∩ Y ′ or not can be determined in O(|X ∩ Y |) time, the subset
relation can be computed in O(s + ps) time, i.e. in O(ps) time.
Alternatively, as sub(XY, X ′Y ′ ) is equivalent to |X ∩ Y | = |(X ∩ Y ) ∩ (X ′ ∩ Y ′ )|, it can be
evaluated in O(1) time, and therefore in O(p2 ) time globally, provided that the values of
|X ∩ Y | and |(X ∩ Y ) ∩ (X ′ ∩ Y ′ )| have been pre-computed. The values of X ∩ Y and |X ∩ Y |
for each edge XY of T can be computed in O(s) time, and the values of |(X ∩Y ) ∩(X ′ ∩Y ′ )|
in O((n + p)α) time since they are the elements of the product of the transpose of M by M,
where M is the n × (p − 1) incidence matrix of the (possibly non-simple) hypergraph whose
vertex set is V and whose hyperedges are the sets X ∩ Y for each edge XY of T . Hence
this alternative complexity is in O(p2 + s + (n + p)α ) time, i.e. in O((n + p)α ) time since
p2 ≤ (n + p)2 , s ≤ np ≤ (n + p)2 and 2 ≤ α.
We obtain a complexity in O(min((n + p)α , ps)) time, i.e. in O(min(nα , ps)) time since
p ≤ n and therefore in O(min(nα , nm)) time since s ≤ n + m by Property 2.13 ✷
It follows that the atom graph can be computed from an atom tree in O(min(nα , nm))
time.
We will now discuss using the 2-pairs of the graph G+ defined in Notation 2.6 to obtain
an alternative complexity in O(n(n + m+ )) time, where m+ is the number of edges of the
complement of G+ , through the following lemma.
Lemma 4.8 Let T be atom tree of a connected graph. Then s△ (T ) ≤ n + t, where t is the
number of 2-pairs of G+ .
Proof: We consider a rooted directed tree Tr = (A(G), U) obtained from T by choosing
an arbitrary root. Thus ΣXY ∈ET |X△Y | = Σ(X,Y )∈U |X△Y |. Σ(X,Y )∈U |Y \ X| ≤ n since each
vertex x of G belongs to Y \ X for at most one edge of Tr , namely the edge (X, Y ) such that
Y is the root of the subtree of Tr induced by the nodes containing x. Hence it is sufficient
to show that Σ(X,Y )∈U |X \ Y | ≤ t. It is shown in [5] that if G is chordal then this sum is
bounded by the number of 2-pairs of G. So it is bounded by t since G+ is chordal and by
Property 2.10 T is also an atom tree of G+ . ✷

Theorem 4.9 The atom graph of a connected graph G can be computed from an atom tree
T of G in O(p(n + s△ (T ))) time, and therefore in O(n(n + m+ )) time, where m+ is the
number of edges of the complement of G+ .
Proof: We consider the variant of Algorithm Forest Join where the subset relation sub is
not given as an input and ”sub(AB, XY )” and ”sub(XY, AB)” in Algorithm Components
are replaced as follows. Condition sub(XY, AB) can be replaced by |A ∩ B| = |X ∩ Y |
since in the algorithm XY satisfies sub(AB, XY ). The values of |X ∩ Y | for each edge XY
of T can be pre-computed in O(np) time. Let S = A ∩ B. As S is a subset of X in the
13

algorithm, condition sub(AB, XY ) is equivalent to (X \ Y ) ∩ S = ∅, which can be evaluated
in O(|X \Y |) time, provided that the sets X ∩Y , X \Y and Y \X for each edge XY of T have
been pre-computed, which can be done in O(np) time. Thus we add to the time complexity
of Algorithm Forest Join in O(p2 ) a pre-computation time in O(np) and O(s△ (T )) time per
call to Components. We obtain a time complexity in O(p2 + np + p ∗ s△ (T )), and therefore
in O(p(n + s△ (T ))) since p − 1 ≤ s△ (T ) (because the nodes of T are pairwise distinct). We
conclude with Lemma 4.8 ✷
The 2-pairs of a chordal graph are closely related to its atom graph.
Characterization 4.10 Let G be a connected chordal graph, and let {x, y} be a pair of
vertices of G. Then xy is a 2-pair of G if and only if there is an edge KL of AG(G) such
that x ∈ K \ L and y ∈ L \ K.
Proof: ⇒: let S = N(x) ∩ N(y). As S is a minimal separator of G and G is chordal,
S is a clique. Let K (resp. L) be a maximal clique containing {x} ∪ S (resp. {y} ∪ S).
S ⊆ K ∩ L ⊆ (N(x) ∪ {x}) ∩ (N(y) ∪ {y}) = N(x) ∩ N(y) = S. Hence S = K ∩ L, and
therefore KL is an edge of AG(G) with x ∈ K \ L and y ∈ L \ K.
⇐: let S = K ∩L. As KL is an edge of AG(G), S is a minimal xy-separator. As G is chordal
K and L are cliques, so S ⊆ N(x) ∩ N(y), and as S is an xy-separator N(x) ∩ N(y) ⊆ S.
Hence S = N(x) ∩ N(y), and thereforexy is a 2-pair of G. ✷
It follows that the number of 2-pairs of a connected chordal graph G is bounded by the
sum of the products |K \ L| ∗ |L \ K| for each edge KL of its atom graph. In particular, in a
graph class (of non-necessarily chordal graphs) in which the values of |A\B| (and |B \A|) for
each edge AB of the atom graph are bounded by a given constant, for instance if the sizes
of the atoms are bounded by a constant, the atom graph can be computed from an atom
tree in O(n(n + m′ )) time where m′ is the number of edges of the computed atom graph.
The number of 2-pairs is not equal in general to the sum of the products |K \ L| ∗ |L \ K| for
each edge KL of its atom graph since a 2-pair may be associated with several edges of the
atom graph. Considering the same relation between the 2-pairs and the edges of an atom
tree T of G, a pair {x, y} associated with an edge KL of T is a 2-pair since KL is an edge
of the atom graph, but the converse does not hold. Contrary to the atom graph, {x, y} can
be associated with at most one edge of T , namely the unique edge connecting the subtrees
of T induced by the sets of nodes containing x and y respectively, which are necessarily
disjoint and at distance 1 from each other in T .
This alternative time complexity in O(n(n + m+ )) considers the worst case where Algorithm Components searches the whole tree T , whereas it only searches the set AS and its
neighborhood which may be very small w.r.t. the set of nodes of T . For the same reason, it
may be more efficient in practice to execute Algorithm Forest Join without pre-computing
the subset relation sub and directly evaluate sub(AB, XY ) and sub(XY, AB) when needed.

14

4.2

Algorithm AG-max-weight

Our second algoirithm, AG-max-weight, takes as input the weighted intersection graph of
the atoms (which, in the case of a chordal graph, is the clique graph) and repeatedly adds
the edges of weight k in decreasing order of k.
By Characterization 2.16 the atom trees of a connected graph G are the maximum
weight spanning trees of the weighted intersection graph of the atoms of G. We will present
a general algorithm computing the union of the maximum weight spanning trees of Gw for
each weighted connected graph Gw with natural integer weights on the edges. This general
algorithm called Union-max-weight is inspired from the following algorithm from Kruskal
which computes a minimum weight spanning tree of Gw : initialize graph T ′ as edgeless and
for each edge xy of Gw in increasing order of weight, add xy to T ′ if and only if x and y are in
different connected components of T ′ . As we want to compute a maximum weight spanning
tree, we will process the edges in decreasing order of weight; the algorithm computes each
maximum weight spanning tree of Gw . Thus an edge xy of weight k may be added to T ′ by
this last algorithm if and only if x and y are in different connected components of T ′ just
after processing the edges of weight at least k + 1. These components are independent from
the graph T ′ computed so far by item a) of Lemma 4.11 below.
Lemma 4.11 Let Gw = (V, E, w) be a weighted connected graph with natural integer weights
on the edges, let T be a maximum weight spanning tree of G, let UM be the union of the
maximum weight spanning trees of G and for a natural integer k, let Gk (resp. Tk , UMk )
be the graph whose vertex set is V and whose edges are the edges of G (resp. T , UM) of
weight at least k. Then
a) Gk , Tk and UMk have the same connected components,
b) the edges of UM of weight k are the edges of G of weight k whose endpoints are in
different connected components of UMk+1 .
Proof: a) As each connected component of Tk is a subset of a connected component of
UMk which is itself a subset of a connected component of Gk , it is sufficient to show that
each connected component of Gk is a subset of a connected component of Tk , or equivalently
that for each edge xy of Gk , PT (x, y) is a path in Tk . Let xy be an edge of Gk . For each
edge x′ y ′ of PT (x, y) w(xy) ≤ w(x′ y ′) (otherwise (T − {x′ y ′ }) + {xy} would be a spanning
tree of G of strictly greater weight than T ), so PT (x, y) is a path in Tk .
b) Let xy be an edge of G of weight k. Let us show that xy is an edge of UM if and only if
x and y are in different connected components of UMk+1 . We assume that xy is an edge of
UM. Let T be a maximum weight spanning tree of G such that xy is an edge of T . x and y
are in different connected components of Tk+1 , and therefore of UMk+1 by a). Conversely we
assume that x and y are in different connected components of UMk+1 . Let T be a maximum
weight spanning tree of G. As x and y are in different connected components of Tk+1 , there
is an edge x′ y ′ of PT (x, y) of weight at most k. Then (T − {x′ y ′ }) + {xy} is a maximum
weight spanning tree of G, and therefore xy is an edge of UM. ✷
Item b) of Lemma 4.11 provides an inductive definition of the edges of weight k of the
15

3

B

2

3

B

2

3

B

2

A

C

A

C

A

C

D

F

D

F

D

F

E

2

E

2

E

2

Figure 4: An execution of Algorithm AG-max-weight (the edge labels that are equal to 1
are omitted).
union of the maximum weight spanning trees, and therefore a simple iterative algorithm to
compute them. Thus Algorithm Union-max-weight computes the union of the maximum
weight spanning trees of G by initializing a set F with the empty set and adding to F , for
each weight value k in decreasing order, the edges xy of G of weight k such that x and y
are in different connected components of the graph (V, F ) in its state just after adding the
edges of weight strictly grater than k.
In Algorithm Union-max-weight, k is the current value of weight, the sets Ci are the
connected components of the graph (V, F ) in its state at the beginning of iteration k and for
each vertex x, numComp(x) is the index i of the component Ci containing x. The algorithm
is similar to the “maximum weight” variant of Kruskal’s algorithm, the difference being that
Kruskal’s algorithm considers the connected components of the graph (tree) (V, F ) being
computed in its current state instead of in its state at the beginning of iteration k, and
therefore would update the variables Ci and numCom just after each addition of an edge
to F . It follows that the algorithms and complexity results already published on Kruskal’s
algorithm hold for the computation of the union of the maximum weight spanning trees.
In particular the complexity can be improved by using a sophisticated UNION-FIND data
structure. However, the simple algorithm presented here is sufficient to compute the atom
graph in O(n2 ) time.
Algorithm AG-max-weight
input : The weighted intersection graph IGw of the atoms of a connected graph G.
output: The atom graph of G.
return Union-max-weight(IGw );

Example 4.12 Figure 4 shows the weighted intersection graph of the atoms of the graph G
from Figure 1 and an execution of Algorithm AG-max-weight, i.e. Algorithm Union-maxweight, on this weighted graph. It shows the state of the computed graph before and after
adding the edges of weight 1.

Theorem 4.13 Given a weighted connected graph Gw = (V, E, w) with natural integer
weights on the edges, Algorithm Union-max-weight computes the union of the maximum
16

Algorithm Union-max-weight
input : A weighted connected graph Gw = (V, E, w), with natural integer weights on
the edges
output: The union of the maximum weight spanning trees of Gw .
Compute the maximum weight wmax of an edge of Gw and for each k in [1, wmax ] the
set Ek of edges of Gw of weight k;
i ← 0;
foreach x ∈ V do
i ← i + 1; Ci ← {x}; numComp(x) ← i;
F ← ∅;
foreach k = wmax downto 0 do
foreach xy ∈ Ek do
if numComp(x) 6= numComp(y) then
Add xy to F ;
foreach xy ∈ Ek do
if numComp(x) 6= numComp(y) then
i ← numComp(x); j ← numComp(y); Ci ← Ci ∪ Cj ;
foreach z ∈ Cj do
numComp(z) ← i;
return (V, F );
weight spanning trees of Gw in O(wmax + n2 ) time, where wmax is the maximum weight of
an edge of Gw .
Proof: It follows from Lemma 4.11 that the property P defined below is an invariant of
the main foreach loop, using the notation UMk of this lemma,
P : UMk = (V, F ) and ∀x ∈ V (CnumComp(x) is the connected component of UMk containing
x ∧ ∀y ∈ CnumComp(x) numComp(x) = numComp(y)),
which proves the correctness of the algorithm.
Let us prove its time complexity. wmax and the sets Ek can be computed and scanned in
the internal foreach loops in O(wmax + m) time by storing the elements of Ek at index k
of an array. The first internal foreach loop runs in O(m) time globally, and the second
one in O(n2 ) time globally since merging two connected components is in O(n) time and is
performed n − 1 times. Hence the algorithm runs in O(wmax + n2 ) time. ✷

Corollary 4.14 Given the weighted intersection graph of the atoms of a connected graph G,
Algorithm AG-max-weight computes the atom graph of G in O(n + p2 ) time, and therefore
in O(n2 ) time.
To evaluate the time complexity of computing the atom graph of G from the set of atoms
17

of G using Algorithm AG-max-weight, we need the time complexity of computing the the
weighted intersection graph of the atoms of G.
Proposition 4.15 Given the set of atoms of a connected graph G, the weighted intersection graph of the atoms of G can be computed in O(min(nα , ps)) time, and therefore in
O(min(nα , nm)) time.
Proof: As |X ∩ Y | can be computed in O(|Y |) time, computing |X ∩ Y | for each pair
{X, Y } of atoms of G is in O(ps) time. Alternatively these values can be computed in
O((n + p)α ) time since they are the elements of the product of the transpose of M by M,
where M is the n × p incidence matrix of the hypergraph (V, A(G)) (which will be called
the atom hypergraph of G in Section 5), i.e. in O(nα ) time since p ≤ n. We obtain a
time complexity in O(min(nα , ps)), and therefore in O(min(nα , nm)) since s ≤ n + m by
Property 2.13. ✷
It follows that the atom graph can be computed from the set of atoms in O(min(nα , nm))
time.

5

Atom hypergraph

In this section, we define the atom hypergraph of a graph and relate it to the more general
notion of α-acyclic hypergraph.
Definition 5.1 Let G = (V, E) be a graph. The atom hypergraph of G is the hypergraph
HA (G) = (V, A(G)).
Thus the atom trees of a connected graph are the join trees of its atom hypergraph. We
recall that for each hypergraph H, 2SEC(H) is the graph whose vertex set is the vertex set
of H and whose edges are the pairs of vertices that are contained in a hyperedge of H
Characterization 5.2 An hypergraph is the atom hypergraph of a connected graph if and
only if it is a connected α-acyclic clutter, and in that case it is the atom hypergraph of the
graph 2SEC(H) which is a connected chordal graph.
Proof: The atom hypergraph of a connected graph G is connected (since G is and each edge
of G is contained in an atom of G), α-acyclic (since G has an atom tree) and a clutter (by
definition of atoms). Conversely, if H is a connected α-acyclic clutter then by Property 2.15
it is the atom hypergraph of the graph 2SEC(H) which is chordal, and which is connected
since H is. ✷
Note that if H is the atom hypergraph of G then 2SEC(H) is the graph G+ defined in
Notation 2.6. Thus we refind that G+ is chordal and has the same atoms as G (Property 2.7).
18

Definition 5.3 The union join graph of an α-acyclic hypergraph H, denoted by UJ(H), is
the union of its join trees.
As the atom graph of a connected graph G is the union of its atom trees by Characterizations 3.5, we have the following property.
Property 5.4 The atom graph of a connected graph is the union join graph of its atom
hypergraph.
As a generalization Characterizations 3.7, the union join graph of an α-acyclic hypergraph H can be computed from a join tree of H by the following operation tuj, where tuj
stands for “to union join”.
Definition 5.5 For each join tree T = (E, ET ) of a hypergraph, tuj(T ) is the graph whose
node set is E and whose edges are the pairs {X, Y } of E such that there is an edge X ′ Y ′ of
PT (X, Y ) such that X ∩ Y = X ′ ∩ Y ′ (or equivalently X ′ ∩ Y ′ ⊆ X ∩ Y ).
Characterization 5.6 For each α-acyclic hypergraph H and each join tree T of H, UJ(H) =
tuj(T ).
Proof: Let H = (V, E) and let {X, Y } ⊆ E. Let us show that XY is an edge of UJ(H) if
and only if XY is an edge of tuj(T ).
⇒ : let T ′ be a join tree of H such that XY is an edge of T ′ , and let EX (resp. EY ) be the
connected component of T ′ − {XY } containing X (resp. Y ). As X ∈ EX and Y ∈ EY , there
is an edge X ′ Y ′ of PT (X, Y ) such that X ′ ∈ EX and Y ′ ∈ EY . As T ′ is a join tree and XY
is an edge of PT ′ (X ′ , Y ′ ), X ′ ∩ Y ′ ⊆ X ∩ Y . Hence XY is an edge of tuj(T ).
⇐ : let X ′ Y ′ be an edge of PT (X, Y ) such that X ∩ Y = X ′ ∩ Y ′ , and let T ′ be the graph
(T − {X ′ Y ′ }) + {XY }. T ′ is a tree having the same weight as T (since w(XY ) = w(X ′Y ′ )),
so by Characterization 2.16 T ′ is also a join tree of H, and therefore XY is an edge of
UJ(H). ✷
Thus we refind Characterization 3.7 from Property 5.4 and Characterization 5.6. Conversely, Characterization 5.6 can be deduced from Characterization 3.7 and Property 5.8
below, which shows that any α-acyclic hypergraph is an atom hypergraph up to isomorphism.
Notation 5.7 Let E and E ′ be two sets and let f be a one-to-one mapping from E to E ′ .
For each graph K = (E, EK ), f (K) denotes the graph obtained from K by isomorphism f ,
i.e. f (K) = (E ′ , {f (X)f (Y ), XY ∈ EK }).
Property 5.8 Let H = (V, E) be an α-acyclic hypergraph. Then there is a connected chordal
graph G = (V ′ , EG ) and a one-to-one mapping f from E to A(G) such that :
1) for each tree T = (E, ET ), T is a join tree of H if and only if f (T ) is an atom tree of G,
19

2) AG(G) = f (UJ(H),
3) If H is connected then for each pair {X, Y } of E, f (X) ∩ f (Y ) = X ∩ Y , otherwise there
is an element a of V ′ such that for each pair {X, Y } of E, f (X) ∩ f (Y ) = (X ∩ Y ) + {a},
4) for each join tree T of H, tuj(f (T )) = f (tuj(T )).
Proof: By Characterization 5.2, it is sufficient to find a connected α-acyclic clutter H ′ =
(V ′ , E ′ ) and a one-to-one mapping f from E to E ′ such that : (1) for each tree T = (E, ET ),
T is a join tree of H if and only if f (T ) is a join tree of H ′ , 2) UJ(H ′ ) = f (UJ(H), and
items 3) and 4). Let E ′ be defined from E by adding a new specific element aX to each
element of E which is not inclusion-maximal in E, and adding a new common element a to
each element of E if H is not connected. Let f map each element of E to the element of E ′
obtained from it, let V ′ = ∪X∈E ′ X, and let H ′ = (V ′ , E ′ ). By definition, H ′ is a connected
clutter satisfying 3). As for each added element aX (resp. a) the set of elements of E ′
containing it is reduced to {X} (resp. equal to E ′), H ′ is α-acyclic and satisfies (1). (2)
follows from (1) and 4) follows from 3). ✷
Thus we can deduce from properties of α-acyclic hypergraphs (proved from the definition
of α-acyclicity) properties of atom graphs, and conversely, we can deduce from properties
of atom graphs (proved from properties of the minimal separators of the underlying graph)
properties of general α-acyclic hypergraphs. This double approach helps to increase knowledge in both domains of atom graphs and α-acyclic hypergraphs, as some properties are
easier to see in one of these domains than in the other one.
We point out here the incoherence between the atom graph and the atom hypergraph
of a non-connected graph, which comes from the choice of the definition of separators of
a non-connected graph. For a non-connected α-acyclic hypergraph H, a join tree of H is
defined from the join trees of the connected components of H by adding edges (associated
with the empty set) between these join trees to obtain a tree. We recall that according to the
definition of separators given in this paper, we associate with each non-connected graph the
forest of atom trees of its connected components. An alternative definition of separators,
which is given for instance in [24], would preserve the coherence between the graph and
hypergraph approaches, as well as Characterizations 2.9 and 3.7. It defines a separator in
the same way in a non-connected graph as in a connected one : S is an ab-separator of G if
a and b are in different connected components of G(V \ S). It follows that the empty set is
the unique minimal ab-separator of G if a and b are in different connected components of G.
Thus, according to this alternative definition, an atom tree of a (not necessarily connected)
graph is a join tree of its atom hypergraph, and its atom graph is obtained from the atom
graphs of its connected components by adding all edges between these atom graphs, as is the
case for the union join graph of its atom hypergraph. Thus the results given in Section 4 for
connected graphs extend to any graph when using this alternative definition of separators
and to α-acyclichypergraphs that are not necessarily connected, as will be seen in Section 6.

20

6

Computing the union join graph

Algorithms and complexity results of Section 4 extend to the computation of the union join
graph of an α-acyclic hypergraph. They immediately extend to a connected α-acyclic clutter
H since in that case H is the atom hypergraph of 2SEC(H) by Characterization 5.2. The
algorithms still hold for any α-acyclic hypergraph since the proofs of their correctness do.
It is also the case for the complexity bounds in function of parameters n, p, s and s△ (T )
whose definitions naturally extend to α-acyclic hypergraphs as follows.
Notation 6.1 For each α-acyclic hypergraph H = (V, E), n = |V |, m is the number of
edges of 2SEC(H), m is the number of edges of its complement, p = |E|, s = ΣX∈E |X|, and
for each join tree T = (E, ET ) of H s△ (T ) = ΣXY ∈ET |X△Y |.
We recall that α is the real number such that O(nα ) is the best known time complexity
of matrix multiplication and that the subset relation is defined in Definition 4.2.
Theorem 6.2 The union join graph of an α-acyclic hypergraph H can be computed :
a) in O(p2) time from a join tree of H and either its subset relation or the weighted line
graph of H,
b) in O(n + p2 ) time from the weighted line graph of H,
c) in O(min((n + p)α , ps, p(n + s△ (T )))) time from a join tree T of H,
d) in O(min((n + p)α , ps)) time from H.

Proof: Item a) follows from Theorem 6.3 and Theorem 6.8, item b) follows from Corollary 6.5, item c) follows from item d) and the extension of Theorem 4.9 to α-acyclic hypergraphs, and item d) follows from item b) and Proposition 6.6. ✷
The four results below extend Theorem 4.6, Proposition 4.7, Corollary 4.14 and Proposition 4.15 respectively. The complexity bound nα is replaced by (n + p)α , which is the
original bound appearing in the proofs of the concerned results and has been simplified into
nα since p ≤ n in the case of the atom graph (a graph has at most n atoms).
Theorem 6.3 Given a join tree of an α-acyclic hypergraph H and its subset relation, Algorithm Forest Join computes the union join graph of H in O(p2 ) time.
Proposition 6.4 Given a join tree of an α-acyclic hypergraph, its subset relation can be
computed in O(min((n + p)α , ps)) time.
Corollary 6.5 (of Theorem 4.13) Given the weighted line graph of an α-acyclic hypergraph
H, Algorithm Union-max-weight computes the union join graph of H in O(n + p2 ) time.
Proposition 6.6 Given an α-acyclic hypergraph, its weighted line graph can be computed
in O(min((n + p)α , ps)) time.
21

We present now Algorithm UJ-min-weight, which is an alternative to Algorithm Unionmax-weight computing the union join graph in O(p2) time instead of O(n + p2 ) time, but
requires a join tree of H as input in addition to the weighted line graph of H. This algorithm
obviously computes the atom graph of a connected graph, but Algorithm AG-max-weight
already does it with the same complexity in O(n2) time and less input. The algorithm follows
from Characterization 6.7 below, which is an immediate consequence of the characterization
of UJ(H) as tuj(T ) (Characterization 5.6). The algorithm computes for each pair {X, Y }
of hyperedges of H the minimum weight of an edge of the path in T between Xand Y and
stores it in the variables minW eight(X, Y ) and minW eight(Y, X) to be used later in the
execution.
Characterization 6.7 Let H = (V, E) be an α-acyclic hypergraph, let T be a join tree of
H and let {X, Y } ⊆ E. Then XY is an edge of UJ(H) if and only if its weight is the
minimum weight of an edge of PT (X, Y ).
Proof: Let wmin be the minimum weight of an edge of PT (X, Y ). As X ∩ Y is a subset
of X ′ ∩ Y ′ for each edge X ′ Y ′ of PT (X, Y ) since T is a join tree, w(XY ) ≤ wmin , and
w(XY ) = wmin if and only there is an edge X ′ Y ′ of PT (X, Y ) such that X ∩ Y = X ′ ∩ Y ′ ,
i.e. if and only if XY is an edge of UJ(H) by Characterization 5.6. ✷
Algorithm UJ-min-weight
input : A join tree T = (E, ET ) and the weighted line graph Lw (H) of an α-acyclic
hypergraph H.
output: The union join graph of H.
// in the following, w(e) = 0 if e is a non-edge of Lw (H);
Choose a node X of T ;
Reached ← {X}; Queue ← {X}; E ′ ← ET ;
while Queue 6= ∅ do
Remove a node X from Queue;
foreach Y ∈ NT (X) do
if Y ∈
/ Reached then
minW eight(X, Y ) ← w(XY ); minW eight(Y, X) ← w(XY );
foreach Z ∈ Reached \ {X} do
mw ← min(w(XY ), minW eight(X, Z));
minW eight(Y, Z) ← mw; minW eight(Z, Y ) ← mw;
if mw = w(Y Z) then
Add Y Z to E ′ ;
Add Y to Reached and to Queue;
return (E, E ′);
Theorem 6.8 Given a join tree and the weighted line graph of an α-acyclic hypergraph H,
Algorithm UJ-min-weight computes the union join tree of H in O(p2 ) time.
22

Proof: Correctness follows from the fact that by Characterization 6.7 the following proposition P is clearly an invariant of the main foreach and while loops.
P : ∀{X, Y } ⊆ E, if {X, Y } ⊆ Reached then (minW eight(X, Y ) is the minimum weight of
an edge of PT (X, Y ) ∧ (XY ∈ E ′ ⇔ XY is an edge of UJ(H))) otherwise (XY ∈ E ′ ⇔
XY ∈ ET ).
The algorithm runs in O(p2 ) time, by numbering the elements of E from 1 to p and storing
the values of MinCard(X, Y ) for each (X, Y ) in E 2 such that X 6= Y in an array p × p. ✷
By Characterization 5.2 the complexity bounds in function of n, m and m+ presented
in Section 4 extend to each connected α-acyclic clutter H replacing m+ by m as the graph
G = 2SEC(H) is equal to G+ since it is chordal (Property 2.15). In fact they also hold for
each α-acyclic clutter, replacing m by n + m. This follows from the fact that the bounds of
the parameters p, s and s△ (T ) by functions of n, m and m+ extend to α-acyclic clutters.
Property 6.9 For each α-acyclic clutter H, p ≤ n, s ≤ n + m, and for each join tree T of
H s△ (T ) ≤ n + m.
Proof: By Characterization 5.2 these inequalities hold if H is connected. It can be proved
that they also hold if H is disconnected by checking that the proofs of these inequalities
given in Section 4 still hold. It can also be directly checked as follows. Let H1 , . . . , Hk the
connected components of H, and for each i in [1, k] and each variable v let vi be the value
of v in Hi . Then p = Σki=1 pi ≤ Σki=1 ni = n. Similarly s ≤ n + m. For s△ (T ) we have
s△ (T ) = Σki=1 s△ (Ti ) + nb1 , where nb1 = ΣXY ∈ET ,X∩Y =∅ |X| ∗ |Y | and m = Σki=1 mi + nb2 ,
where nb2 = Σ{i,j}⊆[1,k]|Vi | ∗ |Vj |. As nb1 ≤ nb2 , it follows that s△ (T ) ≤ n + m. ✷

Corollary 6.10 The complexity bounds in function of n, m and m+ presented in Section 4
hold for each α-acyclic clutter H, replacing m by n + m and m+ by m.
If H is an α-acyclic hypergraph which is not a clutter, the values of p, n and s△ (T ) may
be exponential in n. It is the case of the hypergraph H = (V, P (V ) \ {∅}), which is α-acyclic
since V is a hyperedge of H (the tree whose edges are the pairs of hyperedges containing V
is a join tree of H).

7

Conclusion

In this paper, we provide two efficient algorithms to compute the atom graph of a graph,
and extend them to compute the union join graph of an α- acyclic hypergraph.
Our algorithms, in the general case, compute the atom graph at no extra cost than
computing the atoms.
It would be interesting to explore the class of graphs which are isomorphic to atom
graphs, and to provide a recognition algorithm for this class.
23

Conflict of interest
The authors declare no conflict of interest.

References
[1] L. Alcón, L. Faria, C. M. H. De Figueiredo, and M. Gutierez. The complexity of clique
graph recognition. Theor. Comput. Sci., 410(21-23): 2072–2083, 2009.
[2] A. Berry, A. Brandstädt , V. Giakoumakis, F. Maffray. Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds. Discrete Applied Math.,
184:50-61, 2015.
[3] A. Berry, R. Pogorelcnik, and G. Simonet. Efficient clique decomposition of a graph
into its atom graph. hal-00678702, 2010.
[4] A. Berry, R. Pogorelcnik, and G. Simonet. An introduction to clique minimal separator
decomposition. J. Algorithms, 3(2):197–215, 2010.
[5] A. Berry, R. Pogorelcnik, and G. Simonet. Organizing the atoms of the clique separator
decomposition into an atom tree. Discrete Applied Mathematics, 177: 1–13, 2014.
[6] A. Berry and A. Wagler. Triangulation and clique separator decomposition of claw-free
graphs. LNCS, Lecture Notes in Computer Science, 7551 (2012) 7-21 (WG 2012).
[7] M. D. Biha, B. Kaba, M.-J. Meurs, and E. SanJuan. Graph decomposition approaches
for terminology graphs. MICAI 2007, Lecture Notes in Computer Science , 4827: 883–
893, 2007.
[8] J. R. S. Blair and B. W. Peyton. An introduction to chordal graphs and clique trees.
Graph Theory and Sparse Matrix Computation, 56:1–29, 1993.
[9] A. Brandstädt and F. F. Dragan. Tree-Structured Graphs In Handbook of Graph
Theory, Combinatorial Optimization, and Algorithms, Chapter 29: 751-812, 2015
[10] A. Brandstädt, V. Giakoumakis, F. Maffray. Clique separator decomposition of holefree and diamond-free graphs and algorithmic consequences. Discrete Appl. Math.,
160:471-478, 2012.
[11] A. Brandstädt, C.T. Hoàng. On clique separators, nearly chordal graphs, and the
Maximum Weight Stable Set Problem. Theoret. Comput. Sci., 389:295-306, 2007.
[12] A. Brandstädt, V.B. Le, S. Mahfud. New applications of clique separator decomposition
for the Maximum Weight Stable Set Problem. Theoret. Comput. Sci., 370:229-239,
2007.
[13] H. Bruhn, A. Saito. Clique or hole in claw-free graphs. Journal of Combinatorial
Theory, Series B, 102(1):1-13, 2012.
24

[14] P. Buneman. A characterization of rigid circuit graphs. Discrete Math., 9:205–212,
1974.
[15] D. Coudert, G. Ducoffe. Clique-decomposition revisited. hal-01266147, 2016.
[16] G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25:71–76, 1961.
[17] P. Galinier, M. Habib, and C. Paul. Chordal.graphs and their clique graphs. Graph
Theoretic Concepts in Computer Science (WG’95), Lecture Notes in Computer Science,
Springer-Verlag, 1017: 358–371, 1995.
[18] F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs.
J. Combin. Theory Ser. B, 16:47–56, 1974.
[19] M. Habib and J. Stacho. Reduced clique graphs of chordal.graphs. European Journal
of Combinatories, 33(5): 712–735, 2012.
[20] P. Heggernes, J. A. Telle, and Y. Villanger. Computing minimal triangulations in time
O(nα log n) = o(n2.376 ). SIAM Journal on Discrete Mathematics, 19(4): 900–913, 2005.
[21] W.-L. Hsu and T.-H. Ma. Substitution decomposition on chordal graphs and its applications. SIAM J. Comput., 28:1004-1020, 1999.
[22] P.-A. Jachiet, R. Pogorelcnik, A. Berry, P. Lopez, E. Bapteste. MosaicFinder: identification of fused gene families in sequence similarity networks. Bioinformatics, 29(7):83744, 2013.
[23] B. Kaba, N. Pinet, G. Lelandais, and A. Berry. Clustering gene expression data using
graph separators. In Silico Biology, 7(0031), 2007.
[24] H.-G. Leimer. Optimal decomposition by clique separators. Discrete Mathematics,
113(1-3): 99–123, 1993.
[25] D. Meister. Recognition and computation of minimal triangulations for AT-free clawfree and co-comparability graphs. Discrete Applied Mathematics, 146(3): 193–218,
2005.
[26] K.G. Olesen and A.L. Madsen. Maximal prime subgraph decomposition of Bayesian networks. IEEE Trans. on Systems, Man and Cybernetics, Part B: Cybernetics 32(1):2131, 2002.
[27] D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination
on graphs. SIAM J. Comput., 5(2): 266–283, 1976.
[28] J. L. Szwarcfiter and C. F. Bornstein. Clique Graphs of Chordal and Path Graphs.
SIAM J. Discrete Math., 7(2): 331–336, 1994.
[29] R. E. Tarjan. Decomposition by clique separators. Discrete Mathematics, 55(2): 221–
232, 1985.

25

