{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiaft5b5bghefxt7yomkzohpyppgxexk5xc6nvm5fsuzs2dukanzcy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpo3k2imgdz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2607.00244v1",
  "publishedAt": "2026-07-02T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Édouard Bonnet",
    "Maël Dumas",
    "Julien Duron"
  ],
  "textContent": "**Authors:** Édouard Bonnet, Maël Dumas, Julien Duron\n\nFor every $\\varepsilon > 0$, Max Independent Set admits a polynomial-time $n^\\varepsilon$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Bergé et al., STACS '23]. The approximation factor actually obtained is more precisely $n^{O(1/ \\log \\log n)}$. Prior to the current paper, no approximation hardness was known for this problem, and the existence of a polynomial-time approximation scheme (PTAS) was repeatedly raised as an open question. We answer this question in a strong sense: We show that there is a constant $γ> 0$ such that a polynomial-time $n^{γ/ (\\log \\log n)^2}$-approximation algorithm for Max Independent Set on graphs of twin-width at most 4 would refute the Exponential-Time Hypothesis (ETH). This lower bound further holds if a 4-sequence is provided as part of the input. We show the same hardness of approximation for Min Coloring, which also has a nearly matching $n^{O(1/ \\log \\log n)}$-approximation algorithm on graphs of effectively bounded twin-width. We also clarify the parameterized complexity of $k$-Independent Set on graphs of bounded radius-$r$ merge-width when the range of $r$ is limited. There is a fixed-parameter tractable algorithm for $k$-Independent Set on graphs given with radius-$2^{O(k^2)}$ merge sequences of bounded width [Dreier and Toruńczyk, STOC '25]. We complement this result by showing that $k$-Independent Set is W[1]-hard on graphs given with radius-$o(k)$ merge sequences of bounded width. We further show that this result also holds for $k$-Dominating Set.",
  "title": "Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width"
}