I consider a graph $G(V,E)$ and each clique has a general weight. The problem is to find a clique cover that maximizes the sum of the weights of the cliques. That is, I want to select a set of cliques such that all nodes are covered in exactly one clique while the sum of the clique weights is maximized. This can be solved by an integer linear program.
My question is how to show that this problem is NP-hard (or not). I suspect that this problem is NP-hard since the minimum clique cover problem is NP-hard.
https://en.wikipedia.org/wiki/Clique_cover
Note: I have limited knowledge of graph theory and computational complexity.
Best Answer
It is NP-hard. Lets reduce independent set with bounded degree to this problem.
We are given graph $G$ with $n$ vertices and want to know if it has an independent set of size $k$.
For each edge $u-v$ add new vertex $x_{uv}$ and replace this edge with two: $u-x_{uv}$ and $v - x_{uv}$. For each vertex $u$ and it's neighbors $v$ and $v'$ add edge $x_{uv} - x_{uv'}$. This will be our new graph.
Inclusion-maximal cliques in our new graph are of form $\{u\} \cup \{x_{uv} | v \in N(u)\}$. As $G$ has bounded degree, number of cliques will be polynomial (really linear) in $n$.
Lets say that weight of such inclusion-maximal clique is $1$, and weight of any other clique is $0$. Note that for any two vertices $u$, $v$ s.t. there was edge $u-v$ in $G$, in any clique-cover at most one of $u$, $v$ is covered with inclusion-maximal clique. At the other hand, if we have some independent set, we can cover vertices from it with inclusion-maximal cliques (and cover rest however we want, with singletons, for example).
Thus independent sets of size $m$ corresponds to clique-covers with weight $m$, so $G$ has independent size of size $k$ iff our new graph has clique-cover of weight at least $k$.