Isomorphism and canonization of tournaments and hypertournaments

摘要

We give a polynomial-time oracle algorithm for Tournament Canonization that accesses oracles for Tournament Isomorphism and Rigid-Tournament Canonization. Extending the Babai–Luks Tournament Canonization algorithm (Babai and Luks (1983) [4]), we give an nO(k2+logn) algorithm for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyperedges.