Isomorphism Testing for T-graphs in FPT

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

AGAOGLU CAGIRICI Deniz HLINĚNÝ Petr

Rok publikování 2022
Druh Článek ve sborníku
Konference WALCOM: Algorithms and Computation
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-030-96731-4_20
Klíčová slova chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity
Popis 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].
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.