Isomorphism Testing for T-graphs in FPT

AGAOGLU CAGIRICI, Deniz a 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, s. 239-250. ISBN 978-3-030-96730-7. Dostupné z: https://dx.doi.org/10.1007/978-3-030-96731-4_20.

Základní údaje

• Originální název: Isomorphism Testing for T-graphs in FPT
• Autoři: AGAOGLU CAGIRICI, Deniz (792 Turecko, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí).
• Vydání: LNCS 13174. Cham, WALCOM: Algorithms and Computation, od s. 239-250, 12 s. 2022.
• Nakladatel: Springer, Cham

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10200 1.2 Computer and information sciences
• Stát vydavatele: Švýcarsko
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: tištěná verze "print"
• Impakt faktor: Impact factor: 0.402 v roce 2005
• Kód RIV: RIV/00216224:14330/22:00125687
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-3-030-96730-7
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-030-96731-4_20
• Klíčová slova anglicky: chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity
• Štítky: firank_B, formela-conference
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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].

Návaznosti

• GA20-04567S, projekt VaV: Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs

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

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.