# Partition a graph into two clusters

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 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, 2021 at 7:47
• @JimN I edit my post.
– Jut
Sep 10, 2021 at 10:07
– Jut
Sep 10, 2021 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, 2021 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 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$$

• 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, 2021 at 21:05
• Specially, the first answer by @Gamow is that algorithm that unfortunately work in $O(n^3)$.
– Jut
Sep 10, 2021 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, 2021 at 22:26
• If we want, minimize heaviest edge in $C_1,C_2$, can we reduce the running time of your algorithm to $o(n^2)$?
– Jut
Sep 12, 2021 at 9:26
• 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. Sep 12, 2021 at 20:24

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, 2021 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, 2021 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, 2021 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, 2021 at 15:23