A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry

DOI10.4230/LIPICS.ICALP.2017.66MaRDI QIDQ5111397zbMATH OpenFDO

Authors P. Schweitzer

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1704.08529

zbMATH Keywords

asymmetrygraph isomorphismtournamentsrandomized reductions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: The paper develops a new technique to extract a characteristic subset from a random source that repeatedly samples from a set of elements. Here a characteristic subset is a set that when containing an element contains all elements that have the same probability. With this technique at hand the paper looks at the special case of the tournament isomorphism problem that stands in the way towards a polynomial-time algorithm for the graph isomorphism problem. Noting that there is a reduction from the automorphism (asymmetry) problem to the isomorphism problem, a reduction in the other direction is nevertheless not known and remains a thorny open problem. Applying the new technique, we develop a randomized polynomial-time Turing-reduction from the tournament isomorphism problem to the tournament automorphism problem. This is the first such reduction for any kind of combinatorial object not known to have a polynomial-time solvable isomorphism problem.

Recommendations

• Hardness Results for Tournament Isomorphism and Automorphism
• Isomorphism and canonization of tournaments and hypertournaments
• On Isomorphism and Canonization of Tournaments and Hypertournaments
• Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments
• Polynomial time recognition and isomorphism testing for cyclic tournaments

Cited in

(5)

• Hardness Results for Tournament Isomorphism and Automorphism
• Algorithmic problems in right-angled Artin groups: complexity and applications
• Polynomial time recognition and testing of isomorphism of cyclic tournaments
• Kernelization of Whitney Switches
• Kernelization of Whitney switches

This page was built for publication: A polynomial-time randomized reduction from tournament isomorphism to tournament asymmetry

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111397)