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$.
The special case when each vertex weight $v_i$ is equal to $1$ sums up to solving the following problem: partition the vertices into cliques and minimize the number of cliques.
This is known as the Vertex Clique Cover problem (see here). [Edit: it is straightforward to see that Vertex Clique Cover can be reduced to your problem, and so it's NP-hard.]
Unfortunately, as stated on the Wikipedia page, the problem cannot approximated within a $n^{1 - \varepsilon}$ factor, and so there is polytime approximation algorithm achieving a reasonable factor.
If you have structural knowledge of the graph you are studying, that might help (e.g. I think if the degree is bounded, you may be able to approximate something).