UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
Andrei Arhire, Matei Chiriac, Radu Timofte · 2025
Read UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm by Andrei Arhire, Matei Chiriac, Radu Timofte (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06486.txt.
Introduction
Andrei Arhire, Matei Chiriac, and Radu Timofte compute twin-width, a measure of how close a graph sits to the simple structure of a co-graph. Coined in 2020, twin-width has quickly driven progress in graph theory and algorithm design. The 2023 PACE Challenge gathered benchmark graphs plus heuristic and exact solvers for the problem.
The team offers two solvers, one exact and one heuristic, built for graphs of arbitrary structure. Their entries performed strongly in the contest, with the exact solver taking the best student result and fourth place overall. Public source code accompanies the work so others can apply the methods and extend the research.
Catalog record
| CREATOR | Andrei Arhire, Matei Chiriac, Radu Timofte |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06486
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm Andrei Arhire, Matei Chiriac, Radu Timofte Abstract Twin-width is a recently formulated graph and matrix invariant that intuitively quantifies how far a graph is from having the structural simplicity of a co-graph. Since its introduction in 2020, twin-width has received increasing attention and has driven research leading to notable advances in algorithmic fields, including graph theory and combinatorics. The 2023 edition of the Parameterized Algorithms and Computational Experiments (PACE) Challenge aimed to fulfill the need for a diverse and consistent public benchmark encompassing various graph structures, while also collecting state-of-the-art heuristic and exact approaches to the problem. In this paper, we propose two algorithms for efficiently computing the twin-width of graphs with arbitrary structures, comprising one exact and one heuristic approach. The proposed solutions performed strongly in the competition, with the exact algorithm achieving the best student result and ranking fourth overall. We release our source code publicly to enable practical applications of our work and support further research. Alexandru Ioan Cuza University of Iași, Romania and [email protected] University, Germany and [email protected] Vision Lab, CAIDAS & IFI, and University of Würzburg, Germany and Alexandru Ioan Cuza University of Iași, [email protected] ccs Theory of computation Graph algorithms analysis keywords twin-width, dynamic programming, local search † † copyright: Andrei Arhire † † runningauthor: A. Arhire, M. Chiriac, R. Timofte † † supplement: The source code is available on Zenodo (10.5281/zenodo.8010483) and GitHub (https://github.com/AndreiiArhire/PACE2023) . † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The concept of twin-width was introduced in [ 13 ] as a new measure of structural complexity for graphs, defined through sequences of vertex contractions that control the irregularities in adjacency that emerge during contraction. The authors initially proposed a fixed-parameter tractable (FPT) algorithm for first-order (FO) model checking on graphs of bounded twin-width, and subsequently developed a series of theoretical results expanding the structural and algorithmic understanding of the parameter ( [ 5 ] , [ 7 ] , [ 6 ] , [ 8 ] , [ 9 ] , [ 10 ] , [ 12 ] ). The idea of twin-width has rapidly attracted significant attention in theoretical computer science, inspiring numerous studies on its algorithmic ( [ 11 ] , [ 4 ] ), combinatorial ( [ 16 ] , [ 25 ] ), and logical ( [ 15 ] , [ 17 ] ) aspects. Although deciding whether a graph has twin-width at most four is NP-complete [ 4 ] , a wide range of graph classes are known to have bounded twin-width, including trees and graphs of bounded tree-width, bounded rank-width graphs, subgraphs of d -dimensional grids, map graphs, and unit interval graphs. Among various graph families, the class of planar graphs has seen substantial theoretical progress and active research over recent years, with the known upper bound on their twin-width gradually improving ( [ 19 ] , [ 20 ] , [ 3 ] ) from 583, as established in [ 14 ] , to 8 in [ 18 ] , while a lower bound of 7 was reported in [ 21 ] . As a result of these theoretical advances, the establishment of a public benchmark encompassing graphs from diverse classes and sizes has become a pressing requirement. The PACE Challenge [ 24 ] is an annual competition that aims to close the gap between theoretical research on parameterized algorithms and their practical applications since 2015. The 2023 edition [ 2 ] focused on efficient twin-width computation, encouraging the development of state-of-the-art exact and heuristic approaches on a new, publicly available, and diverse benchmark introduced by the organizers. Our contribution consists of developing two solvers for computing the twin-width of graphs with arbitrary structures. Specifically, one is a heuristic method designed to quickly find a good upper bound using local search, while the other is an exact solver based on dynamic programming that integrates the heuristic to improve efficiency. Both solvers were submitted to the PACE 2023 Challenge, and in the final global leaderboard [ 23 ] , the heuristic solver ranked sixth, while the exact solver ranked fourth, achieving the best student results. The remainder of the paper is organized as follows. Section 2 presents the preliminaries. Section 3 describes the algorithms implemented by the solvers. Section 4 discusses the upper and lower bounds used. Section 5 provides the technical details, while the conclusions are drawn in Section 6. 2 Preliminaries Consider a trigraph G=(V,B,R) consisting of a set of vertices V , black edges B , and red edges R . Here, B and R are subsets of \binom{V}{2} , and they do not have any common elements ( B\cap R=\emptyset ). Without any specific indication, a graph H=(V,E) is treated as the trigraph H^{\prime}=(V,E,\emptyset) . In this context, we define the red degree of a vertex as the number of incident red edges connected to that vertex. When two vertices are compressed (refer to fig. 1 ), a new vertex is formed by considering the edges associated with the original vertices, and subsequently, the original vertices are removed from the graph. Figure 1: Vertex contraction example showing how red and black edges are updated when merging vertices u and v into uv . Formally, the union of vertices x and y , with B_{x} , B_{y} , R_{x} , and R_{y} representing the sets of incident black and red edges, gives rise to a new vertex z with the following definitions: • A vertex u\in R_{z} if u\in{B_{x}\cup B_{y}\cup R_{x}\cup R_{y}}\setminus{B_{x}\cap B_{y}} . • A vertex u\in B_{z} if u\in B_{x}\cap B_{y} . Figure 2: Contraction sequence showing how the red and black edges are updated. The resulting graph has twin-width at most 2. Adapted from [ 4 ] . According to the requirements of the challenge format, the solver assigns the same label to z as that of x . Following this process of reducing the graph to a single vertex through these operations, a sequence of |V|-1 pairs of vertices is generated. The width of such a sequence is defined as the maximum red degree encountered at any vertex during the contraction process. The twin-width represents the minimum width achievable through a sequence of (refer to fig. 2 ) that reduces the graph. 3 Description of the Solver The solver can be divided into four stages: 1. Contract vertices that do not create any red edges when contracted; 2. Find an upper bound for the entire graph using a hill climbing algorithm; 3. Determine a lower bound for each connected component by using dynamic programming on multiple sub-graphs; 4. Compute the twin-width using dynamic programming. Evaluate components in descending order based on their number of vertices (expected twin-width). A component can yield a suboptimal solution as long as another component has a twin-width greater than or equal to its width. The core of the solver relies on a dynamic programming algorithm