Abstract
We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.
Introduction
Twin-width is a structural graph parameter introduced in 2020 that has rapidly gained prominence in theoretical computer science. It measures the "structuredness" of a graph—similar to parameters like treewidth—where low twin-width enables efficient algorithms for otherwise NP-hard problems. However, determining the exact twin-width of a graph is computationally intensive; deciding if a graph has a twin-width of just 4 is NP-complete, and no general approximation algorithms currently exist.
Touiouidth is a high-performance C++ solver developed for the "Exact Track" of the 2023 PACE Challenge. The challenge required researchers to find the precise twin-width for a benchmark set of 200 diverse graphs. Touiouidth addresses this by combining a branch-and-bound framework with aggressive symmetry breaking, bit-level optimizations, and effective heuristics.
Methodology
The core of Touiouidth is a branch-and-bound algorithm that searches for an optimal contraction sequence. This sequence involves merging pairs of vertices until a single vertex remains. During these merges, "red edges" are introduced to represent inconsistencies between the neighborhoods of the merged vertices. The objective is to minimize the maximum "red degree"—the number of red edges incident to any single vertex—throughout the sequence.
Trigraph Representation and Reductions
The solver operates on trigraphs, which distinguish between standard (black) edges and error (red) edges. To simplify the search space, the solver employs "Reduction Rule 1," a generalization of twin-vertex identification. This allows the solver to identify and simplify trigraphs mid-search, accelerating the exact computation.
Symmetry Breaking and Search Space Reduction
A significant challenge in finding contraction sequences is the high degree of redundancy; merging vertex pairs $(u, v)$ then $(x, y)$ often results in the same trigraph as merging $(x, y)$ then $(u, v)$. Touiouidth implements a "forbidden contractions" set to prune these redundant paths. Furthermore, the solver tracks "independent" contractions. If a contraction does not "touch" the two-hop neighborhood of a previously skipped pair, it remains skipped, effectively pruning the search tree without sacrificing optimality.
Bit-Parallelism and Priority Branching
For graphs with up to 64 vertices, Touiouidth utilizes 64-bit integers (unsigned long long) to represent adjacency lists. This enables the use of bitwise CPU instructions for set operations like unions and intersections required during merges, significantly reducing overhead per search node. To guide the search, the solver uses Priority Branching. Instead of arbitrary selection, it prioritizes merges using a metric $\Delta(u, v)$ that favors contractions creating the fewest new red edges.
Solver Workflow
Touiouidth manages its 30-minute execution window per graph through a structured three-phase workflow:
- Lower Bound (15 mins): The solver first attempts to establish the highest possible starting twin-width using induced subgraphs.
- Upper Bound (5 mins): Greedy and randomized heuristics (Heuristic1 and Heuristic2) are employed to find a low-width sequence. The authors found that Heuristic2 was particularly effective, often finding upper bounds that matched the lower bounds, allowing the solver to bypass the exact search entirely.
- Exact Search (10 mins): If a gap remains between the bounds, the solver uses the branch-and-bound algorithm to find the exact value.
Results and Performance
Evaluated on the 2023 PACE Challenge Exact Track dataset, Touiouidth demonstrated high efficiency. The combination of bucket sort for branching and bitset-based adjacency lists minimized computational overhead. The synergy between the lower-bounding techniques and the randomized heuristics proved robust, frequently narrowing the search space before the exact phase began.
Conclusion and Future Directions
While Touiouidth provides a highly optimized architecture for twin-width computation, the exact branch-and-bound phase remains limited by the problem's inherent complexity, especially for large or unstructured graphs. Future work may involve integrating more sophisticated lower-bounding techniques or SAT-solver methods. Additionally, extending the bitset optimization beyond the 64-vertex limit could provide further performance gains for mid-sized instances.
Summary updated