Twin-width is a powerful graph invariant that supports the efficient solution of various NP-hard problems when the input graph has a bounded twin-width. First-order model checking is fixed-parameter tractable on graph classes of bounded twin-width 11. This work introduces two algorithmic strategies for exact twin-width computation: SAT encodings and a Branch the Branch & Bound algorithm leverages cached partial solutions for improved efficiency on larger graphs. We propose a verification framework combining these methods and yield verifiable proofs for computed twin-width. Our research contributes conceptual insights into twin-width computation, including new contraction orderings and lower and upper bound techniques that can be of independent interest. We accompany our theoretical developments with a rigorous experimental evaluation.
Schidler et al. (Wed,) studied this question.