<p>To complete the answer by Holf, it is claimed here <a href="https://www.sciencedirect.com/science/article/pii/S0166218X0400191X?via%3Dihub" rel="noreferrer">DAM 145(3)</a> that isomorphism is GI-complete in <span class="math-container">$\beta$</span>-acyclic hypergraphs. </p>

CC BY-SA 4.0
2018-12-14T13:49:00.460Z
Holf and M. kanté, many thanks for your answers. Perhaps, in order to make the connection between the paper given by M. kanté and help the readers which are not experts in Graph theory (like me), it should be mentioned that the incidence graph of a beta-acyclic hypergraph is a chordal bipartite graph.
Ioannis Kokkinis
CC BY-SA 4.0
2018-12-14T12:16:47.970Z
2018-12-14T12:16:47.970Z
M. kanté
<p>It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and some other complete problems for deterministic logspace." DIRO, Université de Montréal. 1997)</p>

<p>I would like to know whether something similar is known for the hypergraph isomorphism problem. In that case instead of trees we would have alpha-acyclic hypergraphs (see Characterization 15 on page 20 of <a href="https://arxiv.org/abs/1403.7076" rel="nofollow noreferrer">https://arxiv.org/abs/1403.7076</a> for the definition of alpha acyclicity). </p>

<p>So, I am asking whether some non-trivial complexity bounds for the following problem are known: 
Given two alpha acyclic hypergraphs G and H, is there an isomorphism between G and H?</p>

<p>Of course if something is known for other forms of acyclicity (e.g. beta or gamma) that would be interesting too.</p>

CC BY-SA 4.0
2018-12-12T13:43:48.673Z
I have to think more for other acyclicities but for $\alpha$-acyclicity this is likely as hard as the general case with the usual transformation: if you look for an isomorphism between $G$ and $H$, define $G'$ as $G$ plus the edge $V(G)$. Same with $H'$. Now, both $G'$ and $H'$ are $\alpha$-acyclic. And isomorphisms between $H$ and $G$ are exactly the same as those between $H'$ and $G'$.
holf
CC BY-SA 4.0
2018-12-12T14:09:23.257Z
Of course you are right. However, I have to admit that my motivation for asking this question is that I am interested in acyclic conjunctive query isomorphism (ACQI), of which acyclic hypergraph isomorphism is only a special case. In the case of ACQI the reduction you propose will not work. The reason is that when we deal with conjuctive queries the arity of atoms is usually constant and the number of variables is part of the input. So it is impossible to add a new atom that contains all variables of the conjuctive query. If you agree, perhaps I should generalise my question to ACQI.
Ioannis Kokkinis
CC BY-SA 4.0
2018-12-12T14:13:52.700Z
For bounded arity $k$ then, $\alpha$-acyclicity (and hypertree width $k$) reduces to bounded incidence treewidth. I guess you can adapt https://arxiv.org/abs/1803.06858 to check isomorphism between the incidence graph of your hypergraphs that maps hyperedges on hyperedges.
holf
<cc.complexity-theory><db.databases>
Complexity of Acyclic Hypergraph Isomorphism
Ioannis Kokkinis
# Complexity of Acyclic Hypergraph Isomorphism

(Asked by: username_0 on 2018-12-12)

It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and some other complete problems for deterministic logspace." DIRO, Université de Montréal. 1997)

I would like to know whether something similar is known for the hypergraph isomorphism problem. In that case instead of trees we would have alpha-acyclic hypergraphs (see Characterization 15 on page 20 of <https://arxiv.org/abs/1403.7076> for the definition of alpha acyclicity).

So, I am asking whether some non-trivial complexity bounds for the following problem are known:
Given two alpha acyclic hypergraphs G and H, is there an isomorphism between G and H?

Of course if something is known for other forms of acyclicity (e.g. beta or gamma) that would be interesting too.

**Tags:** cc.complexity-theory, db.databases
> **Comments:**
> **username_1**: I have to think more for other acyclicities but for $\alpha$-acyclicity this is likely as hard as the general case with the usual transformation: if you look for an isomorphism between $G$ and $H$, define $G'$ as $G$ plus the edge $V(G)$. Same with $H'$. Now, both $G'$ and $H'$ are $\alpha$-acyclic. And isomorphisms between $H$ and $G$ are exactly the same as those between $H'$ and $G'$.  
> **username_0**: Of course you are right. However, I have to admit that my motivation for asking this question is that I am interested in acyclic conjunctive query isomorphism (ACQI), of which acyclic hypergraph isomorphism is only a special case. In the case of ACQI the reduction you propose will not work. The reason is that when we deal with conjuctive queries the arity of atoms is usually constant and the number of variables is part of the input. So it is impossible to add a new atom that contains all variables of the conjuctive query. If you agree, perhaps I should generalise my question to ACQI.  
> **username_1**: For bounded arity $k$ then, $\alpha$-acyclicity (and hypertree width $k$) reduces to bounded incidence treewidth. I guess you can adapt https://arxiv.org/abs/1803.06858 to check isomorphism between the incidence graph of your hypergraphs that maps hyperedges on hyperedges.  

---

## 1 answers

### Answer by username_2 on 2018-12-14. Score: 5 | Accepted answer

To complete the answer by Holf, it is claimed here [DAM 145(3)](https://www.sciencedirect.com/science/article/pii/S0166218X0400191X?via%3Dihub) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.

> **Comments:**
> **username_0**: Holf and M. kanté, many thanks for your answers. Perhaps, in order to make the connection between the paper given by M. kanté and help the readers which are not experts in Graph theory (like me), it should be mentioned that the incidence graph of a beta-acyclic hypergraph is a chordal bipartite graph.  

---

