Abstract
Twin-width is a graph parameter that is central to explaining the fixed-parameter tractability of first-order model checking across various graph classes. Despite its significance, computing twin-width is challenging: recognizing graphs with twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known.
A recent approach focuses on developing fixed-parameter algorithms for computing or approximating twin-width under different parameterizations. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically.
As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.
Blogger's Review: The difficulty of computing twin-width has long been a significant challenge in graph theory. This research introduces new approaches by leveraging treedepth and vertex integrity, showcasing how to overcome the limitations of traditional parameterized algorithms. Such advancements not only aid theoretical studies but may also provide new solutions for practical graph processing applications.