4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Sep 9, 2015 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
    Commented Sep 9, 2015 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
    Commented Sep 9, 2015 at 17:34

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .