Graph Clustering Problem

Graph Clustering Problem --- задача кластеризации графа.

The graph clustering problem (or GCP) is defined as follows:

Input: a sequence [math]\displaystyle{ (G_{1}, \ldots, G_{m}; m_{1}, \ldots, m_{c}) }[/math], where each [math]\displaystyle{ G_{i} }[/math] is an [math]\displaystyle{ n }[/math]-node graph, each [math]\displaystyle{ m_{j} }[/math] is a positive integer, and it holds that [math]\displaystyle{ \sum_{j=1}^{c} m_{j} = m }[/math].

Question: is there a partition [math]\displaystyle{ (C_{1},\ldots, C_{c}) }[/math] of [math]\displaystyle{ \{G_{1},\ldots, G_{m}\} }[/math] such that [math]\displaystyle{ |C_{j}| = m_{j} }[/math], for all [math]\displaystyle{ j\in [1,c] }[/math], and the following properties hold

(1) for any [math]\displaystyle{ i \in [1, c] }[/math] and any [math]\displaystyle{ G_{k}, G_{l} \in C_{i} }[/math], the graphs [math]\displaystyle{ G_{k} }[/math] and [math]\displaystyle{ G_{l} }[/math] are isomorphic;

(2) for any [math]\displaystyle{ i,j \in [1, c] }[/math] such that [math]\displaystyle{ i \neq j }[/math], and any [math]\displaystyle{ G_{k} \in C_{i} }[/math] and [math]\displaystyle{ G_{l} \in C_{j} }[/math], the graphs [math]\displaystyle{ G_{k} }[/math] and [math]\displaystyle{ G_{l} }[/math] are not isomorphic.

Each set [math]\displaystyle{ C_{j} }[/math], [math]\displaystyle{ j \in [1,c] }[/math], will be called a cluster.