Twin-width approximation for unordered graphs

Open Challenge: Efficient Approximation of Twin-Width for Unordered Graphs · arXiv:2111.00282

arXiv Problem medium confidence— first stated 2022-05-31

Authors: Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé

Status partial high confidence

The open challenge of efficiently approximating twin-width for unordered graphs remains unresolved for general graphs, as confirmed by Bonnet's own open-questions page (updated 2025). Partial progress exists: an FPT approximation algorithm has been found for graphs with small feedback edge number (Balabán, Ganian, Rocton 2023), but no XP or FPT approximation is known for the general unordered case. Exact computation of twin-width is NP-hard—deciding whether twin-width is at most 4 is NP-complete.

Cited literature (1)

partial Computing Twin-Width Parameterized by the Feedback Edge Number (2023)

Jakub Balabán, Robert Ganian, Mathis Rocton · arXiv preprint · arXiv:2310.08243

Provides an FPT approximation algorithm for twin-width on graphs parameterized by feedback edge number, computing an ℓ-contraction sequence or certifying twin-width ≥ ℓ; does not address the general unordered graph case.

Reviewer notes. Bonnet's open questions page (https://perso.ens-lyon.fr/edouard.bonnet/openQuestions.html) explicitly lists FPT approximation for general unordered graphs as still the missing piece; the challenge is open with high confidence. Partial progress exists only for restricted parameterizations such as feedback edge number.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Efficiently approximating twin-width (that is, returning an $f(d)$-sequence when the twin-width of the input is at most $d$) remains an open challenge for unordered graphs.

Context

The authors note that efficient approximation of twin-width has been achieved for classes of totally ordered binary structures and for all mentioned classes of bounded twin-width (bounded tree-width, proper minor-closed, hereditary subclasses of permutation graphs, etc.), but the problem is unresolved for general unordered graphs. This open challenge is stated in the introduction as a key missing piece in the twin-width landscape.

Notes. Stated in running prose in the introduction without a labelled theorem environment. The PDF extraction is incomplete — the paper content cuts off mid-sentence in Section 2.1 (before the bulk of the technical sections), so additional labelled conjectures/problems/questions in later sections of the paper are not captured here.

Source paper

Twin-width VI: the lens of contraction sequences
Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé · 2022-05-31
https://arxiv.org/abs/2111.00282 PDF source