Skip to main content
Ioannis Kokkinis's user avatar
Ioannis Kokkinis's user avatar
Ioannis Kokkinis's user avatar
Ioannis Kokkinis
  • Member for 8 years
  • Last seen more than 2 years ago
awarded
awarded
awarded
comment
Complexity of Acyclic Hypergraph Isomorphism
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.
accepted
comment
Complexity of Acyclic Hypergraph Isomorphism
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.
awarded
asked
Loading…