Isomorphism Testing for T-graphs in FPT

2021/11/21 by Deniz Ağaoğlu Çağırıcı, Çağırıcı, Deniz Ağaoğlu, Petr Hliněný +1
Computer Science · #68R10 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2111.10910

openalex publication_date 2021/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A T-graph (a special case of a chordal graph) is the intersection graph of connected subtrees of a suitable subdivision of a fixed tree T . We deal with the isomorphism problem for T-graphs which is GI-complete in general - when T is a part of the input and even a star. We prove that the T-graph isomorphism problem is in FPT when T is the fixed parameter of the problem. This can equivalently be stated that isomorphism is in FPT for chordal graphs of (so-called) bounded leafage. While the recognition problem for T-graphs is not known to be in FPT wrt. T, we do not need a T-representation to be given (a promise is enough). To obtain the result, we combine a suitable isomorphism-invariant decomposition of T-graphs with the classical tower-of-groups algorithm of Babai, and reuse some of the ideas of our isomorphism algorithm for S_d-graphs [MFCS 2020].

Related

• Efficient Isomorphism for S_d-graphs and T-graphs
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• Recognition and Isomorphism of Proper \boldsymbolU-graphs in FPT-time
• A Generalisation of Isomorphisms with Applications
• Automorphisms of Set Families and of Families of Cliques in an Interval Graph in FPT Time