| Title | : | A Hierarchy of Tinhofer Graphs: Separations and Membership Testing |
| Speaker | : | Sutanay Bhattacharjee (IITM) |
| Details | : | Thu, 21 Aug, 2025 3:30 PM @ SSB 334 |
| Abstract: | : | Color refinement is an important technique which works very well in practice for graph isomorphism. It involves iteratively partitioning (coloring) vertices of a given graph until it stabilizes and using the resulting partition to test isomorphism of graphs. To address the issue that this process may stabilize before discovering the non-isomorphism between two graphs, the idea of individualization was introduced. Tinhofer graphs are a class of graphs where the refinement and individualization works correctly in terms of testing isomorphism of graphs (with respect to any other graph) (Tinhofer (1991). We introduce a hierarchy of graph classes within the class of Tinhofer graphs, which we call the k-Tinhofer graphs - for any 1 le k le n, the graph G is called a k-Tinhofer graph if for any H cong G, after k steps of individualization and refinement, G cong H, irrespective of the vertices chosen for individualization. Inspired by the work of Arvind et. al. (2017), we prove a characterization of k-Tinhofer graphs. We show that our hierarchy is strict at each level. Next, we show the problem of given a k-Tinhofer graph, testing whether it is (k+1)-Tinhofer or not, is P-hard under AC^{0} many-one reductions. We also show, the problem of testing isomorphism between a given $(n-k)$-Tinhofer graph $G$ and a graph $H$ is fixed-parameter tractable with respect to the parameter $k$, which we call the Tinhofer deficiency, where $1 le k le (n-1)$. Our techniques involve combining the techniques in Arvind et. al. (2017) along with properties of the CFI gadgets studied in Cai et. al. (1992) in the context of $WL$-dimension of graphs. |
