5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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'$. $\endgroup$
    – holf
    Commented Dec 12, 2018 at 13:43
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ioannis Kokkinis
    Commented Dec 12, 2018 at 14:09
  • 3
    $\begingroup$ For bounded arity $k$ then, $\alpha$-acyclicity (and hypertree width $k$) reduces to bounded incidence treewidth. I guess you can adapt arxiv.org/abs/1803.06858 to check isomorphism between the incidence graph of your hypergraphs that maps hyperedges on hyperedges. $\endgroup$
    – holf
    Commented Dec 12, 2018 at 14:13

1 Answer 1

Reset to default
5
$\begingroup$

To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Ioannis Kokkinis
    Commented Dec 14, 2018 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.