Isomorphism Testing for T-graphs in FPT

D 2022

Isomorphism Testing for T-graphs in FPT

AGAOGLU CAGIRICI, Deniz and Petr HLINĚNÝ

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

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

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

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

Abstract

V originále

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

Citovat

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.

@inproceedings{1848138,
   author = {Agaoglu Cagirici, Deniz and Hliněný, Petr},
   address = {Cham},
   booktitle = {WALCOM: Algorithms and Computation},
   doi = {http://dx.doi.org/10.1007/978-3-030-96731-4_20},
   edition = {LNCS 13174},
   editor = {Mutzel, P., Rahman, M.S., Slamin},
   keywords = {chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-030-96730-7},
   pages = {239-250},
   publisher = {Springer, Cham},
   title = {Isomorphism Testing for T-graphs in FPT},
   year = {2022}
}

TY  - JOUR
ID  - 1848138
AU  - Agaoglu Cagirici, Deniz - Hliněný, Petr
PY  - 2022
TI  - Isomorphism Testing for T-graphs in FPT
PB  - Springer, Cham
CY  - Cham
SN  - 9783030967307
KW  - chordal graph · H-graph · leafage · graph isomorphism · parameterized complexity
N2  - 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].
ER  -

AGAOGLU CAGIRICI, Deniz and Petr HLINĚNÝ. Isomorphism Testing for T-graphs in FPT. In Mutzel, P., Rahman, M.S., Slamin. \textit{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.

Detailed Information on Publication Record