Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs

Abstract

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 2O(n1−1/d)-time algorithms on unit ball graphs in Rd [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 R3, 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 2O(√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 2o(n)-time algorithm on unit ball graphs in dimension 5, unless the ETH fails.