On the Parameterized Complexity of Min-Sum-Radii

We provide a polynomial-time parameterized reduction from the Multicolored Clique problem. Since the parameter in our reduction only grows linearly, additionally to $𝖶$[1]-hardness, we also obtain that there is no $f(vc+k)\cdot N^{o(vc+k)}$-time algorithm for MSR under $\mathrm{𝖤𝖳𝖧}$, where $N$ denotes the number of input points in the MSR instance.

Let $(G,k,(V_1,\mathrm{\dots },V_k))$ denote an instance of the Multicolored Clique problem. Without loss of generality, we can assume that $V_i=\{v_1^i,\mathrm{\dots },v_n^i\}$ for every $i\in [k]$. We create an instance $(X,d,k^{\prime },\mathrm{\Delta })$ of the MSR problem, where $k^{\prime }=2k$, $X$ is the set of vertices of the weighted undirected graph $G^{\prime }$ and $d$ is the metric induced by $G^{\prime }$ as follows; see also Figure 1 for an illustration of the construction. The graph $G^{\prime }$ contains the following vertices:

• $\mathrm{■}$

  one vertex $v$ for every $v\in V(G)$,

• $\mathrm{■}$

  two vertices $x_{-}^i$ and $x_{+}^i$ for every $i\in [k]$,

• $\mathrm{■}$

  two sets $W_{-}^i$ and $W_{+}^i$ of $2k+1$ vertices each for every $i\in [k]$,

• $\mathrm{■}$

  a vertex $w_e$ for every non-edge $e=\{u,v\}\notin E(G)$ with endpoints $u\in V_i$ and $v\in V_j$ where . Let ${\overline{E}}_{i,j}$ denote the set of these vertices.

Moreover, $G^{\prime }$ has the following edges:

• $\mathrm{■}$

  an edge $\{w,x_{-}^i\}$ of weight ${\omega }_{-}(i)=2^{2i+1}\cdot i\cdot n$ for every $w\in W_{-}^i$ and every $i\in [k]$,

• $\mathrm{■}$

  an edge $\{w,x_{+}^i\}$ of weight ${\omega }_{+}(i)=2^{2i}\cdot i\cdot n$ for every $w\in W_{+}^i$ and every $i\in [k]$,

• $\mathrm{■}$

  an edge $\{x_{+}^i,v_h^i\}$ of weight $h+{\omega }_{+}(i)$ for every $i\in [k]$ and $h\in [n]$,

• $\mathrm{■}$

  an edge $\{x_{-}^i,v_h^i\}$ of weight $n-h+1+{\omega }_{-}(i)$ for every $i\in [k]$ and $h\in [n]$,

• $\mathrm{■}$

  an edge $\{x_{+}^i,w_e\}$ of weight $h+1+{\omega }_{+}(i)$ for every $i\in [k]$ and non-edge $e=\{v_h^i,u\}\notin E(G)$ with $u\in V(G)\setminus V_i$.

• $\mathrm{■}$

  an edge $\{x_{-}^i,w_e\}$ of weight $n-h+1+{\omega }_{-}(i)$ for every $i\in [k]$ and non-edge $e=\{v_h^i,u\}\notin E(G)$ with $u\in V(G)\setminus V_i$.

Finally, we set the cost $\mathrm{\Delta }$ to $nk+{\sum }_{i=1}^k({\omega }_{+}(i)+{\omega }_{-}(i))$.

This completes the construction of the instance $(X,d,k^{\prime },\mathrm{\Delta })$ of the MSR problem. Note that the construction can be achieved in $\mathrm{𝗉𝗈𝗅𝗒}(|V|,k)$-time, i.e., polynomial-time.

Moreover, $G^{\prime }$ is bipartite and because $G^{\prime }-\{x_{+}^1,x_{-}^1,\mathrm{\dots },x_{+}^k,x_{-}^k\}$ is an independent set, it holds that the vertex cover number of $G^{\prime }$ is at most $k^{\prime }=2k$. It therefore only remains to show that $G$ has a multicolored $k$-clique if and only if $(X,d,k^{\prime },\mathrm{\Delta })$ has a clustering into at most $k^{\prime }$ clusters of cost at most $\mathrm{\Delta }$.

We start by showing the following simple observation.

By construction, every edge of $G^{\prime }$ is incident to an anchor vertex of the form $x_{+}^i$ or $x_{-}^i$ for some $i\in [k]$. Hence, without loss of generality, we may assume that $u=x_{+}^i$ for some $i\in [k]$; the case $u=x_{-}^i$ is symmetric.

If $v\in W_{+}^i$, then $v$ has degree one in $G^{\prime }$, and hence $\{u,v\}$ is the unique $u$–$v$ path. Thus $d(u,v)=t$.

Otherwise, let $P$ be any $u$–$v$ path that does not use the edge $\{u,v\}$. The first edge of $P$ leaves $u=x_{+}^i$, and by construction every edge incident to $x_{+}^i$ has weight at least ${\omega }_{+}(i)$. We distinguish the following two cases.

Then as $v$ is adjacent exactly to $u=x_{+}^i$ and $x_{-}^i$, the last edge of $P$ must enter $v$ from $x_{-}^i$, and hence has weight at least ${\omega }_{-}(i)$. Therefore, $w(P)\ge {\omega }_{+}(i)+{\omega }_{-}(i)$.

Any $u$–$v$ path $P$ that avoids $\{u,v\}$ must enter $v$ from one of its remaining neighbors $x_{-}^i,x_{+}^j$, or $x_{-}^j$. If $P$ enters $v$ from $x_{-}^i$, then the last edge has weight at least ${\omega }_{-}(i)$, and hence $w(P)\ge {\omega }_{+}(i)+{\omega }_{-}(i)$. Otherwise, $P$ enters $v$ from $x_{+}^j$ or $x_{-}^j$, in which case the last edge has weight at least ${\omega }_{+}(j)$ or ${\omega }_{-}(j)$, respectively, and hence $w(P)\ge {\omega }_{+}(i)+{\omega }_{+}(j)$. Therefore, $w(P)\ge {\omega }_{+}(i)+\min \{{\omega }_{-}(i),{\omega }_{+}(j)\}$.

In both cases, by construction the weight of the direct $\{u,v\}$ edge satisfies $t\le {\omega }_{+}(i)+n+1$, while for all $j\ge 1$ we have ${\omega }_{+}(j)>n+1$ and ${\omega }_{-}(i)>n+1$. Hence $w(P)>t$, and therefore $d(u,v)\ge t$. $◀$

Towards showing the forward direction, let $S=\{v_{h_1}^1,v_{h_2}^2,\mathrm{\dots },v_{h_k}^k\}$ be a multicolored clique of size $k$ in $G$ for some $h_i\in [n]$ for every $i\in [k]$. We obtain a corresponding clustering $𝒞$ for $(X,d,k^{\prime },\mathrm{\Delta })$ as follows. For each $1\le i\le k$, the clustering $𝒞$ contains two clusters $C_{-}^i$ and $C_{+}^i$ with centers $x_{-}^i$ and $x_{+}^i$ and radii $r_{-}^i=n-h_i+2^{2i+1}\cdot i\cdot n$ and $r_{+}^i=h_i+2^{2i}\cdot i\cdot n$, respectively.

Clearly, the number of clusters $k^{\prime }=2k$ and the overall cost of the clustering $𝒞$ is

It therefore merely remains to show that for every vertex $v\in X=V(G^{\prime })$, there is a cluster in $𝒞$ containing $v$. We first show that the vertices in $V_i$’s, $W_{-}^i$, and $W_{+}^i$ are covered.

• $\mathrm{■}$

  $W_{-}^i\subseteq C_{-}^i$ because the weight $2^{2i+1}\cdot i\cdot n$ of any edge $\{x_{-}^i,w\}$ for $w\in W_{-}^i$ is at most the radius $r_{-}^i=n-h_i+2^{2i+1}\cdot i\cdot n$ of $C_{-}^i$ (as $1\le h_i\le n$).

• $\mathrm{■}$

  $W_{+}^i\subseteq C_{+}^i$ because the weight $2^{2i}\cdot i\cdot n$ of any edge $\{x_{+}^i,w\}$ for $w\in W_{+}^i$ is at most the radius $r_{+}^i=h_i+2^{2i}\cdot i\cdot n$ of $C_{+}^i$ (as $1\le h_i\le n$).

• $\mathrm{■}$

  $\{v_1^i,\mathrm{\dots },v_{h_i}^i\}\subseteq C_{+}^i$ because the weight of any edge $\{x_{+}^i,v_h^i\}$ is $h+2^{2i}\cdot i\cdot n$ and that the radius of $C_{+}^i$ is $r_{+}^i=h_i+2^{2i}\cdot i\cdot n$.

• $\mathrm{■}$

  $\{v_{h_i+1}^i,\mathrm{\dots },v_n^i\}\subseteq C_{-}^i$ because the weight of any edge $\{x_{-}^i,v_h^i\}$ is $n-h+1+2^{2i+1}\cdot i\cdot n$ and that the radius of $C_{-}^i$ is $r_{-}^i=n-h_i+2^{2i+1}\cdot i\cdot n$.

It remains to show that the vertices in ${\overline{E}}_{i,j}$ are covered by $𝒞$. Towards showing this, we observe the following.

Consider a vertex $w_e\in {\overline{E}}_{i,j}$ with $e=\{v_{\mathrm{\ell }}^i,u\}$ for some $\mathrm{\ell }\in [n]$ and $u\in V_j$. Then, the edge $\{x_{+}^i,w_e\}$ has weight $\mathrm{\ell }+1+2^{2i}\cdot i\cdot n$ and because $r_{+}^i=h+2^{2i}\cdot i\cdot n$, it follows from Observation 4 that $w_e\in C_{+}^i$ if and only if $h\ge \mathrm{\ell }+1$. Therefore, . Similarly, the edge $\{x_{-}^i,w_e\}$ has weight $n-\mathrm{\ell }+1+2^{2i+1}\cdot i\cdot n$ and because $r_{-}^i=n-h+2^{2i+1}\cdot i\cdot n$, it follows from Observation 4 that $w_e\in C_{-}^i$ if and only if $n-h\ge n-\mathrm{\ell }+1$, i.e., $h\le \mathrm{\ell }-1$. Therefore, $C_{-}^i\cap {\overline{E}}_{i,j}=\{w_{\{v_{\mathrm{\ell }}^i,u\}}\in {\overline{E}}_{i,j}|\mathrm{\ell }>h\wedge u\in V_j\}$. $◀$ Now consider the vertices in ${\overline{E}}_{i,j}$. By Observation 5, $C_{+}^i\cup C_{-}^i$ cover all vertices in ${\overline{E}}_{i,j}$ apart from the vertices corresponding to non-edges incident to $v_{h_i}^i$. Similarly, $C_{+}^j\cup C_{-}^j$ cover all vertices in ${\overline{E}}_{i,j}$ apart from the vertices corresponding to non-edges incident to $v_{h_j}^j$. Because $S$ is a multicolored $k$-clique in $G$, it holds that $v_{h_i}^i$ and $v_{h_j}^j$ are adjacent in $G$ and therefore there is no non-edge in $G$ that is both incident to $v_{h_i}^i$ and $v_{h_j}^j$ and hence ${\overline{E}}_{i,j}\subseteq C_{+}^i\cup C_{-}^i\cup C_{+}^j\cup C_{-}^j$.

For the reverse direction, let $𝒞$ be a solution (clustering) for $(X,d,k^{\prime },\mathrm{\Delta })$. We start by showing that $𝒞$ has $k^{\prime }=2k$ clusters and those use the vertices $x_{+}^1,x_{-}^1,\mathrm{\dots },x_{+}^k,x_{-}^k$ as centers with certain radii.

Let $\mathrm{\ell }\in [k]$ be the largest index such that there is no $h\in [n]$ such that $𝒞$ has clusters centered either at $x_{+}^{\mathrm{\ell }}$ with radius $r_{-}^{\mathrm{\ell }}\ge h+{\omega }_{+}(\mathrm{\ell })$ or at $x_{-}^{\mathrm{\ell }}$ with radius $r_{-}^{\mathrm{\ell }}\ge n-h+{\omega }_{-}(\mathrm{\ell })$, respectively. Note that the statement of the claim now already applies for every ${\mathrm{\ell }}^{\prime }\in [k]$ with ${\mathrm{\ell }}^{\prime }>\mathrm{\ell }$. We distinguish the following cases.

Because $|W_{-}^{\mathrm{\ell }}|>k^{\prime }$, there is a vertex, say $w\in W_{-}^{\mathrm{\ell }}$, that is not the center of any cluster in $𝒞$. Let $C$ be the cluster in $𝒞$ that contains $w$. Then, as $w$ is not the center in $𝒞$ and has $x_{-}^{\mathrm{\ell }}$ as its unique neighbor, $C$ must also contain $x_{-}^{\mathrm{\ell }}$, but since $x_{-}^{\mathrm{\ell }}$ is not the center of $C$ and every edge incident to $x_{-}^{\mathrm{\ell }}$ has cost at least ${\omega }_{-}(\mathrm{\ell })$, we obtain that $C$ has radius at least $2{\omega }_{-}(\mathrm{\ell })$. Because the statement of the claim holds for every $i>\mathrm{\ell }$, we obtain that the clusters with centers $x_{+}^i$ and $x_{-}^i$ exists for every $i$ where and have total cost at least $(n(k-\mathrm{\ell })+{\sum }_{i>\mathrm{\ell }}{\omega }_{+}(i)+{\omega }_{-}(i))$. Moreover, even if $C$ is one of these clusters, it is easy to see that in order to cover $w$ the radius of such a cluster would have to be increased by at least $2{\omega }_{-}(\mathrm{\ell })-n$ above the lower bound stated in the claim. Therefore, the the cost of $𝒞$ is at least $(n(k-\mathrm{\ell }-1)+{\sum }_{i>\mathrm{\ell }}{\omega }_{+}(i)+{\omega }_{-}(i))+2{\omega }_{-}(\mathrm{\ell })$. Because $\mathrm{\Delta }=nk+{\sum }_{i=1}^k({\omega }_{+}(i)+{\omega }_{-}(i))$, it suffices to show that , which is equivalent to showing that , which is shown as follows. We start by expanding the left hand term

where the last inequality follows as for all $\mathrm{\ell }\ge 1$.

Because $|W_{+}^{\mathrm{\ell }}|>k^{\prime }$, there is a vertex, say $w\in W_{+}^{\mathrm{\ell }}$, that is not the center of any cluster in $𝒞$. Let $C$ be the cluster in $𝒞$ that contains $w$. Then, $C$ must also contain $x_{+}^{\mathrm{\ell }}$, but since $x_{+}^{\mathrm{\ell }}$ is not the center of $C$ and every edge incident to $x_{+}^{\mathrm{\ell }}$ has cost at least ${\omega }_{+}(i)$, we obtain that $C$ has radius at least $2{\omega }_{+}(i)$. Moreover, the radius of the cluster, say $C^{\prime }\in 𝒞$, with center $x_{-}^i$ is at least ${\omega }_{-}(i)$, since otherwise $C^{\prime }$ only contains $x_{-}^i$ and at least one of the clusters containing a vertex from $W_{-}^i$ must already contain $x_{-}^i$ (because $|W_{-}^i|>k^{\prime }$). Therefore, the cost of $𝒞$ is at least $(n(k-\mathrm{\ell })+{\sum }_{{\mathrm{\ell }}^{\prime }>\mathrm{\ell }}{\omega }_{+}(i)+{\omega }_{-}(i))+2{\omega }_{+}(i)+{\omega }_{-}(i)=(n(k-\mathrm{\ell })+{\sum }_{{\mathrm{\ell }}^{\prime }>\mathrm{\ell }}{\omega }_{+}(i)+{\omega }_{-}(i))+2{\omega }_{-}(i)$ and therefore the same lower bound on the cost obtained in Case 1. Therefore, using the same calculation as in Case 1, we obtain that this cost lower bound is already larger than $\mathrm{\Delta }$.

Note that because of Case 1 and Case 2, we can from now on assume that $𝒞$ has a cluster with center $c$ for every $c\in \{x_{+}^1,x_{-}^1,\mathrm{\dots },x_{+}^k,x_{-}^k\}$ and because $|\{x_{+}^1,x_{-}^1,\mathrm{\dots },x_{+}^k,x_{-}^k\}|=k^{\prime }$, $𝒞$ does not have any other clusters. Moreover, if $C\in 𝒞$ is a cluster with center $x_{+}^i$ (or $x_{-}^i$), then its radius $r_{+}^i$ ($r_{-}^i$) must be at least ${\omega }_{+}(i)$ (${\omega }_{-}(i)$). This is because otherwise $C$ only contains $x_{+}^i$ ($x_{-}^i$) but because $|W_{+}^i|>k^{\prime }$ ($|W_{-}^i|>k^{\prime }$), there must be another cluster containing some $w\in W_{+}^i$ ($w\in W_{-}^i$) and $x_{+}^i$ ($x_{-}^i$) and therefore $C$ would not be needed. It follows that the cost of the clustering is already at least $n(k-\mathrm{\ell })+{\sum }_{i=1}^k({\omega }_{+}(i)+{\omega }_{-}(i))$, leaving only $n\mathrm{\ell }$ for additional costs.

Because the conditions of the claim are not satisfied for $\mathrm{\ell }$, it must now holds that . But then, there must be some $h\in \{0\}\cup [n-1]$ such that $r_{+}^{\mathrm{\ell }}={\omega }_{+}(\mathrm{\ell })+h$ and , which implies that the vertex $v_{h+1}^i$ is not covered by $C_{+}^{\mathrm{\ell }}$ or $C_{-}^{\mathrm{\ell }}$. But then, $v_{h+1}^i$ must be contained in some other cluster, say $C$, with center $c\in \{x_{+}^1,x_{-}^1,\mathrm{\dots },x_{+}^k,x_{-}^k\}\setminus \{x_{+}^{\mathrm{\ell }},x_{-}^{\mathrm{\ell }}\}$. Assume that $c=x_{\lambda }^i$ for some $i\in [k]\setminus \{\mathrm{\ell }\}$ and $\lambda \in \{+,-\}$. Then, in order to cover $v_{h+1}^i$, the radius of $C$ must be at least by $2{\omega }_{+}(\mathrm{\ell })$ larger than the lower bound that we computed for $C$ above, i.e., the cost of the clustering is now at least $n(k-\mathrm{\ell })+{\sum }_{i=1}^k({\omega }_{+}(i)+{\omega }_{-}(i))+2{\omega }_{+}(\mathrm{\ell })$. Since $2{\omega }_{+}(\mathrm{\ell })=2\cdot 2^{2\mathrm{\ell }}\cdot \mathrm{\ell }\cdot n>n\mathrm{\ell }$, this exceeds the allowed cost of $\mathrm{\Delta }=nk+{\sum }_{i=1}^{\mathrm{\ell }}({\omega }_{+}(i)+{\omega }_{-}(i))$ and concludes the proof of the claim. $\mathrm{⊲}$

Because of Claim 6, we obtain that $𝒞$ contains exactly one cluster $C_c$ with center $c$ for every $c\in \{x_{+}^1,x_{-}^1,\mathrm{\dots },x_{+}^k,x_{-}^k\}$ and no other clusters. Moreover, for every $i\in [k]$, there is an $h_i\in [n]$ such that the cluster in $𝒞$ with center at $x_{+}^i$ or $x_{-}^i$ has radius $r_{+}^i\ge h_i+{\omega }_{+}(i)$ or $r_{-}^i\ge n-h_i+{\omega }_{-}(i)$, respectively. Since the total cost is at most $\mathrm{\Delta }$, these bounds are tight, and hence $r_{+}^i=h_i+{\omega }_{+}(i)$ and $r_{-}^i=n-h_i+{\omega }_{-}(i)$ for all $i\in [k]$. We now claim that the vertex set $S=\{v_{h_1}^1,\mathrm{\dots },v_{h_k}^k\}$ is a $k$-clique of $G$. In other words, it is sufficient to show that $\{v_{h_i}^i,v_{h_j}^j\}\in E(G)$ for every . Because of Observation 5, we obtain that for every $\mathrm{\ell }\in \{i,j\}$, it holds that $C_{x_{+}^{\mathrm{\ell }}}\cup C_{x_{-}^{\mathrm{\ell }}}$ cover exactly all vertices in ${\overline{E}}_{i,j}$ that do not correspond to non-edges incident to $v_{h_{\mathrm{\ell }}}^{\mathrm{\ell }}$. Therefore, $C_{x_{+}^i}\cup C_{x_{-}^i}\cup C_{x_{+}^j}\cup C_{x_{-}^j}$ cover all vertices in ${\overline{E}}_{i,j}$ if and only if $G$ does not contain a non-edge between $v_{h_i}^i$ and $v_{h_j}^j$, i.e., if and only if $\{v_{h_i}^i,v_{h_j}^j\}\in E(G)$. In the following, we observer that every vertex in ${\overline{E}}_{i,j}$ must be covered by one of the clusters $C_{x_{+}^i}$, $C_{x_{-}^i}$, $C_{x_{+}^j}$, $C_{x_{-}^j}$. Suppose this is not the case, i.e., there exists a vertex $w_e\in E_{i,j}$ that is not covered by one of the clusters $C_{x_{+}^i}$, $C_{x_{-}^i}$, $C_{x_{+}^j}$, $C_{x_{-}^j}$. As $𝒞$ is a valid clustering of $(X,d,k,\mathrm{\Delta })$ and hence $w_e$ must be covered by some other cluster centered at some $x_{+}^t$ (or at $x_{-}^t$) where $t\in [k]\ne i,j$, which by construction must have radius more than $r_{+}^t=2^{2t}\cdot t\cdot n+h_{t^{\prime }}$ (or more than $r_{-}^t=2^{2t+1}\cdot t\cdot n+n-h_{t^{\prime }}$) for some $h_{t^{\prime }}\in V_t$, a contradiction to Claim 6. This concludes the reverse direction of the proof. $◀$ It is interesting to note that the result of Theorem 2 even holds for the variant of MSR, where the set of centers is given and one merely needs to find the right radius for every center.

It follows from Theorem 1 that MSR is $\mathrm{𝖭𝖯}$-hard and $𝖶$[1]-hard parameterized by $k+\mathrm{\Delta }$ even on metrics induced by weighted bipartite graphs and we will show the theorem by providing a parameterized and polynomial-time reduction from this case to the two cases stated in the theorem. Let $(X,d,k,\mathrm{\Delta })$ be an instance of the MSR problem such that $X$ is the set of vertices of the weighted bipartite graph $G$ with partition $\{A,B\}$ and $d$ is the metric induced by $G$. To reduce to the case of a complete graph, let $(X,d^{\prime },k,\mathrm{\Delta })$ be the instance of MSR such that $d^{\prime }$ is the metric induced by the graph $G^{\prime }$ obtained from $G$ after adding an edge of cost $\mathrm{\Delta }+1$ between any two vertices in $G$ that are not adjacent. Similarly, to reduce to the case of a complete bipartite graph, let $(X,d^{\prime \prime },k,\mathrm{\Delta })$ be the instance of MSR such that $d^{\prime \prime }$ is the metric induced by the graph $G^{\prime \prime }$ obtained from $G$ after adding an edge of cost $\mathrm{\Delta }+1$ between any vertex in $A$ and any vertex in $B$.

It is straightforward to show that these two constructions provide parameterized and polynomial-time reductions as required. $◀$

While Theorem 7 excludes fixed-parameter tractability for any dense structural parameter plus $k+\mathrm{\Delta }$, we will now show that MSR on metrics induced by weighted graphs is fixed-parameter tractable parameterized by the treewidth of the graph plus the cost of the clustering. To do so, we need the following definitions.

Let $G$ be an weighted graph and let $v\in V(G)$. We denote by $N_r[v]$ the $r$-neighborhood of $v$, i.e., the all vertices that have distance at most $r$ to $v$. Moreover, we denote by $\mathrm{\#}(v)$ the number of distinct sets in $\{N_r[v]|r\in ℝ\}$ and by $\mathrm{\#}(G)$ the maximum of $\mathrm{\#}(v)$ over all vertices $v\in V(G)$. Using these notions, fixed-parameter tractability for treewidth plus cost now follows immediately from the algorithm used to show [14, Theorem 1] by observing that the number of vertices $|V|$ in their statement of the run-time of the algorithm can be easily replaced by the more concise parameter $\mathrm{\#}(G)$.