<p><strong>Theorem 1.</strong> <em>The problem admits a 2-approximation algorithm that runs in <span class="math-container">$O((m+n)\log n)$</span> time, given a graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$m$</span> edges and <span class="math-container">$n$</span> vertices.</em></p>
<p>[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.)]</p>
<p><em>Proof.</em>  Here's the algorithm:</p>
<ol>
<li><p>let <span class="math-container">$e_1, e_2, \ldots, e_m$</span> denote the edges sorted by decreasing weight</p>
</li>
<li><p>let <span class="math-container">$G_t=(V, E_t)$</span> where <span class="math-container">$E_t=\{e_1,e_2,\ldots, e_t\}$</span>
denote the graph with only the heaviest <span class="math-container">$t$</span> edges</p>
</li>
<li><p>let <span class="math-container">$t'\in\{1,\ldots, m\}$</span> be maximum such that <span class="math-container">$G_{t'}$</span> is bipartite
(find <span class="math-container">$t$</span> using binary search)</p>
</li>
<li><p>let <span class="math-container">$(C_1, C_2)$</span> be a bipartition of <span class="math-container">$G_{t'}$</span> (such that <span class="math-container">$E_{t'}\subseteq C_1\times C_2)$</span>)</p>
</li>
<li><p>return <span class="math-container">$(C_1, C_2)$</span></p>
</li>
</ol>
<p>The algorithm can be implemented to run in <span class="math-container">$O((m+n)\log n)$</span> time, because the binary search requires <span class="math-container">$O(\log m) = O(\log n)$</span> rounds, and each round requires checking whether a given <span class="math-container">$G_t$</span> is bipartite (and finding its bipartition, if it is), which can be done in <span class="math-container">$O(n+m)$</span> time using, say, depth-first search (see e.g. <a href="https://en.wikipedia.org/wiki/Bipartite_graph#Algorithms" rel="nofollow noreferrer">here</a>).</p>
<p>Consider any execution of the algorithm. Let <span class="math-container">$t'$</span> and <span class="math-container">$(C_1, C_2)$</span> be as computed by the algorithm.  To finish we show that <span class="math-container">$(C_1, C_2)$</span> has objective-function value at most twice the optimum.</p>
<p>If the given graph <span class="math-container">$G$</span> is bipartite, then the algorithm returns a bipartition of <span class="math-container">$G$</span>, which (by the caveat above) is an optimal solution.  So assume that <span class="math-container">$G$</span> is not bipartite.  So <span class="math-container">$t' &lt; m$</span>.</p>
<p>Each edge within <span class="math-container">$C_1$</span> or <span class="math-container">$C_2$</span> is not in <span class="math-container">$E_{t'}$</span>, so has weight at most <span class="math-container">$w(e_{t'+1})$</span>.  So the algorithm's solution achieves objective-function value at most <span class="math-container">$2 w(e_{t'+1})$</span>.</p>
<p>Now consider any optimal solution <span class="math-container">$(C^*_1, C^*_2)$</span>. Because <span class="math-container">$G$</span> is not bipartite, there is at least one edge within one of the clusters <span class="math-container">$C^*_1$</span> or <span class="math-container">$C^*_2$</span>.  Let <span class="math-container">$e_{t^*}$</span> be the edge with <s>maximum</s> minimum index (and hence maximum weight) within either cluster.  The value of the optimal solution is at least <span class="math-container">$w(e_{t^*})$</span> (using here that the edge weights are non-negative).</p>
<p>Removing <span class="math-container">$e_{t^*}$</span> and all cheaper edges yields the graph <span class="math-container">$G_{t^*-1}=(V, E_{t^*-1})$</span>. By the choice of <span class="math-container">$e_{t^*}$</span> this graph is bipartite with bipartition <span class="math-container">$(C^*_1, C^*_2)$</span> (as all edges within each cluster are not in <span class="math-container">$E_{t^*-1}$</span>).  Hence <span class="math-container">$t^*-1 \le t'$</span>, and <span class="math-container">$w(e_{t^*}) \ge w(e_{t'+1})$</span>.  Hence the optimal solution value is at least <span class="math-container">$w(e_{t'+1})$</span>.
<span class="math-container">$~~~~~\Box$</span></p>

CC BY-SA 4.0
2021-09-10T21:05:40.343Z
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)$?
ErroR
CC BY-SA 4.0
2021-09-10T21:06:57.090Z
Specially, the first answer by @Gamow is that algorithm that unfortunately work in $O(n^3)$.
ErroR
CC BY-SA 4.0
2021-09-10T22:26:12.520Z
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.
Neal Young
CC BY-SA 4.0
2021-09-12T09:26:23.990Z
If we want, minimize heaviest edge in $C_1,C_2$, can we reduce the running time of your algorithm to $o(n^2)$?
ErroR
CC BY-SA 4.0
2021-09-12T20:24:11.117Z
That's what the given algorithm does.  As described in the answer, it also runs in time $O((n+m)\log n)$, which is $o(n^2)$ unless $m=\Theta(n^2/\log n)$.  (And if $m = \Theta(n^2)$, then you're not going to get $o(n^2)$ time because any algorithm has to at least look at all the edges.
Neal Young
CC BY-SA 4.0
2021-09-13T10:56:27.493Z
Thanks, is it possible that reference your answer to a paper? I want read the full paper of your approximation algorithm, if it's possible.
ErroR
CC BY-SA 4.0
2021-09-13T14:37:12.023Z
I'm not sure what you're asking.  If you're asking for a paper to cite or read, I don't know of any publication in which the algorithm appears, other than the answer here.  If you have questions, please feel free to ask them here.
Neal Young
CC BY-SA 4.0
2021-09-15T18:07:04.747Z
excuse me, in your algorithm, if we have a constraint that say: some of pair of vertices can't belong to one cluster, how we can handle this in your algorithm? suppose we can't add weight +$\infty$ to handle that.
ErroR
CC BY-SA 4.0
2021-09-15T19:42:24.543Z
Yes, easily: just modify the algorithm above to define each $G_t$ to also include all the edges that you don't want included in any cluster.  This is exactly the effect you would also get by giving them weight $\infty$ (which also works), so I'm a bit perplexed by your question.
Neal Young
CC BY-SA 4.0
2021-10-15T02:16:26.003Z
Thank you for your answer. But i can't undersant why $t^*-1\leq t'$. Can you explain more about it?
ErroR
CC BY-SA 4.0
2021-10-15T12:51:06.533Z
Good question.  I should have defined $t^*$ as the edge with *minimum* index within either cluster (I've fixed the post so that it says that).  So each edge $e_i$ that is within either cluster (that is, that doesn't cross between the two clusters) has $i \ge t^*$.  So, removing all such edges ($e_{t^*}, \ldots, e_{m}$) yields a bipartite graph, specifically the graph $G_{t^*-1}$ (as defined in the algorithm.  But $t'$ is the maximum index such that $G_{t'}$ is bipartite.  So $t' \ge t^* - 1$.
Neal Young
CC BY-SA 4.0
2022-01-08T22:26:57.117Z
Hello, Suppose $G$ is metric and contains exactly $n$ vertices, also we say two a bi-partition of $G$ is a good, if and only if, sum of diameters of $C_1+C_2$ be less than diameter of $G$.
ErroR
CC BY-SA 4.0
2022-01-12T01:23:07.237Z
(i) The lemma fails (consider vertices (a, c, b) with c in between a and b and forbidden pairs (a, c) (c, b).  (ii) Given that there is an O(m log n)-time algorithm (above), depending on what you mean by "black box", the answer to your question is technically yes.  Just don't use the black box -- solve the problem in O(m log n) time directly.  Jut, you may have more luck if you make your questions more precise.  You keep asking many related but (in my opinion) somewhat imprecise questions, which makes it hard to give definitive answers.  Perhaps you could give a statement of your precise goal?
Neal Young
CC BY-SA 4.0
2022-01-12T02:19:48.303Z
Thank you so I read again and I will ask you in precise manner about the problem, if get stuck. for (i) if we each point appear exactly in one pair, are there any counter example?
ErroR
CC BY-SA 4.0
2022-01-12T02:48:43.957Z
Yes, there is a counter-example.
Neal Young
CC BY-SA 4.0
2021-09-10T20:53:49.007Z
2021-10-15T12:51:19.833Z
2021-10-15T12:51:19.833Z
Neal Young
<p>The problem even seems to be solvable in polynomial time.
Let us call <span class="math-container">$C_1$</span> the <strong>black</strong> cluster and <span class="math-container">$C_1$</span> the <strong>white</strong> cluster.
We test for every two edges <span class="math-container">$e_1,e_2\in E$</span> whether there exists a bipartition so that <span class="math-container">$e_1$</span> is the heaviest edge in <span class="math-container">$C_1$</span> and <span class="math-container">$e_2$</span> is the heaviest edge in <span class="math-container">$C_2$</span>. In the end, we ouput the bipartition that minimizes the sum of the two heaviest edges.</p>
<p>Now the test for two edges <span class="math-container">$e_1,e_2\in E$</span> proceeds as follows.
We use a 2-SAT formulation.
There is a variable <span class="math-container">$x(v)$</span> for every vertex; the value TRUE corresponds to <span class="math-container">$v$</span> being black and the value FALSE corresponds to <span class="math-container">$v$</span> being white.</p>
<ul>
<li>For any edge <span class="math-container">$e=\{u,v\}$</span> with <span class="math-container">$w(e)&gt;w(e_1)$</span>, we require that <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are in different clusters. Hence we create the clauses <span class="math-container">$(u\lor v)(\lnot u\lor\lnot v)$</span>.</li>
<li>For any edge <span class="math-container">$e=\{u,v\}$</span> with <span class="math-container">$w(e_1)\ge w(e)&gt;w(e_2)$</span>, the two endpoints must either both be in <span class="math-container">$C_1$</span>, or one is in <span class="math-container">$C_1$</span> and the other one in <span class="math-container">$C_2$</span>.
This corresponds to the clause <span class="math-container">$(u\lor v)$</span>.</li>
<li>Edges <span class="math-container">$e=\{u,v\}$</span> with <span class="math-container">$w(e_2)\ge w(e)$</span> are ignored for this particular test.</li>
</ul>

CC BY-SA 4.0
2021-09-10T16:20:11.043Z
Thanks, what is running time of your algorithm?
ErroR
CC BY-SA 4.0
2021-09-10T16:33:05.413Z
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)$.
ErroR
CC BY-SA 4.0
2021-09-11T12:03:37.383Z
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.
Gamow
CC BY-SA 4.0
2021-09-14T15:23:08.627Z
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})$).
Neal Young
CC BY-SA 4.0
2021-09-10T13:26:18.107Z
2021-09-10T13:26:18.107Z
Gamow
<p>Suppose given a complete weighted graph <span class="math-container">$G=(V,E)$</span>, Is there an algorithm that partition <span class="math-container">$G$</span> into two clusters <span class="math-container">$C_1,C_2$</span> such that sum of heaviest edges in <span class="math-container">$C_1,C_2$</span> minimized?</p>
<p>Note that, heaviest edge in a cluster is an edge with maximum weight. Also, i rename a partition to cluster, additionally, <span class="math-container">$G$</span> can partitioned to two clusters <span class="math-container">$C_1,C_2$</span>.</p>
<p>If there be an approximation algorithm that running time be less than <span class="math-container">$o(n^3)$</span> it's helpful. I find some related paper, but all paper work on metric space, but <span class="math-container">$G$</span> is not a metric graph.</p>
<p>In essence, according <a href="https://math.stackexchange.com/questions/4245835/how-we-can-change-the-metric-weightetd-graph-such-that-it-remain-metric">this post</a> at the first, my graph is metric, but after changing the weight of some of edges to <span class="math-container">$\infty$</span> then <span class="math-container">$G$</span> isn't remain metric.</p>

CC BY-SA 4.0
2021-09-10T07:47:08.737Z
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
CC BY-SA 4.0
2021-09-10T10:07:00.763Z
@JimN I edit my post.
ErroR
CC BY-SA 4.0
2021-09-10T16:23:17.017Z
@NealYoung Thanks. Can you explain in more detail about your idea in answer section? Really, i can't  correctly understand your idea.
ErroR
CC BY-SA 4.0
2021-09-14T15:25:27.727Z
Note: OP, you have four posts, apparently about this question:
[(i)](https://cstheory.stackexchange.com/questions/50461/partition-a-graph-into-two-clusters),
[(ii)](https://math.stackexchange.com/questions/4245835/how-we-can-change-the-metric-weighted-graph-such-that-it-remain-metric),
[(iii)](https://cs.stackexchange.com/questions/143766/a-question-about-euclidean-graph),
and [(iv)](https://cstheory.stackexchange.com/questions/50469/adding-a-constraint-to-input-graph).  These posts are all somewhat unclear, and cross-posting is discouraged.  I suggest you delete the other three posts.
Neal Young
CC BY-SA 4.0
2021-09-14T15:32:03.867Z
See also OP's post [(v)](https://cs.stackexchange.com/questions/143630/minimize-the-sum-of-diameters-of-2-clustering-graph).
Neal Young
CC BY-SA 4.0
2021-09-17T22:03:24.103Z
@NealYoung Yes i'm interested, thanks.
ErroR
CC BY-SA 4.0
2021-09-18T12:15:19.950Z
Followup post with more details about the specific problem OP is interested in: https://cstheory.stackexchange.com/questions/50494/applying-a-change-in-particular-algorithm/
Neal Young
CC BY-SA 4.0
2021-09-18T12:41:57.220Z
@NealYoung Thanks, it's a great answer. But i think before reading your answer, i prefer to solve my problem by myself step by step, if it's possible and you are agree with me, i delete my post, because your solution is very complete and easily i can copy it that it's not good for me. If it's possible, i seek for some hint to progress my problem with myself. I forget to mentioned that in my post that i'm not agree with complete solution, because i want find solution step by step with myself. Also i have a copy of paper Monma and Suri, if you need i can scan it and send for you by email.
ErroR
CC BY-SA 4.0
2021-09-18T12:45:14.457Z
@NealYoung I'm not agree with complete solution delete the post, so i delete the post. If you are not agree with me, i will restore it. Thanks.
ErroR
CC BY-SA 4.0
2021-09-18T18:06:02.637Z
I see.  In future posts please make it clearer what you are looking for.  As it happens I spent some time thinking about how to answer your question and writing up and posting an answer for you, which from my point of view now was time wasted.  I suppose if you wanted to you could undelete the post and not look at my answer (or look at it briefly if you want to get some idea), but it's up to you. :-) As for a copy of the paper, I don't need one, thanks.
Neal Young
CC BY-SA 4.0
2021-09-20T02:23:47.487Z
Hi Jut, I think that with the post deleted you can still see it and the answer, so deleting effectively hides the post and answer only from others.  For this reason, my vote would be to undelete it, so others can see it too.
Neal Young
CC BY-SA 4.0
2021-10-13T19:44:31.787Z
@NealYoung Thanks for your comment. I undelete your greatful answer. Also i have a question, can i ask you?
ErroR
CC BY-SA 4.0
2021-10-13T20:25:49.217Z
Sure.  FYI it looks like your post https://cstheory.stackexchange.com/questions/50494/applying-a-change-in-particular-algorithm/ is still deleted (at the moment).  A while back I made a copy with my answer here: https://cstheory.stackexchange.com/questions/50514/partitioning-points-in-the-plane-into-two-clusters-to-minimize-maximum-cluster-d
Neal Young
CC BY-SA 4.0
2021-10-13T22:02:15.767Z
@NealYoung I undeleted the post. Can i ask my question by email? Thanks.
ErroR
CC BY-SA 4.0
2021-10-14T01:51:21.533Z
yes, go ahead.  Also, if you think the answer to the now-undeleted post is correct, can you go ahead and accept it?
Neal Young
CC BY-SA 4.0
2021-10-14T10:47:01.237Z
I want be honest with you, because i find solution after reading a Thesis of a student and paper Suri, et-all, but your complete solution in the internet can be harm for my academic history. I think it's better to describe anything in Skype to you. I can't describe other things in this site.
ErroR
CC BY-SA 4.0
2021-10-14T10:54:27.337Z
With regard, it's very crirtical for me that describe my problem for you in a short time in Skype. Please if it's possible, accept my request. Thanks.
ErroR
CC BY-SA 4.0
2021-10-14T12:57:22.797Z
Jut, I'm not available to Skype, but feel free to email me.
Neal Young
CC BY-SA 4.0
2021-10-14T14:10:00.277Z
Thank you. I send an email. With regard.
ErroR
CC BY-SA 4.0
2021-10-14T22:32:56.320Z
@NealYoung Yesterday, I send an email to "lastname.firstname@gmail.com". I hope you received my email. Thank you.
ErroR
CC BY-SA 4.0
2021-10-14T22:53:16.013Z
Jut, I did not. You'll have to substitute my actual last name and first name to get my email address.
Neal Young
CC BY-SA 4.0
2021-10-15T00:08:27.113Z
@NealYoung Forgive me for that mistake. I sent, again an email for you. I hope you received my email.
ErroR
CC BY-SA 4.0
2021-10-15T14:54:42.617Z
Hi Jut, I responded to your email.
Neal Young
<ds.algorithms><graph-theory><approximation-algorithms>
Partition a graph into two clusters
ErroR
# Partition a graph into two clusters

(Asked by: username_0 on 2021-09-09)

Suppose given a complete weighted graph $G=(V,E)$, Is 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](https://math.stackexchange.com/questions/4245835/how-we-can-change-the-metric-weightetd-graph-such-that-it-remain-metric) at the first, my graph is metric, but after changing the weight of some of edges to $\infty$ then $G$ isn't remain metric.

**Tags:** ds.algorithms, graph-theory, approximation-algorithms

> **Comments:**
> **username_1**: 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'  
> **username_0**: @username_1 I edit my post.  
> **username_0**: @NealYoung Thanks. Can you explain in more detail about your idea in answer section? Really, i can't  correctly understand your idea.  
> **username_2**: Note: OP, you have four posts, apparently about this question: [(i)](https://cstheory.stackexchange.com/questions/50461/partition-a-graph-into-two-clusters), [(ii)](https://math.stackexchange.com/questions/4245835/how-we-can-change-the-metric-weighted-graph-such-that-it-remain-metric), [(iii)](https://cs.stackexchange.com/questions/143766/a-question-about-euclidean-graph), and [(iv)](https://cstheory.stackexchange.com/questions/50469/adding-a-constraint-to-input-graph).  These posts are all somewhat unclear, and cross-posting is discouraged.  I suggest you delete the other three posts.  
> **username_2**: See also OP's post [(v)](https://cs.stackexchange.com/questions/143630/minimize-the-sum-of-diameters-of-2-clustering-graph).  
> **username_0**: @NealYoung Yes i'm interested, thanks.  
> **username_2**: Followup post with more details about the specific problem OP is interested in: https://cstheory.stackexchange.com/questions/50494/applying-a-change-in-particular-algorithm/  
> **username_0**: @NealYoung Thanks, it's a great answer. But i think before reading your answer, i prefer to solve my problem by myself step by step, if it's possible and you are agree with me, i delete my post, because your solution is very complete and easily i can copy it that it's not good for me. If it's possible, i seek for some hint to progress my problem with myself. I forget to mentioned that in my post that i'm not agree with complete solution, because i want find solution step by step with myself. Also i have a copy of paper Monma and Suri, if you need i can scan it and send for you by email.  
> **username_0**: @NealYoung I'm not agree with complete solution delete the post, so i delete the post. If you are not agree with me, i will restore it. Thanks.  
> **username_2**: I see.  In future posts please make it clearer what you are looking for.  As it happens I spent some time thinking about how to answer your question and writing up and posting an answer for you, which from my point of view now was time wasted.  I suppose if you wanted to you could undelete the post and not look at my answer (or look at it briefly if you want to get some idea), but it's up to you. :-) As for a copy of the paper, I don't need one, thanks.  
> **username_2**: Hi Jut, I think that with the post deleted you can still see it and the answer, so deleting effectively hides the post and answer only from others.  For this reason, my vote would be to undelete it, so others can see it too.  
> **username_0**: @NealYoung Thanks for your comment. I undelete your greatful answer. Also i have a question, can i ask you?  
> **username_2**: Sure.  FYI it looks like your post https://cstheory.stackexchange.com/questions/50494/applying-a-change-in-particular-algorithm/ is still deleted (at the moment).  A while back I made a copy with my answer here: https://cstheory.stackexchange.com/questions/50514/partitioning-points-in-the-plane-into-two-clusters-to-minimize-maximum-cluster-d  
> **username_0**: @NealYoung I undeleted the post. Can i ask my question by email? Thanks.  
> **username_2**: yes, go ahead.  Also, if you think the answer to the now-undeleted post is correct, can you go ahead and accept it?  
> **username_0**: I want be honest with you, because i find solution after reading a Thesis of a student and paper Suri, et-all, but your complete solution in the internet can be harm for my academic history. I think it's better to describe anything in Skype to you. I can't describe other things in this site.  
> **username_0**: With regard, it's very crirtical for me that describe my problem for you in a short time in Skype. Please if it's possible, accept my request. Thanks.  
> **username_2**: Jut, I'm not available to Skype, but feel free to email me.  
> **username_0**: Thank you. I send an email. With regard.  
> **username_0**: @NealYoung Yesterday, I send an email to "lastname.firstname@gmail.com". I hope you received my email. Thank you.  
> **username_2**: Jut, I did not. You'll have to substitute my actual last name and first name to get my email address.  
> **username_0**: @NealYoung Forgive me for that mistake. I sent, again an email for you. I hope you received my email.  
> **username_2**: Hi Jut, I responded to your email.  

---

## 2 answers

### Answer by username_2 on 2021-09-10. Score: 2 | Accepted answer

**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](https://en.wikipedia.org/wiki/Bipartite_graph#Algorithms)).

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~~ minimum 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$

> **Comments:**
> **username_0**: 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)$?  
> **username_0**: Specially, the first answer by @username_3 is that algorithm that unfortunately work in $O(n^3)$.  
> **username_2**: 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.  
> **username_0**: If we want, minimize heaviest edge in $C_1,C_2$, can we reduce the running time of your algorithm to $o(n^2)$?  
> **username_2**: That's what the given algorithm does.  As described in the answer, it also runs in time $O((n+m)\log n)$, which is $o(n^2)$ unless $m=\Theta(n^2/\log n)$.  (And if $m = \Theta(n^2)$, then you're not going to get $o(n^2)$ time because any algorithm has to at least look at all the edges.  
> **username_0**: Thanks, is it possible that reference your answer to a paper? I want read the full paper of your approximation algorithm, if it's possible.  
> **username_2**: I'm not sure what you're asking.  If you're asking for a paper to cite or read, I don't know of any publication in which the algorithm appears, other than the answer here.  If you have questions, please feel free to ask them here.  
> **username_0**: excuse me, in your algorithm, if we have a constraint that say: some of pair of vertices can't belong to one cluster, how we can handle this in your algorithm? suppose we can't add weight +$\infty$ to handle that.  
> **username_2**: Yes, easily: just modify the algorithm above to define each $G_t$ to also include all the edges that you don't want included in any cluster.  This is exactly the effect you would also get by giving them weight $\infty$ (which also works), so I'm a bit perplexed by your question.  
> **username_0**: Thank you for your answer. But i can't undersant why $t^*-1\leq t'$. Can you explain more about it?  
> **username_2**: Good question.  I should have defined $t^*$ as the edge with *minimum* index within either cluster (I've fixed the post so that it says that).  So each edge $e_i$ that is within either cluster (that is, that doesn't cross between the two clusters) has $i \ge t^*$.  So, removing all such edges ($e_{t^*}, \ldots, e_{m}$) yields a bipartite graph, specifically the graph $G_{t^*-1}$ (as defined in the algorithm.  But $t'$ is the maximum index such that $G_{t'}$ is bipartite.  So $t' \ge t^* - 1$.  
> **username_0**: Hello, Suppose $G$ is metric and contains exactly $n$ vertices, also we say two a bi-partition of $G$ is a good, if and only if, sum of diameters of $C_1+C_2$ be less than diameter of $G$.  
> **username_2**: (i) The lemma fails (consider vertices (a, c, b) with c in between a and b and forbidden pairs (a, c) (c, b).  (ii) Given that there is an O(m log n)-time algorithm (above), depending on what you mean by "black box", the answer to your question is technically yes.  Just don't use the black box -- solve the problem in O(m log n) time directly.  Jut, you may have more luck if you make your questions more precise.  You keep asking many related but (in my opinion) somewhat imprecise questions, which makes it hard to give definitive answers.  Perhaps you could give a statement of your precise goal?  
> **username_0**: Thank you so I read again and I will ask you in precise manner about the problem, if get stuck. for (i) if we each point appear exactly in one pair, are there any counter example?  
> **username_2**: Yes, there is a counter-example.  

---

### Answer by username_3 on 2021-09-10. Score: 2

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.

> **Comments:**
> **username_0**: Thanks, what is running time of your algorithm?  
> **username_0**: 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)$.  
> **username_3**: 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.  
> **username_2**: 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})$).  

---

