# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight
// in the following, \(w(e)=0\) if \(e\) is a non-edge of \(L_{w}(H)\);  Choose a node \(X\) of \(T\); \(Reached\leftarrow\{X\}\); \(Queue\leftarrow\{X\}\); \(E^{\prime}\gets E_{T}\); whileQueue \(\
eq\emptyset\)do  Remove a node \(X\) from Queue; foreach\(Y\in N_{T}(X)\)do if\(Y\
otin Reached\)then \(minWeight(X,Y)\gets w(XY)\); \(minWeight(Y,X)\gets w(XY)\); foreach\(Z\in Reached\setminus\{X\}\)do \(mw\gets min(w(XY),minWeight(X,Z))\); \(minWeight(Y,Z)\gets mw\); \(minWeight(Z,Y)\gets mw\); if\(mw=w(YZ)\)then  Add \(YZ\) to \(E^{\prime}\);  end if  end for  Add \(Y\) to Reached and to Queue;  end foreach  end foreach  end foreach return \((\mathcal{E},E^{\prime})\);
```

**Algorithm 5**UJ-min-weight. **Theorem 7**. : _Given a join tree and the weighted line graph of an \(\alpha\)-acyclic hypergraph \(H\), the algorithm UJ-min-weight computes the union join tree of \(H\) in \(O(p^{2})\) time._

Proof. : Correctness follows from the fact that by Characterization 13 the following proposition \(P\) is clearly an invariant of the main for each and while loops. \(P\): \(\forall\{X,Y\}\subseteq\mathcal{E}\), if \(\{X,Y\}\subseteq Reached\), then \((minWeight(X,Y)\) is the minimum weight of an edge of \(P_{T}(X,Y)\wedge(XY\in E^{\prime}\Leftrightarrow XY\) is an edge of \(UJ(H)))\); otherwise, \((XY\in E^{\prime}\Leftrightarrow XY\in E_{T})\). The algorithm runs in \(O(p^{2})\) time by numbering the elements of \(\mathcal{E}\) from 1 to \(p\) and storing the values of \(MinCard(X,Y)\) for each \((X,Y)\) in \(\mathcal{E}^{2}\), such that \(X\
eq Y\) in an array \(p\times p\). By Characterization 11, the complexity bounds in function of \(n\), \(m\), and \(\overline{m^{+}}\) presented in Section 4 extend to each connected \(\alpha\)-acyclic clutter \(H\) replacing \(\overline{m^{+}}\) by \(\overline{m}\), as the graph \(G=2 SEC(H)\) is equal to \(G^{+}\). In fact, they also hold for each \(\alpha\)-acyclic clutter, replacing \(m\) by \(n+m\). This follows from the fact that the bounds of the parameters \(p\), \(s\), and \(s_{\triangle}(T)\) by functions of \(n\), \(m\), and \(\overline{m^{+}}\) extend to \(\alpha\)-acyclic clutters. **Property 12**. : _For each \(\alpha\)-acyclic clutter \(H\), \(p\leq n\), \(s\leq n+m\), and for each join tree \(T\) of \(H\), \(s_{\triangle}(T)\leq n+\overline{m}\)._

Proof. : By Characterization 11, 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 \(H_{1},\dots,H_{k}\) the connected components of \(H\), and for each \(i\) in \([1,k]\) and each variable \(v\), let \(v_{i}\) be the value of \(v\) in \(H_{i}\). Then, \(p=\Sigma_{i=1}^{k}p_{i}\leq\Sigma_{i=1}^{k}n_{i}=n\). Similarly, \(s\leq n+m\). For \(s_{\triangle}(T)\), we have \(s_{\triangle}(T)=\Sigma_{i=1}^{k}s_{\triangle}(T_{i})+nb_{1}\), where \(nb_{1}=\Sigma_{XY\in\mathbb{F}_{T},X\cap Y=\varnothing}|X|*|Y|\) and \(\overline{m}=\Sigma_{i=1}^{k}\overline{m_{i}}+nb_{2}\), where \(nb_{2}=\Sigma_{\{i,j\}\leq[1,k]}|V_{i}|*|V_{j}|\). As \(nb_{1}\leq nb_{2}\), it follows that \(s_{\triangle}(T)\leq n+\overline{m}\). Corollary 3: _The complexity bounds in function of \(n\), \(m\) and \(\overline{m^{+}}\) presented in Section 4 hold for each \(\alpha\)-acyclic clutter \(H\), replacing \(m\) by \(n+m\) and \(\overline{m^{+}}\) by \(\overline{m}\)._

If \(H\) is an \(\alpha\)-acyclic hypergraph, which is not a clutter, the values of \(p\), \(n\), and \(s_{\triangle}(T)\) may be exponential in \(n\). It is the case of the hypergraph \(H=(V,P(V)\setminus\{\varnothing\})\), which is \(\alpha\)-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 Conclusions

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 \(\alpha\)-acyclic hypergraph.