On connections between k-coloring and Euclidean k-means
<|reference_start|>On connections between k-coloring and Euclidean k-means: In the Euclidean $k$-means problems we are given as input a set of $n$ points in $\mathbb{R}^d$ and the goal is to find a set of $k$ points $C\subseteq \mathbb{R}^d$, so as to minimize the sum of the squared Euclidean distances from each point in $P$ to its closest center in $C$. In this paper, we formally explore connections between the $k$-coloring problem on graphs and the Euclidean $k$-means problem. Our results are as follows:   $\bullet$ For all $k\ge 3$, we provide a simple reduction from the $k$-coloring problem on regular graphs to the Euclidean $k$-means problem. Moreover, our technique extends to enable a reduction from a structured max-cut problem (which may be considered as a partial 2-coloring problem) to the Euclidean $2$-means problem. Thus, we have a simple and alternate proof of the NP-hardness of Euclidean 2-means problem.   $\bullet$ In the other direction, we mimic the $O(1.7297^n)$ time algorithm of Williams [TCS'05] for the max-cut of problem on $n$ vertices to obtain an algorithm for the Euclidean 2-means problem with the same runtime, improving on the naive exhaustive search running in $2^n\cdot \text{poly}(n,d)$ time.   $\bullet$ We prove similar results and connections as above for the Euclidean $k$-min-sum problem.<|reference_end|>
@article{aman2024on,
    title={On connections between k-coloring and Euclidean k-means},
    author={Enver Aman, Karthik C. S., and Sharath Punna},
    journal={arXiv preprint arXiv:2405.13877},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.13877},
    primaryClass={cs.CG cs.CC cs.DS}
}