# Computing a Clique Tree with the Algorithm Maximal Label Search
## 4 Clique Tree of the Complement Graph  
The algorithm MLS can be used to compute a PEO of the complement graph [11]. We will show that it can be used to compute a PMO, a clique tree and the minimal separators of the complement graph, provided that this complement graph is connected and chordal. **Definition 6**. : _Let \(\mathcal{L}=(L,\preceq,l_{0},\mathit{Inc})\) be a labeling structure. \(\mathcal{L}\) is complement-reversing if for any integers \(i\) and \(n\) with \(1\leq i\leq n\) and any subsets \(I\) and \(I^{\prime}\) of \([i,n]\), if \(\mathit{lab}_{\mathcal{L}}(I)\preceq\mathit{lab}_{\mathcal{L}}(I^{\prime})\), then \(\mathit{lab}_{\mathcal{L}}([i,n]\setminus I^{\prime})\preceq\mathit{lab}_{ \mathcal{L}}([i,n]\setminus I)\)._  
**Remark 2**. : _[_11_]_ _For each \(X\in\{\mathit{MCS},\mathit{LexBFS},\mathit{LexDFS},\mathit{MNS}\}\), \(\mathcal{L}_{X}\) is complement-reversing._  
**Definition 7**. : _For any labeling structure \(\mathcal{L}\), \(\mathit{Rev}(\mathcal{L})\) denotes the labeling structure obtained from \(\mathcal{L}\) by replacing the order on the labels by its dual order._  
Figure 2: LexDFS labels do not detect new maximal cliques. **Theorem 5**. : _[_11_]_ _Let \(\mathcal{L}\) be a complement-reversing labeling structure. Then, an ordering of a graph \(G\) is a \(\mathcal{L}\)-MLS ordering of \(\overline{G}\) if and only if it is a \(\text{Rev}(\mathcal{L})\)-MLS ordering of \(G\)._  
Thus, if \(\mathcal{L}\) is complement-reversing, then replacing \"maximal\" by \"minimal\" in the algorithm MLS results in an algorithm that, with \(G\) and \(\mathcal{L}\) as input, computes a \(\text{Rev}(\mathcal{L})\)-MLS ordering of \(G\) and therefore a \(\mathcal{L}\)-MLS ordering of \(\overline{G}\), which is a PEO of \(\overline{G}\) if it is chordal. However, it is not correct to replace in the algorithm complex-MLS or MLS-CliqueTree condition \"if possible strictly greater than _prev-max-label_\" by \"if possible strictly smaller than _prev-max-label_\" since in the case \(N_{H}^{\alpha+}[x_{i+1}]=N_{H}^{\alpha+}(x_{i})\). With \(H=\overline{G}\), we have \(N_{G}^{\alpha+}(x_{i+1})=N_{G}^{\alpha+}(x_{i})\), i.e., _prev-min-label_\(=label(x)\) at iteration \(i\) (as \(x\) is adjacent to \(x_{i+1}\) in \(H\), it is not adjacent to \(x_{i+1}\) in \(G\), and therefore, its label is not increased during iteration \(i+1\)). We will show that _prev-min-label_\(\
eq label(x)\) is a necessary and sufficient condition for starting a new clique in \(H\), whether the labeling structure is DCL or not. Thus, the algorithm complement-DCL-MLS-CliqueTree (Algorithm 8) detects new cliques on the complement of the input graph by a condition on labels whether the labeling structure is DCL or not. ```
input : a graph \(G\) whose complement is a connected chordal graph and a complement-reversing labeling structure \(\mathcal{L}=(L,\preceq,l_{0},\text{Inc})\) output : a PMO \(\alpha=(x_{1},\ldots,x_{n})\), a clique tree \(T\) and the set \(Sep\) of minimal separators of \(\overline{G}\) \(H\leftarrow\overline{G}\); InitCT;  Initialize all labels as \(l_{0}\); prev-min-label \(\gets l_{0}\); for\(i=n\)down to \(1\)do  Choose a vertex \(x\) in \(V\setminus V^{\prime}\) whose label is minimal, and if possible equal to _prev-min-label_; \(x_{i}\gets x\); \(S\gets N_{H}(x)\cap V^{\prime}\); // \(S=N_{H}^{\alpha+}(x)\) ifprev-min-label \(\
eq label(x)\) and \(i<n\)then StartClique; prev-min-label \(\gets label(x)\);  end for IncreaseClique; foreach\(y\) in \(N_{G}(x)\setminus V^{\prime}\)do \(label(y)\gets Inc(label(y),i)\);  end for \(V^{\prime}\gets V^{\prime}\cup\{x\}\);  end for DefineCT;
```  
**Algorithm 8**complement-DCL-MLS-CliqueTree. Note that as by condition, IC labels can only increase, _prev-min-label_ is necessarily minimal. **Theorem 6**.