License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.66
URN: urn:nbn:de:0030-drops-74928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7492/
Go to the corresponding LIPIcs Volume Portal

Schweitzer, Pascal

A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry

pdf-format:
LIPIcs-ICALP-2017-66.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{schweitzer:LIPIcs:2017:7492,
  author =	{Pascal Schweitzer},
  title =	{{A Polynomial-Time Randomized Reduction from Tournament Isomorphism to Tournament Asymmetry}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7492},
  URN =		{urn:nbn:de:0030-drops-74928},
  doi =		{10.4230/LIPIcs.ICALP.2017.66},
  annote =	{Keywords: graph isomorphism, asymmetry, tournaments, randomized reductions}
}

Keywords: graph isomorphism, asymmetry, tournaments, randomized reductions
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI