Canonizing Graphs of Bounded Tree Width in Logspace (2017)
Link: https://dl.acm.org/doi/abs/10.1145/3132720
Abstract: Graph canonization is the problem of computing a unique representative, a canon, from the isomorphism class of a given graph. This implies that two graphs are isomorphic exactly if their canons are equal. We show that graphs of bounded tree width can be canonized by logarithmic-space (logspace) algorithms. This implies that the isomorphism problem for graphs of bounded tree width can be decided in logspace. In the light of isomorphism for trees being hard for the complexity class logspace, this makes the ubiquitous class of graphs of bounded tree width one of the few classes of graphs for which the complexity of the isomorphism problem has been exactly determined.
Some useful quotes:
The graph isomorphism problem (isomorphism)—deciding whether two given graphs are the same up to renaming vertices—is one of the few fundamental problems in NP for which we neither know that it is polynomial-time solvable nor that it is NP-complete.
Logspace algorithms are known for small constant bounds on the tree width. Indeed, Lindell’s classical approach to testing isomorphism of trees (Lindell 1992) provides us with a logspace algorithm for graphs of tree-width at most 1. This was generalized to graphs of tree width at most 2 (Arvind et al. 2008).
The known logspace approaches for canonizing certain classes of bounded tree width graphs are based on first computing an isomorphism-invariant tree decomposition for the given input graph and then adjusting Lindell’s tree canonization approach to canonize the graph with respect to the decomposition. For example, for k-trees (Arvind et al. 2012) an isomorphism-invariant tree decomposition arises by taking a graph’s maximal cliques and their intersections as the bags of the decomposition and connecting two bags based on inclusion. The resulting tree decomposition is both isomorphism-invariant, which is required for a canonization procedure to be correct, and has width k, which enables the application of an extension of Lindell’s approach by taking (the constant number of) orderings of the vertices of the bags into account.
Ingredient 1: Isomorphism-invariant tree decomposition into bags without clique separators. In general, for graphs of tree width at most $k$, there is no isomorphism-invariant tree decomposition of width $k$. A simple example of graphs demonstrating this are cycles, which have tree width 2, but no isomorphism-invariant tree decomposition of width 2. We could hope to find an isomorphism-invariant tree decomposition by allowing approximate tree decompositions (that means, allowing an increase of the width to some constant $k′$). Again, cycles show that such tree decompositions do not always exist. To address this issue, we could consider not just one tree decomposition, but an isomorphism-invariant and polynomial-size collection of tree decompositions. However, for all $k′ \in N$, there are graphs of tree width at most 3 for which the smallest isomorphism-invariant collection of tree decompositions of width $k′$ has exponential size. Simple graphs demonstrating this fact are given by forming the disjoint union of $n$ cycles of length $n$, and adding a vertex that is adjacent to every other vertex.
We work around this problem by considering isomorphism-invariant tree decompositions that may have bags of unbounded size but with bags that are easier from a graph-theoretic and algo- rithmic perspective than the original graph.
Our first main technical contribution develops a tree decomposition of a graph whose bags are maximal atoms that is isomorphism-invariant and logspace-computable for graphs of bounded tree width.
Two graphs $G$ and $G′$ are isomorphic with respect to tree decompositions $D = (T, \mathcal{B})$ and $D′ = (T′, \mathcal{B}’)$, respectively, if there exists an isomorphism $\phi$ from $G$ to $G′$ and an isomorphism $\psi$ from $T$ to $T′$ satisfying $B′_{\psi(n)} = \{\phi(v) | v \in B_n\}$ for every node $n \in V(T)$. Under these conditions, we say that $\phi$ respects $D$ and $D′$. Based on this definition and the way of how it refines the isomorphism equivalence relation among graphs, we also consider canons of graphs with respect to tree decompositions.
We showed how to canonize and compute canonical labelings for graphs of bounded tree width in logspace, and this implies that deciding isomorphism graphs and computing isomorphisms can be done in logspace for graphs of bounded tree width. For the proof, we first developed a tree decomposition into clique-separator-free subgraphs that is isomorphism-invariant and logspace-computable. Then, we showed how to compute, for each bag, an isomorphism-invariant family of width-bounded tree decompositions in logspace. Finally, we combined both decomposition approaches to construct nested tree decompositions and developed a recursive canonization procedure that works on nested tree decompositions.