# Complexity of a very simple graph partitioning problem

The following problem seems like a very simple and natural one, but I am not familiar with any existing work on it; in particular I am hoping to prove it is NP hard:

Let $G$ be a complete weighted graph that satisfies a triangle inequality, let $k \geq 2$ be an integer, and let $r>0$. My goal is to partition the vertices of $G$ into $k$ subsets $G_1,\dots,G_k$ with the following property: if we select any set of $k$ vertices $v_1,\dots,v_k$, with $v_i \in G_i$ for all $i$, and we let $S$ be the subgraph on the $v_i$'s consisting of edges with weights less than $r$, then we want $S$ to be connected. Thus, we're looking for a $k$-way partition that is "connected with radius $r$".

Does this ring any bells? I would think that one could prove that this is NP-hard by, say, a reduction to a maximum covering problem or a $k$-centers problem, but my attempts have been unsuccessful so far. The problem as stated is a feasibility question because we are given $k$ and $r$, but it could also be made into an optimization problem by fixing one parameter and searching for the minimum possible value of the other.

• You are going to need r big enough so that such a decomposition is remotely possible. I'm thinking that the subgraph T_r of G which contains only edges of length less than r has to be k-connected or something along those lines. Are there quick ways to determine if T_r "might be connected enough"? Gerhard "Maybe A Simpler Hard Problem" Paseman, 2015.09.09 – Gerhard Paseman Sep 9 '15 at 17:23
• In particular, if G has a vertex v with distance greater than r to all other vertices, then v can't belong to any of the k subsets. Are you promising anything with respect to r, or is an additional goal to find a minimal such r? Gerhard "The Problem Behind The Problem?" Paseman, 2015.09.09 – Gerhard Paseman Sep 9 '15 at 17:27
• @GerhardPaseman, sure, the problem as stated is a feasibility problem, but one could certainly search for the minimal $r$ that ensures connectivity. – Tom Solberg Sep 9 '15 at 17:34

For $k=2$, it's polynomial (in fact quadratic in the number of vertices). Draw an edge (in an auxiliary graph) between two vertices iff their distance is greater than $r$ (marking that these two vertices must be in the same part). Then you can partition the graph into two sets if and only if the auxiliary graph is disconnected.