2017/04/27 by Pascal Schweitzer, Schweitzer, Pascal
Computer Science · Economics, Econometrics and Finance · #Combinatorics (math.CO) #Data Management and Algorithms #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.1.3 #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1704.08529
openalex publication_date 2017/04/27 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
The paper develops a new technique to extract a characteristic subset from a\nrandom source that repeatedly samples from a set of elements. Here a\ncharacteristic subset is a set that when containing an element contains all\nelements that have the same probability. With this technique at hand the paper\nlooks at the special case of the tournament isomorphism problem that stands in\nthe way towards a polynomial-time algorithm for the graph isomorphism problem.\nNoting that there is a reduction from the automorphism (asymmetry) problem to\nthe isomorphism problem, a reduction in the other direction is nevertheless not\nknown and remains a thorny open problem. Applying the new technique, we develop\na randomized polynomial-time Turing-reduction from the tournament isomorphism\nproblem to the tournament automorphism problem. This is the first such\nreduction for any kind of combinatorial object not known to have a\npolynomial-time solvable isomorphism problem.\n