Tree-clique products
A tree decomposition of a graph is, intuitively, a representation of the graph as a “thickened” tree. It comes from the use of separators in divide-and-conquer algorithms: if a graph can be separated into two smaller subgraphs by the removal of a separator, a small subset of its vertices, then many algorithmic problems can be solved by a recursive algorithm that combines the solutions from those subgraphs. The tree, in the tree decomposition, has a root node that represents the separator at the top level of the recursion, children that represent the separators at the next level, and so on.
It is tempting but incorrect to imagine that each vertex of the given graph belongs to only a single node of this tree. That would mean that you could “thicken” your tree merely by attaching disjoint sets of graph vertices to the tree nodes, so that each graph edge goes between two vertices at the same node or at adjacent nodes. If you could do this, it would give your graph a special kind of product structure: it would be a subgraph of a strong product of a tree and a complete graph, of size roughly equal to the width. You could recover the separators of the separator theorem as the subsets of vertices associated with a single tree node.
Unfortunately, this kind of tree-clique product structure doesn’t work, at least not with the usual separator theorems and the usual divide-and-conquer algorithms. Instead, each recursive subproblem needs to keep track of how its subgraph is attached to the higher-level separator vertices. That means that these separator vertices are really part of the subgraphs on both sides, rather than being confined to a single node at the root of the decomposition tree. Working out the implications of this leads to the standard notion of a tree decomposition, a tree with non-disjoint “bags” of vertices on each node. Each graph vertex may belong to many bags, but they must form a connected subtree of the whole tree. Each graph edge must have both endpoints together in at least one bag.
A counterexample for a related graph coloring problem, by Linial, Matoušek, Sheffet, and Tardos, “Graph colouring with no large monochromatic components”, Probability & Computing 2008, arXiv:math/0703362, also shows some of the limitations of the naive tree-clique-product idea. Their example uses a rectangular grid of dimensions \(n^{1/3}\times n^{2/3}\), with each vertex on the top row of the grid fanning out to another \(n^{1/3}\) vertices in a path of linearly many vertices, and one more vertex attached to everything in this path.
It’s planar, so it has a tree decomposition of width (bag size) \(O(\sqrt n)\), but representing it as the subgraph of a tree-clique product requires cliques of size \(\Omega(n^{2/3})\). If you try to use smaller cliques, then the tree node containing the high-degree vertex cannot include enough grid columns nor enough of the top grid row to separate the rest into pieces of small enough size. Some piece will contain \(\Omega(n^{2/3})\) vertices of the long path. However it is further subdivided, at least two of the subdivisions will be connected to each other through the piece and also through the high-degree vertex, forming a loop that is impossible in a tree. (Linial et al. triangulate the grid and show more strongly that in any product structure involving a small clique the other factor has a triangle, but that is more than we need here.)
This graph does have a tree-clique product structure with cliques of size \(O(n^{2/3})\). By applying the standard planar separator theorem repeatedly, in any planar graph you can find a separator of size \(O(n^{2/3})\) whose removal partitions the remaining subgraph into components of size \(O(n^{2/3})\). This can be thought of as a tree-clique product where the tree is a star with the separator as root and all the remaining components as leaf children. In the graph of Linial et al, the separator can be formed from the high-degree vertex, the entire top row of the grid, an evenly-spaced subset of vertices of the long path, and the left column of each square subset of the grid. The components it forms are the remainder of each square subset of the grid, and the remaining paths within the long path. More generally, in any class of graphs with \(O(\sqrt n)\)-separators, the same idea produces a representation as a subgraph of a clique–star product \(K_{O(n^{2/3})}\boxtimes K_{1,O(n^{1/3})}\), as David Wood observed in his recent preprint “Product structure of graph classes with strongly sublinear separators”, arXiv:2208.10074.
Which all brings us to my newest preprint, “Graphs excluding a fixed minor are \(O(\sqrt n)\)-complete-blowups of a treewidth 4 graph”, with Marc Distel, Vida Dujmović, Robert Hickingbotham, Gwenaël Joret, Pat Morin, Michał Seweryn, and David Wood, arXiv:2212.08739. It asks: what if you insist on a product structure involving cliques of size \(O(\sqrt n)\), but you let the other factor be something other than a tree? How well-structured can you make the other factor? As the title says, for graphs in any minor-closed graph family, we can find a representation of the graph as a strong product \(K\boxtimes G\) where \(K\) is a clique of size \(O(\sqrt n)\) and \(G\) has treewidth at most four. The details are messy and use the full strength of a different graph structure theorem, the theorem of Robertson and Seymour that the graphs in any minor-closed family can be decomposed by separators of bounded size into pieces that are graphs of bounded genus, plus a bounded number of arbitrary “apex” vertices, plus “vortices” of bounded pathwidth attached to a bounded number of faces. See the paper if you want an explanation of that part.