Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time
László Babai, Paolo Codenotti · 2008
We give an algorithm to decide isomorphism of hypergraphs of rank k in time exp (Otilde(k2radicn)), where n is the number of vertices. (The rank is the maximum size of edges; the tilde refers to a polylogarithmic factor.) The case of bounded k answers a 24-year-old question and removes an obstacle to improving the worst case-bound for Graph Isomorphism testing. The best previously known bound, even for k = 3, was Cn(Luks 1999).