# Finding a subgraph of cliques with the minimum total sum weight

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$.

• From your description, your graph has only $9$ vertices, so the problem can be solved in constant time by bruce force. Do you really mean this? Commented Jan 4, 2017 at 20:02
• @TonyHuynh Sorry my bad. This is only an example. In this example with 9 vertices, we a number of possible connected components. For this example, we can do brute-force, but for a graph with larger number of vertices, this solution is not practical. Commented Jan 4, 2017 at 20:29
• Your incomplete proof seems correct as far as it goes. But the issue is exactly in the last part you mention. In fact, given a graph this greedy algorithm works (for all weights put on that graph) iff every greedy algorithm works when all the weights are equal. Commented Jan 5, 2017 at 0:22
• @TonyHuynh I updated the question. Do you have any idea for solving it? Commented Jan 6, 2017 at 7:34
• math.stackexchange.com/q/1833883/14578
– D.W.
Commented Jan 9, 2017 at 2:44

Not sure what you mean by saying vertices "can form an acceptable connected component" but no, your greedy algorithm isn't right.

Here are two examples that disprove what you want based on what exactly you're saying (example 2 is probably better).

Example 1: [this might not be a counterexample depending on what you intended your algorithm to do. See example 2 if you aren't happy with this.] As in your example, I'll call the vertices $\{A_1, A_2, A_3, B_1, \ldots, C_3\}$. The graph is the complete graph minus two edges. Namely, we insist $A_1 \not \sim A_2$ and $A_2 \not \sim A_3$. The weights should be $A_1$ has weight 1000, $A_2$ has weight 999, $A_3$ has weight $2$, and all the others have weight 1. If your algorithm picks the heaviest vertex and then grows this by greedily finding the heaviest adjacent vertex (et cetera), then your algorithm with fail on this input.

Example 2: this has 9 vertices (but we only need the four non-isolated vertices). The graph has exactly 3 edges, which are $A_1 \sim B_2 \sim B_1 \sim A_2$. The weights are that $B_1$ and $B_2$ have weight 100, $A_1$ and $A_2$ have weight $99$, and the other vertices have weight 0. The best min-weight decomposition here has weight $200$ but [if yours does anything close to what I think it does] your algorithm will give a weight of $100 + 99 +99$.

Example 3: the greedy algorithm fails for the graph you gave as an example. Let the weights for $A_i$ all be equal to $1.1$, and let all the other weights be $1.$ Greedy algorithm would give $4.1$ but best is $3.3$.

That said! Is there a polynomial-time algorithm? I bet there is by some sort of greedy with augmentation, but I haven't thought too much about that.

Added after question was edited:

The original question posted was about decomposing the graph into connected components, and it has since changed to be about decomposing the graph into cliques (and notation has been changed). With this new problem, the greedy algorithm still fails [in fact, I believe it's easier to see this]. To see that it fails, take the graph you show and weight it so that $V_{1}^{\{2,3\}}$ and $V_2 ^{\{1\}}$ have weight 1.1 with all others having weight 1.

• Thanks for your suggested approach. But, I don't think your example 2 is correct. As I mentioned in the problem discerption, no two vertices with the same subscript can be in a connected component. So, for your example, $A_1$, $B_1$, $C_1$ should be in three different connected component, make the weight of optimal solution at least $3 \times 99$. Furthermore, two of these connected component should include $A_2$ and $B_2$, make the weight of them equal to $100$. So, $100 + 2 \times 99$ is definitely a lower bound for the optimal solution. Commented Jan 4, 2017 at 22:56
• I didn't have any particular "method" in mind. But I was thinking of (for example) some sort of augmenting path idea. But that was more fitting for the original question you had asked. Now that you want a clique decomposition, the problem definitely sounds harder. This new problem (or more precisely, a decision-problem version of it) is almost certainly NP-complete, and I could probably outline a proof of this if you like, but it would be a reduction from chromatic number. Commented Jan 6, 2017 at 22:52
• This comment thread has gotten quite long, so perhaps we should leave it as is (find my email through my webpage if you'd like to talk any more on this). In short, [I'd bet money that] your question is NP-hard (so there is no fast algorithm for it). You could hope for an approximation, yes. In practice, for this problem, greedy as you describe might be an ok approximation depending on the inputs you give it. You can think of the question as trying to approximate the chromatic number of a graph, which is very similar to this, and it's something to look up if curious. Commented Jan 6, 2017 at 23:23
• If you want to decompose your graphing to just join cliques, that's the same as decomposing the complement of the graph into disjoint independent sets. This is the same as finding a coloring of the complement of your grass. In general find a chromatic number of a graph is a heart problem. Your graph is so general, that I feel that you could in bed very many graphs into it such that solving your problem for your graphs is the same as finding the chromatic number of a great family of graphs Commented Feb 3, 2017 at 21:20
• In particular, weight the vertices with just the weights one and zero. The vertices of weight zero don't matter. Then you're finding the chromatic number of (the complement of) the vertices with weight one. Commented Feb 3, 2017 at 21:20