Assume we are given a graph of $N$ vertices $V_1, \ldots, V_N$. For each vertex $V_i$, there is a corresponding weight $v_i$. For a graph of $N$ vertices, we want to find the minimum weight subgraph consisting of disjoint cliques which includes all vertices (that is, all vertices are present in the subgraph and each vertex is exactly in one clique) under two following conditions:
- For each clique (complete subgraph) of the original graph, the weight is defined as the maximum of the weights of the vertices of the clique. More specifically, if vertices $X_1, \ldots, X_k$ form a clique where $x_i$ is the weight of vertex $X_i$, then the weight of this clique is $\max\{x_1,\ldots,x_k \}$.
- The total weight of a subgraph with multiple cliques is the sum of the weights of the cliques.
I want to know whether this problem is NP-complete? Is there any approximation algorithm for this problem which runs in polynomial time of $N$.