UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914144425345024 |
|---|---|
| author | Arhire, Andrei Chiriac, Matei Timofte, Radu |
| author_facet | Arhire, Andrei Chiriac, Matei Timofte, Radu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06486 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm Arhire, Andrei Chiriac, Matei Timofte, Radu Data Structures and Algorithms Discrete Mathematics 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. |
| title | UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2511.06486 |