Isomorphism Testing for T-graphs in FPT

AGAOGLU CAGIRICI, Deniz and Petr HLINĚNÝ. Isomorphism Testing for T-graphs in FPT. In Mutzel, P., Rahman, M.S., Slamin. WALCOM: Algorithms and Computation. LNCS 13174. Cham: Springer, Cham, 2022, p. 239-250. ISBN 978-3-030-96730-7. Available from: https://dx.doi.org/10.1007/978-3-030-96731-4_20.

Basic information

• Original name: Isomorphism Testing for T-graphs in FPT
• Authors: AGAOGLU CAGIRICI, Deniz (792 Turkey, belonging to the institution) and Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution).
• Edition: LNCS 13174. Cham, WALCOM: Algorithms and Computation, p. 239-250, 12 pp. 2022.
• Publisher: Springer, Cham

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10200 1.2 Computer and information sciences
• Country of publisher: Switzerland
• Confidentiality degree: is not subject to a state or trade secret
• Publication form: printed version "print"
• Impact factor: Impact factor: 0.402 in 2005
• RIV identification code: RIV/00216224:14330/22:00125687
• Organization unit: Faculty of Informatics
• ISBN: 978-3-030-96730-7
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-030-96731-4_20
• Keywords in English: chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity
• Tags: firank_B, formela-conference
• Tags: International impact, Reviewed

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 isomorphisminvariant decomposition of T-graphs with the classical tower-of-groups algorithm of Babai, and reuse some of the ideas of our isomorphism algorithm for Sd-graphs [MFCS 2020].

Links

• GA20-04567S, research and development project: Name: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Czech Science Foundation

• MUNI/A/1145/2021, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Acronym: SV-FI MAV XI.)

Investor: Masaryk University