Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GRAPH ISOMORPHISM:
Reports tagged with Graph Isomorphism:
TR96-054 | 2nd November 1996
Oded Goldreich

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1


The Graph Clustering Problem is parameterized by a sequence
of positive integers, $m_1,...,m_t$.
The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,
and the question is whether the equivalence classes
under the graph isomorphism relation have sizes which match
the sequence of parameters.
In this note
we show ... more >>>


TR98-006 | 27th January 1998
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

The Graph Clustering Problem has a Perfect Zero-Knowledge Proof


The input to the {\em Graph Clustering Problem}\/
consists of a sequence of integers $m_1,...,m_t$
and a sequence of $\sum_{i=1}^{t}m_i$ graphs.
The question is whether the equivalence classes,
under the graph isomorphism relation,
of the input graphs have sizes which match the input sequence of integers.
In this note ... more >>>


TR02-037 | 21st May 2002
Vikraman Arvind, Piyush Kurur

Graph Isomorphism is in SPP

We show that Graph Isomorphism is in the complexity class
SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for
each $k\geq 2$). We derive this result as a corollary of a more
general result: we show that a {\em generic problem} $\FINDGROUP$ has
an $\FP^{\SPP}$ ... more >>>


TR04-121 | 7th December 2004
Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.


In this paper we study the complexity of Bounded Color
Multiplicity Graph Isomorphism (BCGI): the input is a pair of
vertex-colored graphs such that the number of vertices of a given
color in an input graph is bounded by $b$. We show that BCGI is in the
#L hierarchy ... more >>>


TR05-093 | 24th August 2005
Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

Concurrent Zero Knowledge without Complexity Assumptions

We provide <i>unconditional</i> constructions of <i>concurrent</i>
statistical zero-knowledge proofs for a variety of non-trivial
problems (not known to have probabilistic polynomial-time
algorithms). The problems include Graph Isomorphism, Graph
Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a
restricted version of Statistical Difference, and approximate
versions of the (<b>coNP</b> forms of the) Shortest Vector ... more >>>


TR07-068 | 24th July 2007
Thomas Thierauf, Fabian Wagner

The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC^1.

In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>


TR07-071 | 1st August 2007
Jacobo Toran

Reductions to Graph Isomorphism

We show that several reducibility notions coincide when applied to the
Graph Isomorphism (GI) problem. In particular we show that if a set is
many-one logspace reducible to GI, then it is in fact many-one AC^0
reducible to GI. For the case of Turing reducibilities we show that ... more >>>


TR09-053 | 20th May 2009
Johannes Köbler, Sebastian Kuhnert

The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

We show that k-tree isomorphism can be decided in logarithmic
space by giving a logspace canonical labeling algorithm. This improves
over the previous StUL upper bound and matches the lower bound. As a
consequence, the isomorphism, the automorphism, as well as the
canonization problem for k-trees ... more >>>


TR09-093 | 8th October 2009
Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>


TR10-043 | 5th March 2010
Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky

Interval Graphs: Canonical Representation in Logspace

Revisions: 1

We present a logspace algorithm for computing a canonical interval representation and a canonical labeling of interval graphs. As a consequence, the isomorphism and automorphism problems for interval graphs are solvable in logspace.

more >>>

TR11-052 | 4th April 2011
Fabian Wagner

On the Complexity of Group Isomorphism

Revisions: 4 , Comments: 3

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>


TR11-168 | 9th December 2011
Joshua Grochow

Lie algebra conjugacy

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies$AB - BA \in ... more >>>


TR12-078 | 14th June 2012
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

Approximate Graph Isomorphism

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>


TR12-122 | 17th September 2012
Giorgio Ausiello, Francesco Cristiano, Luigi Laura

Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first ... more >>>


TR13-074 | 9th May 2013
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Helly Circular-Arc Graph Isomorphism is in Logspace

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>


TR14-068 | 5th May 2014
Eric Allender, Bireswar Das

Zero Knowledge and Circuit Minimization

Revisions: 1

We show that every problem in the complexity class SZK (Statistical Zero Knowledge) is
efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RP^MCSP.

This is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these ... more >>>


TR14-070 | 14th May 2014
Vikraman Arvind, Gaurav Rattan

The Complexity of Geometric Graph Isomorphism

We study the complexity of Geometric Graph Isomorphism, in
$l_2$ and other $l_p$ metrics: given two sets of $n$ points $A,
B\subset \mathbb{Q}^k$ in
$k$-dimensional euclidean space the problem is to
decide if there is a bijection $\pi:A \rightarrow B$ such that for
... more >>>


TR14-111 | 15th August 2014
Vikraman Arvind, Gaurav Rattan

Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous
best running time bound of $O^*(2^{O(k^2/\log
k)})$.

more >>>

TR15-032 | 21st February 2015
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky

Graph Isomorphism, Color Refinement, and Compactness

Revisions: 2

Color refinement is a classical technique used to show that two given graphs $G$ and $H$
are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph $G$ amenable to color refinement if the color-refinement procedure succeeds in distinguishing $G$ from any non-isomorphic ... more >>>


TR15-162 | 9th October 2015
Eric Allender, Joshua Grochow, Cris Moore

Graph Isomorphism and Circuit Size

Revisions: 1

We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied ... more >>>


TR17-158 | 23rd October 2017
Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

Minimum Circuit Size, Graph Isomorphism, and Related Problems

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>>


TR20-118 | 5th August 2020
Oded Goldreich

On Testing Asymmetry in the Bounded Degree Graph Model

Revisions: 4

We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of $n$-vertex graphs with connected components ... more >>>


TR20-158 | 26th October 2020
Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>


TR21-097 | 7th July 2021
Jacobo Toran, Florian Wörz

Number of Variables for Graph Identification and the Resolution of GI Formulas

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>


TR24-004 | 7th January 2024
Omkar Baraskar, Agrim Dewan, Chandan Saha

Testing equivalence to design polynomials

An $n$-variate polynomial $g$ of degree $d$ is a $(n,d,t)$ design polynomial if the degree of the gcd of every pair of monomials of $g$ is at most $t-1$. The power symmetric polynomial $\mathrm{PSym}_{n,d} := \sum_{i=1}^{n} x^d_i$ and the sum-product polynomial $\mathrm{SP}_{s,d} := \sum_{i=1}^{s}\prod_{j=1}^{d} x_{i,j}$ are instances of design polynomials ... more >>>




ISSN 1433-8092 | Imprint