# Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph
## 4 Computing the Atom Graph
### Algorithm AG-Max-Weight
: _The union join graph of an \(\alpha\)-acyclic hypergraph \(H\) can be computed (a) in \(O(p^{2})\) time from a join tree of \(H\) and either its subset relation or the weighted line graph of \(H\); (b) in \(O(n+p^{2})\) time from the weighted line graph of \(H\); (c) in \(O(min((n+p)^{\omega},ps,p(n+s_{\triangle}(T))))\) time from \(H\), where \(T\) is a join tree of \(H\) (which is computed along with the union join graph of \(H\))._

Proof. : Item a) follows from Theorem 6 and Theorem 7, item b) follows from Corollary 2, item c) follows from item b) and Proposition 4 for the \(O(min((n+p)^{\omega},ps))\) bound, as well as from the extension of Theorem 3 to \(\alpha\)-acyclic hypergraphs and the fact that a join tree can be computed in \(O(s)\) time [27] for the \(O(p(n+s_{\triangle}(T)))\) bound. The four results below extend Theorem 2, Proposition 1, Corollary 1 and Proposition 2, respectively. The complexity bound \(n^{\omega}\) is replaced by \((n+p)^{\omega}\), which is the original bound appearing in the proofs of the concerned results and has been simplified into \(n^{\omega}\) since \(p\leq n\) in the case of the atom graph (a graph has at most \(n\) atoms). **Theorem 6**. : _Given a join tree of an \(\alpha\)-acyclic hypergraph \(H\) and its subset relation, the algorithm Forest join computes the union join graph of \(H\) in \(O(p^{2})\) time._

**Proposition 3**. : _Given a join tree of an \(\alpha\)-acyclic hypergraph, its subset relation can be computed in \(O(min((n+p)^{\omega},ps))\) time._

**Corollary 2**. : _(of Theorem 4) Given the weighted line graph of an \(\alpha\)-acyclic hypergraph \(H\), the algorithm Union-max-weight computes the union join graph of \(H\) in \(O(n+p^{2})\) time._

**Proposition 4**. : _Given an \(\alpha\)-acyclic hypergraph, its weighted line graph can be computed in \(O(min((n+p)^{\omega},ps))\) time._

We present now the algorithm UJ-min-weight (Algorithm 5), which is an alternative to the algorithm Union-max-weight, computing the union join graph in \(O(p^{2})\) time instead of \(O(n+p^{2})\) time but requiring a join tree of \(H\) as input in addition to the weighted line graph of \(H\). This algorithm can obviously be used to compute the atom graph of a connected graph \(G\) from an atom tree and the weighted intersection graph of the atoms of \(G\) in \(O(p^{2})\) time and therefore in \(O(n^{2})\) time, which is already done by the algorithm AG-max-weight with less input. The algorithm follows from Characterization 13 below, which is an immediate consequence of the characterization of \(UJ(H)\) as \(tuj(T)\) (Characterization 12). The algorithm computes for each pair \(\{X,Y\}\) of hyperedges of \(H\) the minimum weight of an edge of the path in \(T\) between \(X\)and \(Y\) and stores it in the variables \(minWeight(X,Y)\) and \(minWeight(Y,X)\) to be used later in the execution. **Characterization 13**. : _Let \(H=(V,\mathcal{E})\) be an \(\alpha\)-acyclic hypergraph, let \(T\) be a join tree of \(H\), and let \(\{X,Y\}\subseteq\mathcal{E}\). Then, \(XY\) is an edge of \(UJ(H)\) if and only if its weight is the minimum weight of an edge of \(P_{T}(X,Y)\)._Proof. : Let \(w_{min}\) be the minimum weight of an edge of \(P_{T}(X,Y)\). As \(X\cap Y\) is a subset of \(X^{\prime}\cap Y^{\prime}\) for each edge \(X^{\prime}Y^{\prime}\) of \(P_{T}(X,Y)\), since \(T\) is a join tree, \(w(XY)\leq w_{min}\), and \(w(XY)=w_{min}\) if and only there is an edge \(X^{\prime}Y^{\prime}\) of \(P_{T}(X,Y)\), such that \(X\cap Y=X^{\prime}\cap Y^{\prime}\), i.e., if and only if \(XY\) is an edge of \(UJ(H)\) by Characterization 12. ```
input : A join tree \(T=(\mathcal{E},E_{T})\) and the weighted line graph \(L_{w}(H)\) of an \(\alpha\)-acyclic hypergraph \(H\). output : The union join graph of \(H\).