Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
<|reference_start|>Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs: In Clique Cover, given a graph $G$ and an integer $k$, the task is to partition the vertices of $G$ into $k$ cliques. Clique Cover on unit ball graphs has a natural interpretation as a clustering problem, where the objective function is the maximum diameter of a cluster.   Many classical NP-hard problems are known to admit $2^{O(n^{(1 - 1/d)})}$-time algorithms on unit ball graphs in $\mathbb{R}^d$ [de Berg et al., SIAM J. Comp 2018]. A notable exception is the Maximum Clique problem, which admits a polynomial-time algorithm on unit disk graphs and a subexponential algorithm on unit ball graphs in $\mathbb{R}^3$, but no subexponential algorithm on unit ball graphs in dimensions 4 or larger, assuming the ETH [Bonamy et al., JACM 2021].   In this work, we show that Clique Cover also suffers from a "curse of dimensionality", albeit in a significantly different way compared to Maximum Clique. We present a $2^{O(\sqrt{n})}$-time algorithm for unit disk graphs and argue that it is tight under the ETH. On the other hand, we show that Clique Cover does not admit a $2^{o(n)}$-time algorithm on unit ball graphs in dimension $5$, unless the ETH fails.<|reference_end|>
@article{koana2024subexponential,
    title={Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball
  Graphs},
    author={Tomohiro Koana, Nidhi Purohit, Kirill Simonov},
    journal={arXiv preprint arXiv:2410.03609},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.03609},
    primaryClass={cs.DS cs.CG}
}