__
TR96-054 | 2nd November 1996 00:00
__

#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

**Abstract:**

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 that this problem has a (perfect) zero-knowledge

interactive proof system.

__
Comment #1 to TR96-054 | 2nd February 1998 13:59
__
#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof Comment on: TR96-054.

**Abstract:**

We have posted, as TR98-006, an improvement over TR96-054.

Whereas TR96-054 considers the parametrized

(by sequence of integers) problem,

the new posting refers to the non-parametrized version

where these integers are part of the input.