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

DOI10.4230/LIPICS.ICALP.2017.66zbMATH Open1441.68196arXiv1704.08529MaRDI QIDQ5111397FDOQ5111397

Authors: P. Schweitzer 

Publication date: 27 May 2020

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.

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

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

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)

Cited In (5)

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

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)