Proof of NP-hardness of the k-means clustering problem for $k\geqslant 3$

Question

coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems to be separately proved in various places (publications as well as some online PDFs). For instance, the article NP-hardness of Euclidean sum-of-squares clustering (link found on Wikipedia) proves the result for $k=2$ only.

What I don't understand well is that proving such a result seems to lead to an easy one-sentence generalization (see below) to any value of $k$. Knowing very little about the k-means problem, I am pretty sure I am missing something but why not add the following claim to all these articles?

Having proved the NP-hardness of the k-means problem for $k=2$, we notice that any instance of the problem for some value of $k$ can be reduced to an instance of the same problem for the case $k+1$ (by adding one more point to the dataset far enough from all existing points), we easily prove the NP-hardness of the problem for any value of $k$.

For instance, say I want to solve the problem for some $k$ and $n$ points in $[0,1]$. I know the sum of the square is smaller than $n$. I now add the new point $1+\sqrt{2n}+\epsilon$ to the dataset, building an instance of the clustering problem for $k+1$. The solution must put this new point alone in a separate cluster (thus not changing the previous sum of squares); because in any other case the new sum of squares would be greater than $n$. Thus solving this new problem for $k+1$ clusters immediately solves the initial instance of the problem. Of course, the very same idea can be used for the plane or any euclidean space.

Answer 1

I think this is a matter of convention in how people communicate the results. It would be one thing to say "The k-means problem is NP-hard [when k is allowed to be any number up to $n$, the number of data points]". People might still then hope that there was, say, a $O(n^k)$ algorithm. Subsequently someone may prove that there is some finite $k$ such that the k-means problem is NP-hard, but that this required $k \ge 10^5$. Then people would surely try to modify the approach to show hardness for smaller and smaller values of $k$, until the end of the race: that for all $k \ge k_0$ it is NP-hard, and for all $k < k_0$ it's in $P$.

Each of those improvements, where they reduce $k_0$, would often write their result as "We show that k-means is NP-hard even when $k=2$". They certainly could write $\ge$, but that feels like a given, and to them their theorem might "really" be saying, "We've shown $k_0 \le 2$". And they'll be focused on their own particular reduction, where $k=2$.

In short: you're right, yes, $k=2$ could be replaced with $k\ge 2$. But to the people writing that theorem, and most reading it, those really just feel like the same thing.