  We investigate the two problems of computing the union join graph as well as
computing the subset graph for acyclic hypergraphs and their subclasses. In the
union join graph $G$ of an acyclic hypergraph $H$, each vertex of $G$
represents a hyperedge of $H$ and two vertices of $G$ are adjacent if there
exits a join tree $T$ for $H$ such that the corresponding hyperedges are
adjacent in $T$. The subset graph of a hypergraph $H$ is a directed graph where
each vertex represents a hyperedge of $H$ and there is a directed edge from a
vertex $u$ to a vertex $v$ if the hyperedge corresponding to $u$ is a subset of
the hyperedge corresponding to $v$.
  For a given hypergraph $H = (V, \mathcal{E})$, let $n = |V|$, $m =
|\mathcal{E}|$, and $N = \sum_{E \in \mathcal{E}} |E|$. We show that, if the
Strong Exponential Time Hypothesis is true, both problems cannot be solved in
$\mathcal{O} \bigl( N^{2 - \varepsilon} \bigr)$ time for $\alpha$-acyclic
hypergraphs and any constant $\varepsilon > 0$, even if the created graph is
sparse. Additionally, we present algorithms that solve both problems in
$\mathcal{O} \bigl( N^2 / \log N + |G| \bigr)$ time for $\alpha$-acyclic
hypergraphs, in $\mathcal{O} \bigl( N \log (n + m) + |G| \bigr)$ time for
$\beta$-acyclic hypergaphs, and in $\mathcal{O} \bigl( N + |G| \bigr)$ time for
$\gamma$-acyclic hypergraphs as well as for interval hypergraphs, where $|G|$
is the size of the computed graph.
