{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaernkwoxv6nsytofldf4cnht6hdrtpixmdcejzuqk3bbzzrku3ma",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkosgzbd25n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.26533v1",
  "publishedAt": "2026-04-30T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Malory Marin",
    "Rémi Watrigant"
  ],
  "textContent": "**Authors:** Malory Marin, Rémi Watrigant\n\nWhile 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(\\sqrt{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 $\\mathbb{R}^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 $\\mathbb{R}^d$, for every fixed dimension $d \\geqslant 2$. We introduce the notion of a weak square-root phenomenon: problems that can be solved in time $2^{\\tilde{O}(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.",
  "title": "Small Independent Sets versus Small Separator in Geometric Intersection Graphs"
}