On 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, we give an n~(O(k+log n)) algorithm for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyperedges.