Here is a simple graph clustering problem. Given a graph \(G = (V,E,w)\) and a parameter \(\Delta > 0\), we want to partition the vertex set \(V\) into clusters such that (1) every cluster has a diameter at most \(\Delta\) and (2) the fraction of edges between clusters is at most \(\beta/\Delta\). Our goal is to minimize \(\beta\) (and thereby minimize the number of edges between clusters).
The problem above could be solved by padded decomposition. A \((\beta,\Delta)\)-padded decomposition of \(G = (V,E,w)\) is a stochastic decomposition of \(V\) into a set \(\mathcal{P}\), clusters of diameter at most \(\Delta\) such that for every \(v\in V\), the probability that the ball of radius \(\gamma\Delta\) from \(v\) is entirely contained in the cluster of \(v\), denoted by \(\mathcal{P(v)}\) is small. More precisely:
\[\mathrm{Pr}[B_G(v,\gamma \Delta)\subseteq \mathcal{P(v)}] \leq e^{-\beta\gamma} \quad \text{for every }\gamma\ll 1\]
In padded decomposition, our goal is to minimize \(\beta\), called the padding parameter. It is not hard to see that a \((\beta,\Delta)\)-padded decomposition gives a solution for the clustering problem with the same value \(\beta\). Furthermore, padded decomposition has applications to other problems, such as uniform sparsest cut, flow-cut gap, multicut, embedding into \(\ell_{\infty}\).
For general graph, Bartal construct a padded decomposition with \(\beta = O(\log n)\). The famous KPR theorem implies that \(\beta = O(r^3)\) for \(K_r\)-minor-free graphs. This result was then improved by a sequence of papers to \(\beta = O(r)\). (See here for a simple proof of the KPR theorem by James Lee.) A long-standing open problem is:
Open Problem: Can we construct a padded decomposition with a padding parameter \(\beta = O(\log r)\) in \(K_r\)-minor-fre graphs?
While the problem is very difficult, there are two important special cases that we could try to solve: (1) graphs embedded on a surface of genus \(g\) and (2) graphs of treewidth at most \(k\). Why these two special cases? Because they are building blocks of the Robertson-Seymour decomposition of \(K_r\)-minor-free graphs. (Though it does not seem that one could resolve the one problem above by using the Robertson-Seymour decomposition as the dependency on \(r\) in the decomposition is galactic.)
The special case (1), graphs with genus \(g\), was studied by several papers, achieving better and better bounds, from \(\beta = 2^{O(g)}\) to \(O(g^2)\) and finally \(O(\log g)\) by Sidiropoulos.
Our recent preprint solves the special case (2), graphs with treewidth \(k\), achieving \(\beta = O(\log k)\). Prior to our work, there was no progress on special case (2); the best known bound was \(\beta = O(k)\), which follows from the bound of \(K_r\)-minor-free graphs.
About the techniques. In a STOC 23 paper, a subset of us — Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif— designed a clever ball carving procedure to solve the multicut problem on graphs with treewidth \(k\). This paper shows that multiflow-multicut gap is \(O(\log k)\). We then realize that the technique of the STOC 23 paper could be interpreted as constructing a certain kind of net, called tree-ordered net.
A (classical) \(r\)-net is a subset \(N\) of vertices such that any two vertices in \(N\) has distance at least \(r\) (packing), while any vertex not in \(N\) has distance at most \(r\) from a vertex in \(N\) (covering). A tree-ordered net one could associate the vertex set \(V\) with a partial order represented by a tree \(T\) such that for two vertices \(x,y\) in \(V\), \(x\preceq y\) if \(x\) is a descendant of \(y\) in a tree \(T\). Loosely speaking, on a \((\tau,r)\)-tree-ordered net \(N\), the covering property is: every vertex \(v\) has an ancestor \(x\in N\) such that the distance to \(x\) is at most \(r\). The covering property is: for every \(v\), the number of ancestors at a distance \(O(r)\) is at most \(\tau\).
The technique of the STOC 23 paper could be used to construct a \((\tau,\Delta)\)-tree-ordered net with \(\tau = \mathrm{poly}(k)\) for graphs with treewidth \(k\). (Well, to be more precise, we are only able to construct the net for graphs with tree-partition width \(k\); there is a subtle difference between treewidth and tree-partition width, which readers should refer to the manuscript for details.)
We observe that if one can construct a \((\tau,\Delta)\)-tree-ordered net, then one can construct a \((\beta,\Delta)\)-padded decomposition with \(\beta = O(\log \tau)\). Combining this with the aforementioned tree-ordered net result, we obtain \(\beta = O(\log k)\).