go-v.orgdoi

A note on graph automorphism and smart reductions

Eric Allender, Joshua A. Grochow, Moore, Cristopher, Dieter van Melkebeek, Andrew Morgan · Rutgers University Community Repository (Rutgers University) · 2018

  • DOI 10.7282/00000010
  • Publisher Rutgers, The State University of New Jersey
  • Type article
  • Issued 2018

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

Rutgers University Community Repository (Rutgers University) · Rutgers, The State University of New Jersey · article · 2018

Abstract

It is well-known [KST93] that the complexity of the Graph Automorphism problem is characterized by a special case of Graph Isomorphism, where the input graphs satisfy the " promise " of being rigid (that is, having no nontrivial automorphisms). In this brief note, we observe that the reduction of Graph Automorphism to the Rigid Graph Isomorphism problem can be accomplished even using Grollman and Selman's notion of a " smart reduction " .

Open the resolved locator · 10.7282/00000010

Metadata licence: OpenAlex metadata (CC0)