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.

  • 2
    $\begingroup$ 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' $\endgroup$
    – JimN
    Sep 10 at 7:47
  • $\begingroup$ @JimN I edit my post. $\endgroup$
    – Jut
    Sep 10 at 10:07
  • $\begingroup$ @NealYoung Thanks. Can you explain in more detail about your idea in answer section? Really, i can't correctly understand your idea. $\endgroup$
    – Jut
    Sep 10 at 16:23
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Sep 14 at 15:25
  • $\begingroup$ See also OP's post (v). $\endgroup$
    – Neal Young
    Sep 14 at 15:32

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$

  • $\begingroup$ 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? $\endgroup$
    – Jut
    Sep 10 at 21:00
  • $\begingroup$ Each cluster contains edge, because my input is as follow: exactly $n$ edges have weight $\infty$. $\endgroup$
    – Jut
    Sep 10 at 21:02
  • $\begingroup$ 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)$? $\endgroup$
    – Jut
    Sep 10 at 21:05
  • $\begingroup$ Specially, the first answer by @Gamow is that algorithm that unfortunately work in $O(n^3)$. $\endgroup$
    – Jut
    Sep 10 at 21:06
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    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.
  • $\begingroup$ Thanks, what is running time of your algorithm? $\endgroup$
    – Jut
    Sep 10 at 16:20
  • $\begingroup$ 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)$. $\endgroup$
    – Jut
    Sep 10 at 16:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gamow
    Sep 11 at 12:03
  • 1
    $\begingroup$ 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})$). $\endgroup$
    – Neal Young
    Sep 14 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.