Logic engines and product graphs

The graph product structure theorem of Dujmović et al.¹ states that every planar graph can be represented as a subgraph of a special kind of graph product: the strong product of a path graph and a graph of bounded treewidth. Like other graph products, the strong product \(G\boxtimes H\) of two graphs \(G\) and \(H\) has a vertex for each pair of a vertex in \(G\) and a vertex in \(H\). You can move in the strong product by moving along an edge in one of the factors and staying put in the other (like the Cartesian product) but also by moving along an edge in each factor (like the tensor product). So, for instance, the graph of king moves on a chessboard is a strong product of two paths, one representing the sequence of rows along which the king can move and the other representing the sequence of columns.

In terminology later introduced by Bose et al.,² the graph product structure theorem states that planar graphs have “bounded row treewidth”. Here, having row treewidth \(w\) is the same as being a subgraph of a strong product of a path with a graph of treewidth \(w\). You can define the same sort of concept “row X-width” for any other graph width parameter, meaning the same thing: having row X-width \(w\) means being a subgraph of a strong product of a graph of X-width \(w\). Since the announcement of the graph product structure theorem, this area has quickly expanded in interest, with many papers studying the relations between these row parameters, the decompositions of beyond-planar graphs, and other kinds of product decompositions.

However, there has not been as much work so far on the computational complexity of row treewidth and related parameters. Treewidth is NP-hard in general, but for any fixed \(k\), testing whether a graph has treewidth \(k\) takes only linear time.³ Can this sort of fixed-parameter tractable algorithm be found for row treewidth and other analogous parameters? The answer turns out to be no. My new preprint, “On the complexity of embedding in graph products”, with Therese Biedl and Torsten Ueckerdt (arXiv:2303.17028) provides NP-completeness proofs showing that even the smallest nontrivial parameter values are difficult to test, even on very simple graphs.

The starting point for several of our proofs is a result that has been known for much longer: it is hard to tell whether a given graph is a subgraph of the integer grid. It remains hard even when the given graph is a tree.⁴ The proof uses a technique later called the “logic engine”,⁵ in which one makes a graph with pieces that, in any grid embedding, must remain rigid, with flexible connections to the other pieces. The illustration below shows an example that could be used in a proof of the known result that embedding planar graphs as subgraphs of a grid is NP-complete. It is constructed from a not-all-equal satisfiability problem, whose variables are translated into the blue arms of the figure. Each arm can flip vertically, across the central horizontal spine, giving its variable two states, true or false. The green flags, each suspended from a vertical path attached to an arm, can flip to the left or to the right. Each row of flags is confined by the surrounding yellow frame, in such a way that the flags can only fit into their row if at least one arm is missing a flag on that row. When a variable belongs to a clause, its flag is removed from the clause’s row of the construction, providing a gap that will allow all the flags to fit on that row.

Grids are Cartesian products of a path with a path, but the products involved in row treewidth and row pathwidth are a bit more complicated, both because they use the strong product in place of the Cartesian product, and because one of the factors is not a path. The simplest case for row treewidth is width one, embedding into a strong product of a path and a tree. Testing whether such an embedding exists is trivial for trees (just use the product of the tree itself with a one-vertex path). But as we prove, it is hard for the next simplest case, when the graph to be embedded has treewidth two. Our proof again uses the logic engine. However, compared to the figure above, more care is needed in the construction to ensure that parts of the logic engine cannot avoid bumping into each other by twisting in ways that would be impossible for Cartesian products but possible in strong products, or by escaping into another branch of the factor graph.

Testing whether the row pathwidth one turns out to be hard even for trees. Because the graphs of pathwidth one are just the caterpillars, this means testing whether the given tree can be embedded into a strong product of a path with a caterpillar. It would be possible to prove this again using the logic engine, but we don’t. Instead, we use the known result that it’s hard to embed trees into grids. We find a way to transform trees into larger trees so that grid embedding of the smaller tree becomes equivalent to path-caterpillar-product embedding of the expanded tree.

We also prove that row treedepth, defined in the same way, is hard, even to test whether a tree has row treedepth one. This is the same as asking whether the given tree can be represented as a subgraph of a product of a path with a star. For this problem, the logic engine doesn’t work. Path-star products are too narrow for its components to fit into them. Instead, we use a different hardness reduction based on bin packing.

Even accurately approximating the row treewidth is hard, at least if you believe that approximating treewidth itself is hard. The hardness of approximation of treewidth has not been proven rigorously, but instead rests on an unproven assumption, the small set expansion hypothesis, a variant of the unique games conjecture. But if this assumption is true, then it is impossible to approximate treewidth to within any constant factor. If you add a universal vertex to a graph, you don’t change its treewidth much, but you force its row treewidth to be within a constant factor of its treewidth, because it prevents you from using path factors that are longer than two edges. So, under this assumption, it is also impossible to approximate row treewidth to within any constant factor.

(Discuss on Mastodon)