Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty and for all $k$. For example, if $K =2$, we have $V_1^{\{2\}}$ and $V_2^{\{1\}}$. if $K =3$, we have $V_1^{\{2,3\}}$, $V_1^{\{2\}}$, $V_1^{\{3\}}$, $V_2^{\{1,3\}}, V_2^{\{1\}}, V_2^{\{3\}}, V_3^{\{1,2\}}, V_3^{\{1\}}, V_3^{\{2\}}$. The weight of vertex $V_k^s$ is denoted by $v_k^s$.
There is an edge between two vertices $V_k^s$ and $V_l^t$, if $k \in t$ and $l \in s$. For example, for $K=3$, there is an edge between $V_1^{\{2,3\}}$ and $V_2^{\{1\}}$, but there is no edge between $V_1^{\{2\}}$ and $V_3^{\{1\}}$.
The resulting graphs for $K=2$ and $K=3$ have been shown in the two following figures. Note that the corresponding graph for $K=k$ have $Q_k = k \times (2^{k-1}-1)$ vertices.
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 \}$. For example, the weight of the following clique is defined as $\max\{v_1^{\{2,3\}},v_2^{\{1,3\}},v_3^{\{1,2\}} \}$. 
Then, the total weight of a subgraph with multiple cliques is the sum of the weights of the cliques. For example, the weight of the following subgraph is $\max\{v_1^{\{2,3\}},v_2^{\{1,3\}},v_3^{\{1,2\}} \}+ \max \{v_1^{\{2\}},v_2^{\{1\}} \} + \max \{v_1^{\{3\}},v_3^{\{1\}} \} +v_2^{\{3\}} + v_3^{\{2\}}$. 
For a given number $K$ and its corresponding graph, 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). Is the following greedy algorithm optimal?
*Assume we have access to an oracle that can say whether a set of vertices can form a clique or not. Now, we sort the vertices based on their weights in decreasing order (the first one has the highest weight) and if two have the same weight we sort them based on the number of edges of them. For example for $K=3$, if all vertices have the same weight, we sort them as $v_1^{\{2,3\}},v_2^{\{1,3\}},v_3^{\{1,2\}}, v_1^{\{2\}},v_1^{\{3\}}, v_2^{\{1\}}, v_2^{\{3\}}, v_3^{\{1\}}, v_3^{\{2\}}$.
Assume the sorted list is $X_1, \ldots, X_9$ where $X_i$ is one of the vertices. Now, we start from the clique $S = X_1$ and check the list $X_2, \ldots, X_9$ from left to right. For each element, we check whether adding $X_j$ to $S$ results in a clique or not. If yes, we form a clique of $S$ and $X_j$, and remove $X_j$ from the list. We continue this process (now for $S = \{X_1,X_j\}$) until we reach the end of list $X_2, \ldots, X_9$. Now we remove the vertices of set S, from $X_1, \ldots, X_9$, and repeat the above procedure for the first element of $X_1, \ldots, X_9$ minus the set $S$.
