Unbreakable Decomposition in Close-to-Linear Time

Unbreakable decomposition, introduced by [CLP + 19, CKL + 20], has proven to be one of the most powerful tools for parameterized graph cut problems in recent years. Unfortunately, all known constructions require at least Ω k mn 2 time, given an undirected graph with n vertices, m edges, and cut-size parameter k. In this work, we show the first close-to-linear time parameterized algorithm that computes an unbreakable decomposition. More precisely, for any 0 < ǫ ≤ 1, our algorithm runs in time 2 O( k ǫ log k ǫ ) m 1+ǫ and computes a (O(k/ǫ), k) unbreakable tree decomposition of G, where each bag has adhesion at most O(k/ǫ).

This immediately opens up possibilities for obtaining close-to-linear time algorithms for numerous problems whose only known solution is based on unbreakable decomposition.