Partition a graph into two clusters

Suppose given a complete weighted graph $$G=(V,E)$$, with positive weight. Are there an algorithm that partition $$G$$ into two clusters $$C_1,C_2$$ such that sum of heaviest edges in $$C_1,C_2$$ minimized?

Note that, heaviest edge in a cluster is an edge with maximum weight. Also, i rename a partition to cluster, additionally, $$G$$ can partitioned to two clusters $$C_1,C_2$$.

If there be an approximation algorithm that running time be less than $$o(n^3)$$ it's helpful. I find some related paper, but all paper work on metric space, but $$G$$ is not a metric graph.

In essence, according this post at the first, my graph is metric, but after changing the weight of some of edges to $$\infty$$ then $$G$$ isn't remain metric.

• Can you define "heaviest edges" in $C_1, C_2$ ? does this mean the sum of the one single largest edge in C1 and the one single largest edge in C2? Can you define what a 'cluster' is? Can $G$ be partitioned into any two $C_1$ and $C_2$? (So one could be a single edge and the other one be the rest of the graph?) Or do these partitions need to satisfy some other property to be considered a valid 'cluster'
– JimN
Sep 10 at 7:47
• @JimN I edit my post.
– Jut
Sep 10 at 10:07
– Jut
Sep 10 at 16:23
• Note: OP, you have four posts, apparently about this question: (i), (ii), (iii), and (iv). These posts are all somewhat unclear, and cross-posting is discouraged. I suggest you delete the other three posts. Sep 14 at 15:25

Theorem 1. The problem admits a 2-approximation algorithm that runs in $$O((m+n)\log n)$$ time, given a graph $$G=(V,E)$$ with $$m$$ edges and $$n$$ vertices.

[Caveat: The current post doesn't specify the objective-function value if one or both of the clusters contains no edges. I assume that the objective-function value only sums the maximum-weight edges within clusters that do contain edges. (If, say, the graph is bipartite then the optimal value is zero.)]

Proof. Here's the algorithm:

1. let $$e_1, e_2, \ldots, e_m$$ denote the edges sorted by decreasing weight

2. let $$G_t=(V, E_t)$$ where $$E_t=\{e_1,e_2,\ldots, e_t\}$$ denote the graph with only the heaviest $$t$$ edges

3. let $$t'\in\{1,\ldots, m\}$$ be maximum such that $$G_{t'}$$ is bipartite (find $$t$$ using binary search)

4. let $$(C_1, C_2)$$ be a bipartition of $$G_{t'}$$ (such that $$E_{t'}\subseteq C_1\times C_2)$$)

5. return $$(C_1, C_2)$$

The algorithm can be implemented to run in $$O((m+n)\log n)$$ time, because the binary search requires $$O(\log m) = O(\log n)$$ rounds, and each round requires checking whether a given $$G_t$$ is bipartite (and finding its bipartition, if it is), which can be done in $$O(n+m)$$ time using, say, depth-first search (see e.g. here).

Consider any execution of the algorithm. Let $$t'$$ and $$(C_1, C_2)$$ be as computed by the algorithm. To finish we show that $$(C_1, C_2)$$ has objective-function value at most twice the optimum.

If the given graph $$G$$ is bipartite, then the algorithm returns a bipartition of $$G$$, which (by the caveat above) is an optimal solution. So assume that $$G$$ is not bipartite. So $$t' < m$$.

Each edge within $$C_1$$ or $$C_2$$ is not in $$E_{t'}$$, so has weight at most $$w(e_{t'+1})$$. So the algorithm's solution achieves objective-function value at most $$2 w(e_{t'+1})$$.

Now consider any optimal solution $$(C^*_1, C^*_2)$$. Because $$G$$ is not bipartite, there is at least one edge within one of the clusters $$C^*_1$$ or $$C^*_2$$. Let $$e_{t^*}$$ be the edge with maximum index (and hence maximum weight) within either cluster. The value of the optimal solution is at least $$w(e_{t^*})$$ (using here that the edge weights are non-negative).

Removing $$e_{t^*}$$ and all cheaper edges yields the graph $$G_{t^*-1}=(V, E_{t^*-1})$$. By the choice of $$e_{t^*}$$ this graph is bipartite with bipartition $$(C^*_1, C^*_2)$$ (as all edges within each cluster are not in $$E_{t^*-1}$$). Hence $$t^*-1 \le t'$$, and $$w(e_{t^*}) \ge w(e_{t'+1})$$. Hence the optimal solution value is at least $$w(e_{t'+1})$$. $$~~~~~\Box$$

• Thank you, also i have a greedy algorithm, but when i want find out the approximation factor i get stuck, can i add my algorithm to question and then help me to find the approximation factor of my idea?
– Jut
Sep 10 at 21:00
• Each cluster contains edge, because my input is as follow: exactly $n$ edges have weight $\infty$.
– Jut
Sep 10 at 21:02
• Excuse me, i read a paper that solve my question in with an exact algorithm in $O(n^3)$. But after reading many paper, i think, i can't do better than $o(n^3)$, so i search to find an approximation algorithm that work in $o(n^3)$ and has constant approximation factor. Are you have any comment about an exact algorithm for above problem that work in $o(n^3)$?
– Jut
Sep 10 at 21:05
• Specially, the first answer by @Gamow is that algorithm that unfortunately work in $O(n^3)$.
– Jut
Sep 10 at 21:06
• I don't have an idea for a faster exact algorithm, no. ^^^Rather than edit your post to change your question (which would invalidate the current answers), it would be better to create a new post with the new question. Also, please accept one of the current answers if it answers your current question, thanks. Sep 10 at 22:26

The problem even seems to be solvable in polynomial time. Let us call $$C_1$$ the black cluster and $$C_1$$ the white cluster. We test for every two edges $$e_1,e_2\in E$$ whether there exists a bipartition so that $$e_1$$ is the heaviest edge in $$C_1$$ and $$e_2$$ is the heaviest edge in $$C_2$$. In the end, we ouput the bipartition that minimizes the sum of the two heaviest edges.

Now the test for two edges $$e_1,e_2\in E$$ proceeds as follows. We use a 2-SAT formulation. There is a variable $$x(v)$$ for every vertex; the value TRUE corresponds to $$v$$ being black and the value FALSE corresponds to $$v$$ being white.

• For any edge $$e=\{u,v\}$$ with $$w(e)>w(e_1)$$, we require that $$u$$ and $$v$$ are in different clusters. Hence we create the clauses $$(u\lor v)(\lnot u\lor\lnot v)$$.
• For any edge $$e=\{u,v\}$$ with $$w(e_1)\ge w(e)>w(e_2)$$, the two endpoints must either both be in $$C_1$$, or one is in $$C_1$$ and the other one in $$C_2$$. This corresponds to the clause $$(u\lor v)$$.
• Edges $$e=\{u,v\}$$ with $$w(e_2)\ge w(e)$$ are ignored for this particular test.
• Thanks, what is running time of your algorithm?
– Jut
Sep 10 at 16:20
• There is a paper that solution is identical with your solution but the running time is $O(n^3)$, so it's not good for my question, because i trying to find a solution that work in $o(n^3)$.
– Jut
Sep 10 at 16:33
• So, why didn't you provide us with full information on the known results around your problem (in the statement of your question)??? And PLEASE provide a link to that other paper with the $O(n^3)$ algorithm. Sep 11 at 12:03
• FWIW I think this algorithm can be implemented (by enumerating all first edges and using binary search over the second) to run in time $O(m(m+n)\log n)$, which is $o(n^3)$ for sufficiently sparse graphs (as long as $m$ is $o(n^{3/2} /\sqrt{\log n})$). Sep 14 at 15:23