2026-07-20T12:07:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22236 2024-12-05T15:32:41Z ddc:004 open_access

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs Koana, Tomohiro Purohit, Nidhi Simonov, Kirill Clique cover diameter clustering subexponential algorithms unit disk 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 ℝ^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 ℝ³, 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(√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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomohiro Koana and Nidhi Purohit and Kirill Simonov 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.10 urn:nbn:de:0030-drops-222369 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode