Maximise the value of the minimum weight intra edge

I've been doing review problems for a midterm and I came across this one problem that I haven't been able to solve. The problem essentially says that given a complete graph $$G=(V,E)$$ partition the vertices into two subsets $$A$$ and $$B$$ such that weight of the smallest intra edge (i.e. an edge $$e=(u,v)$$ such that $$u$$ and $$v$$ belong to the same subset) is maximized. The graph has $$n$$ vertices and $$k$$ weighted edges.

The edges with no weight can be assumed to have infinite weight. The required runtime is $$O((n+k) \log k)$$.

I thought of this in two ways:

1. Arrange the edge weights in increasing order and for every edge $$(u,v)$$, place $$u$$ and $$v$$ in different subsets.

2. Arrange the edge weights in decreasing order and for every edge $$(u,v)$$, place $$u$$ and $$v$$ in the same subset until all the vertices have been placed in some subset.

The second approach doesn't work because there could be a smaller edge among two vertices in the same subset.

• I think that the measure to maximize is: $\min_{ (u,v) \in A^2 \cup B^2} w(u,v)$. – Steven Mar 7 at 12:49
• Could you please explain what you mean by the correct value? Also, since the graph is complete, wouldn’t it always have an odd cycle, thus making it not bipartite? – Johnny Kingston Mar 7 at 13:00
• Thanks, poor reading comprehension on my part, sorry. I would delete all infinite-weight edges and use approach 1, maintaining independent bipartitions for each connected component that forms as you add weighted edges. In particular, when adding an edge $uv$ and neither $u$ nor $v$ has been considered so far, don't commit to a particular subset for them, only record that they are in different subsets within that brand new component. When adding an edge $uv$ such that $u$ and $v$ are in different existing components, the two bipartitions combine to put $u$ and $v$ on opposite sides. – j_random_hacker Mar 7 at 13:41
• Sort the edges by weight, and start constructing a bipartite graph. The first edge you add that creates an odd cycle is the solution. – Pål GD Mar 7 at 13:58
• – D.W. Mar 7 at 18:23

As I mentioned in the comments, the algorithm could be like this:

1. Sort the $$k$$ edges in $$k \log k$$ time and notice that $$n$$ doesn't really factor into the running time.
2. Iteratively add one and one edge (from small to large).
3. If an edge causes an odd cycle, you output the value of that edge, the rest of the graph can be partitioned arbitrary.

A graph is bipartite if and only if there are no odd cycle, so in step 2 you are iteratively building a bipartite graph. How do you quickly build up a bipartite graph?

Using Union find, you can merge components one component at a time, and you need to keep track of each vertex in a component whether it is "red" or "blue". However, you need to be able to flip all colors in a component in $$O(1)$$ time, which should be kept as a flag in the root of a component.

Therefore, once you add an edge within a component between two vertices of the same color, you are done.

All in all, this should be doable in $$O(k \log k)$$ time.

Let $$G=\left(V, E=\binom{V}{2}\right)$$ be your input graph, let $$n=|V|$$, and call $$w(u,v)$$ the weight of edge $$(u,v) \in E$$. Let $$x^* = \max_{A, B} \min_{ (u,v) \in A^2 \cup B^2} w(u,v)$$ be the value of an optimal solution to your problem (here $$A \cup B = V$$ and $$A \cap B = \emptyset$$).

Suppose that you have a guess $$x$$ on the value of $$x^*$$ and let $$D_x$$ be the set of all edges of weight smaller than $$x$$. Consider the graph $$G'=(V, D)$$.

If $$G'$$ is bipartite, then the two sides of a bipartition will give you a partition of $$V$$ such that every intra-edge has weight at least $$x$$. This shows that $$x \le x^*$$.

If $$G_x$$ is not bipartite then, for every partition $$A,B$$ of $$V$$, you have $$D_x \setminus (A \times B) \neq \emptyset$$. Since the same must hold for every $$x' \ge x$$ (since $$D_{x'} \supseteq D_x$$) this shows that no partition of $$G$$ can have a measure of at least $$x$$. I.e., $$x > x^*$$.

You can then sort the set $$W=\{w(u,v) \mid (u,v) \in E\}$$ of all edge weights and binary search for the value of $$x^* \in W$$. The binary search will require at most $$O(\log n)$$ iterations, and each iteration requires time $$O(n^2)$$ to check whether $$G_x$$ is bipartite.

The overall running time is then $$O(n^2 \log n)$$.

If the edges are already sorted by their weight, or if the edge weights are polynomially bounded (w.r.t. $$n$$) you can improve the above time complexity by a factor of almost $$\Theta(\log n)$$.

Indeed, if you have already conducted a bipartiteness test on $$G_x$$, and $$G_x$$ was bipartite, and then you are asked to determine whether $$G_{x'}$$, with $$x' > x$$, is bipartite there is no need to check all edges in $$D_{x'}$$. Indeed, you can get away with only checking the edges in $$\Delta(x, x') = D_{x'} \setminus D_{x}$$.

The idea is as follows: maintain a disjoint-set (union find) data structure $$U$$ on the vertices of $$V$$, such that if $$u,v \in V$$ belong to the same set in $$U$$, then they must also belong to the same side of the bipartition of the last tested graph $$G_x$$.

To be more precise: $$U$$ will contain one set $$S$$ for each isolated vertex of $$G_x$$ and two sets $$S_1, S_2$$ for each connected component $$C$$ of $$G$$ with at least $$2$$ vertices, where $$S_1, S_2$$ are the unique bipartition of $$G$$. It is also convenient to store, for each set $$S_i$$ in $$U$$, the name $$\eta(S_i)$$ of the set corresponding to the other side of the bipartition. Namely, $$\eta(S_1) = S_2$$ and $$\eta(S_2)=S_1$$. If $$S$$ is a singleton set, then $$\eta(S)$$ is undefined.

Initially $$x=0$$ (assuming w.l.o.g. that all edge weights are non-negative) so $$D_0 = \emptyset$$ and $$U$$ contains $$n$$ singletons.

A bipartitness check on $$G_{x'}$$ can be done as follows: For each edge $$(u,v) \in \Delta(x, x')$$ query $$U$$ to find the sets $$S_1,S_2$$ such that $$u \in S_1$$ and $$v \in S_2$$. We distinguish some cases:

• Case 1: $$S_1 = S_2$$. In this case $$G_{x'}$$ cannot be bipartite since we already know that $$u$$ and $$v$$ must be on the same side of the bipartition.

• Case 2: $$S_1 \neq S_2$$, $$\eta(S_1)$$ is defined, and $$\eta(S_1)=S_2$$. In this case $$(u,v)$$ connects two vertices in different sides of the bipartition of an already existing connected component. Do nothing.

• Case 3: $$S_1 \neq S_2$$ and $$\eta(S_1)$$ is either undefined or $$\eta(S_1) \neq S_2$$. In this case we just discovered an edge across different connected components. Perform a union operation between $$\eta(S_1)$$ and $$S_2$$ and let $$S'$$ be the resulting set (if $$\eta(S_1)$$ is undefined then $$S' = S_2$$). Perform a union operation between $$\eta(S_2)$$ and $$S_1$$ and let $$S''$$ be the resulting set (if $$\eta(S_2)$$ is undefined then $$S'' = S_1$$). Set $$\eta(S') = S''$$ and $$\eta(S'')=S'$$. See the figure for an example.

If all edges in $$\Delta(x, x')$$ are processed without ever encountering case 1, then $$G_{x'}$$ is bipartite.

The final algorithm checks whether $$G_x$$ is bipartite for $$x \in W$$ in order, until $$G_x$$ becomes not bipartite. Then it returns the predecessor $$y$$ of $$x$$ in $$W$$. The actual partition of $$V$$ can be found using standard techniques (the laziest one is to find a bipartition of $$G_y$$ from scratch).

All the sets $$\Delta(x, x')$$ can be found in time $$O(n^2)$$ once $$E$$ is sorted w.r.t. $$w(\cdot)$$ (if $$E$$ is not already sorted we can use radix sort and the fact that the weights are polynomially bounded). Moreover, the number of find operations is $$O(n^2)$$ and the number of union operations is $$O(n)$$. Thus the overall required time $$O(n^2 \alpha(n))$$ where $$\alpha(n)$$ is the inverse Ackermann function.

Notice that $$\Omega(n^2)$$ is a trivial lower bound for your problem.