2-Center problem with forbidden pairs

Question

Is there a nearly linear-time 2-approximation (or $O(1)$-approximation) algorithm for the following problem?

2-Center with Forbidden Pairs

input: Bipartite graph $G=(V,E)$ where each vertex $v$ is a point $v\in\mathbb R^2$.

output: An assignment $f:V\rightarrow\{a,b\}$ where $\{a,b\}\subseteq V$ and $f(u)\ne f(w)$ for each $(u,w)\in E$, minimizing $\max_{v\in V} d(v, f(v))$, where $d(v, w)$ is the Euclidean distance.

That is, given some points in the plane with some pairs designated as "forbidden", partition the points into two clusters, each with some point designated as its "center", so that no forbidden pair is contained within either cluster. Minimize the maximum distance from any point to its cluster's center.

The generalization to $k$ clusters is NP-hard for any $k\ge 3$, as it subsumes $k$-COLORING.

Answer 1

Maybe this will give ideas for a faster algorithm:

Theorem 1. There's an $O(n^2 \log n)$-time 2-approximation algorithm.

Proof. Here's the algorithm:

1. Using binary search over the $O(n^2)$-pairwise distances $\{d(u,w) : u, w\in V\}$, find the minimum radius $r$ such that the graph $G_r=(V, E_r)$ is bipartite, where $E_r = E \cup\{(u,w) : d(u, w) > r\}$.
2. Return a bipartition of $G_r$, making any vertex in each part the center of that part.

Time. The binary search requires $O(\log n)$ iterations, and each iteration (checking bipartiteness) can be done in $O(n^2)$ time, so the algorithm takes $O(n^2\log n)$ time.

Performance guarantee. Clearly the algorithm returns a solution of value $r$. We'll show that the optimal solution has value at least $r/2$. Let $(C^*, V\setminus C^*)$ be an optimal solution, of value $r^*$. Consider the graph $G_{2r^*}$ as defined in the algorithm above. Within each cluster of the optimal solution, each point is at distance at most $r^*$ from its center, so all pairs of points within the cluster have distance at most $2r^*$. Also, no pairs of points within either cluster are forbidden. It follows that no edge in $G_{2r^*}$ is contained in $C^*$ or in $V\setminus C^*$, so that $(C^*, V\setminus C^*)$ is a bipartition of $G_{2r^*}$. So $G_{2r^*}$ is bipartite. So, by the choice of $r$, $2r^* \ge r$. That is, $r\le r^*/2$. $~~~\Box$