Clique partition for an undirected weighted graph

Question

I have an undirected graph and graph edges are weighted. I want to partition the graph into cliques. I don't know the number of cliques in advance.

These are the objectives:

1. Primary objective: The number of cliques should be as small as possible.
2. Secondary objective: For each clique, we calculate the mean edge weight. The sum of these means should be as small as possible.

I'm using a hierarchical approach for comparing solutions: first, I compare the number of cliques between solutions. The solution with fewer cliques is preferred. If two solutions have the same number of cliques, I then look at the sum of edge weights within the cliques, choosing the solution with the smaller sum. This way, the number of cliques is always prioritized as the primary objective, with edge weight minimization serving as a secondary objective when clique count is tied.

The graph structure could be anything. It could be a path. It could be a clique. I have no bounds for clique size or vertex degrees.

While Integer Linear Programming (ILP) could potentially provide an optimal solution, it would likely be too computationally expensive for my case. So, I'm looking for a method that can give a good approximate solution and is scalable.

Answer 1

I think you need to assume additional structure for this problem to be tractable. Is any graph possible? A simple path? Could the whole graph be a clique? Do you have a bound on clique size? On vertex degrees?

In general, finding a maximal clique is not only NP-hard, it's NP-hard to approximate (in your case, you would need to replace edge weights by max_weight minus each weight or something, but I think the principle still applies).

Also, you've given no weight function between the two objectives, so another possible formulation of this would be simply to set all non-zero edges to one and iteratively find maximal cliques.

Answer 2

Not much to optimize here. If your edge weights are positive, then the unique optimal solution is a single clique containing everything.

Here is a proof (for any weighted set, not just graphs). Suppose you have any partition of the set with sums of weights $s_1, s_2, \dots, s_k$ and part sizes $m_1, m_2, \dots, m_k$. The sum of mean weights, which you want to minimize, is $s_1/m_1 + s_2/m_2 + \dots $.

Consider merging the first two parts. The new partition has sum of mean weights $(s_1 + s_2) / (m_1 + m_2) + \dots$.

Everything in $\dots$ remains unchanged. The difference of the two sums is:

$$ \frac {s_1 + s_2} {m_1 + m_2} - \frac {s_1} {m_1} - \frac {s_2} {m_2} = \frac {m_1 m_2 (s_1 + s_2) - s_1 m_2 (m_1+m_2) - s_2 m_1 (m_1+m_2)} {m_1 m_2 (m_1 + m_2)} = \frac {- s_1 m_2^2 - s_2 m_1^2} {m_1 m_2 (m_1 + m_2)} < 0.$$.

So it is always better to merge. We can repeat the merge operation until only one clique remains.