# Deciding twin-width at most 4 is NP-complete

arXiv: https://arxiv.org/abs/2112.08953 · HTML: https://mlsanity.com/paper/2112.08953/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2021.

## Built on by (most cited first, 1 of 1)

- [Component twin-width as a parameter for BINARY-CSP and its semiring generalisations](https://mlsanity.com/paper/2207.12368/) (2022)

## Abstract (arXiv)

We show that determining if an n-vertex graph has twin-width at most 4 is NP-complete, and requires time 2Omega(n/log n) unless the Exponential-Time Hypothesis fails. Along the way, we give an elementary proof that n-vertex graphs subdivided at least 2 log n times have twin-width at most 4. We also show how to encode trigraphs H (2-edge colored graphs involved in the definition of twin-width) into graphs G, in the sense that every d-sequence (sequence of vertex contractions witnessing that the twin-width is at most d) of G inevitably creates H as an induced subtrigraph, whereas there exists a partial d-sequence that actually goes from G to H. We believe that these facts and their proofs can be of independent interest.