Return to Answer

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.

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.

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

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.

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.

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 5 vertices (if you don't like that, add isolated vertices). The graph has 4 edges, which are $A_1 \sim B_2 \sim B_1 \sim A_2 \sim A_3$. The weights are that $B_1$ and $B_2$ have weight 100, and the other vertices have weight 99. 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$.

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.

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

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.