2026-08-25T16:34:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27273 2026-08-25T13:18:20Z ddc:004 open_access

Small Independent Sets Versus Small Separator in Geometric Intersection Graphs Marin, Malory Watrigant, Rémi Subexponential Algorithms Unit Disk Graphs 2-Subcoloring Two-Sets Cut-Uncut While most classical NP-hard graph problems cannot be solved in time 2^o(n) on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomenon and admit optimal algorithms running in time 2^O(√n) on certain geometric intersection graphs, such as planar graphs or unit disk graphs. In 2018, de Berg et al. developed a general algorithmic framework for such problems on intersection graphs of similarly sized fat objects in ℝ^d, achieving running times of the form 2^O(n^{1-1/d}), along with matching lower bounds under ETH. In this paper, we identify problems that do not exhibit the square-root phenomenon, yet still admit subexponential algorithms on intersection graphs of similarly sized fat objects in ℝ^d, for every fixed dimension d ⩾ 2. We introduce the notion of a weak square-root phenomenon: problems that can be solved in time 2^Õ(n^{1-1/(d+1)}), and for which matching lower bounds hold under ETH. We develop both an algorithmic framework and a corresponding lower bound framework. As concrete examples, we show that the problems 2-Subcoloring and Two Sets Cut-Uncut exhibit this behavior. Our algorithms rely on a new win-win structural theorem, which can be informally stated as follows: every such graph admits a sublinear separator whose removal leaves connected components with sublinear independence number. To facilitate the design of these algorithms, we introduce a new graph parameter, the α-modulator number, which generalizes both the independence number and the vertex cover number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Malory Marin and Rémi Watrigant 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.137 urn:nbn:de:0030-drops-272734 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.137 eng https://creativecommons.org/licenses/by/4.0/legalcode