## 5 Theoretical and bibliographical background
### Decomposing a graph into atoms  
Decomposition Step 3.1 and Algorithm Atoms of Section 4 are largely inspired from the decomposition of a graph by clique separators described by [PERSON] [15]. [PERSON] considers clique separators instead of clique minimal separators, with the drawback that the set of atoms obtained is not unique (see Subsection 5.4). He also computes a meo of \(G\) and the corresponding minimal triangulation of \(G\), but he selects the vertices that generate a clique separator instead of a clique minimal separator of \(G\). The proof of the clique separator decomposition algorithm given in [15] can easily be modified into a proof of Algorithm Atoms. We will give an idea of this proof.  
**Theorem 5.3**: _Algorithm Atoms computes a clique minimal separator decomposition of input graph \(G\)._  
**Proof:** _(idea of the proof)_ The proof works by induction on \(k=|X^{\prime}|\), where \(X^{\prime}\) is the set of vertices of \(X\) that generate a clique of \(G\) w.r.t. \(\alpha\), _i.e._, the set of vertices of \(G\) that generate a clique minimal separator of \(G\) w.r.t. \(\alpha\). If \(k\) = 0 then the computed decomposition is \(\{G\}\), which is correct since \(G\) has no clique minimal separator. We suppose that the decomposition is correct if \(|X^{\prime}|\leq k\). Let us show that it is still correct if \(|X^{\prime}|=k+1\). Let \(x\) be the first vertex of \(X^{\prime}\) in ordering \(\alpha\), let \(S\) be the clique minimal separator of \(G\) generated by \(x\) w.r.t. \(\alpha\), let \(C\) be the connected component of \(G(V-S)\) containing \(x\), let \(G_{1}=G(S\cup C)\) and \(G_{2}=G(V-C)\). For \(j\) in \(\{1,2\}\), let \(V_{j}\) be the vertex set of \(G_{j}\), let \(\alpha_{j}\) be the restriction of \(\alpha\) to \(V_{j}\), let \(H_{j}=H(V_{j})\) and \(X^{\prime}_{j}=X^{\prime}\cap V_{j}\). It can be shown that for \(j\) in \(\{1,2\}\), \(\alpha_{j}\) is a meo of \(G_{j}\), with \(H_{j}\) as corresponding minimal triangulation of \(G_{j}\). Moreover, each vertex of \(V_{2}\) generates the same set in \(G_{2}\) w.r.t. \(\alpha_{2}\) as in \(G\) w.r.t. \(\alpha\), which is a minimal separator of \(H_{2}\) if and only if it is a minimal separator of \(H\). Hence \(X^{\prime}_{2}\) is exactly the set of vertices of \(G_{2}\) that generate a a clique minimal separator of \(G_{2}\) w.r.t. \(\alpha_{2}\), with \(|X^{\prime}_{2}|\leq k\) since \(X^{\prime}_{2}\subseteq X^{\prime}-\{x\}\). It follows by induction hypothesis that \(G_{2}\) is correctly decomposed. It remains to show that \(G_{1}\) is an atom of \(G\). It can be shown that each vertex of \(C-\{x\}\) precedes \(x\) in ordering \(\alpha\), and generates the same set in \(G_{1}\) w.r.t. \(\alpha_{1}\) as in \(G\) w.r.t. \(\alpha\), which is a minimal separator of \(H_{1}\) if and only if it is a minimal separator of \(H\). As no vertex of \(C-\{x\}\) generatesa clique minimal separator of \(G\) w.r.t. \(\alpha\) (since \(x\) is the first vertex that does), no vertex of \(C-\{x\}\) generates a clique minimal separator of \(G_{1}\) w.r.t. \(\alpha_{1}\) either. Now each vertex of \(S\cup\{x\}\) generates a subset of \(S\), which is not a separator of \(G_{1}\), w.r.t. \(\alpha_{1}\). Hence \(G_{1}\) has no clique minimal separator, and is therefore an atom of \(G\). \(\Box\)