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.

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Sep 9 '15 at 17:23
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Sep 9 '15 at 17:27
  • $\begingroup$ @GerhardPaseman, sure, the problem as stated is a feasibility problem, but one could certainly search for the minimal $r$ that ensures connectivity. $\endgroup$ – 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.


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.