Efficient Isomorphism for Sd-Graphs and T-Graphs

J 2023

Efficient Isomorphism for Sd-Graphs and T-Graphs

AGAOGLU CAGIRICI, Deniz a Petr HLINĚNÝ

Základní údaje

Originální název

Efficient Isomorphism for Sd-Graphs and T-Graphs

Autoři

AGAOGLU CAGIRICI, Deniz (792 Turecko, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)

Vydání

ALGORITHMICA, UNITED STATES, SPRINGER, 2023, 0178-4617

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

full preprint URL

Impakt faktor

Impact factor: 1.100 v roce 2022

Kód RIV

RIV/00216224:14330/23:00130021

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1007/s00453-022-01033-8

UT WoS

000850021200002

Klíčová slova anglicky

intersection graph; isomorphism testing; chordal graph; H-graph; parameterized complexity

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 6. 2023 13:42, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for Sd-graphs and T-graphs, where Sd is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of Sd-graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of Sd-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper Sd- and T-graphs.

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/1081/2022, interní kód MU

Název: Modelování, analýza a verifikace (2023)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)

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.

Citovat

AGAOGLU CAGIRICI, Deniz a Petr HLINĚNÝ. Efficient Isomorphism for Sd-Graphs and T-Graphs. ALGORITHMICA. UNITED STATES: SPRINGER, 2023, roč. 85, č. 2, s. 352-383. ISSN 0178-4617. Dostupné z: https://dx.doi.org/10.1007/s00453-022-01033-8.

@article{2218880,
   author = {Agaoglu Cagirici, Deniz and Hliněný, Petr},
   article_location = {UNITED STATES},
   article_number = {2},
   doi = {http://dx.doi.org/10.1007/s00453-022-01033-8},
   keywords = {intersection graph; isomorphism testing; chordal graph; H-graph; parameterized complexity},
   language = {eng},
   issn = {0178-4617},
   journal = {ALGORITHMICA},
   title = {Efficient Isomorphism for Sd-Graphs and T-Graphs},
   url = {http://arxiv.org/abs/1907.01495},
   volume = {85},
   year = {2023}
}

TY  - JOUR
ID  - 2218880
AU  - Agaoglu Cagirici, Deniz - Hliněný, Petr
PY  - 2023
TI  - Efficient Isomorphism for Sd-Graphs and T-Graphs
JF  - ALGORITHMICA
VL  - 85
IS  - 2
SP  - 352-383
EP  - 352-383
PB  - SPRINGER
SN  - 01784617
KW  - intersection graph
KW  - isomorphism testing
KW  - chordal graph
KW  - H-graph
KW  - parameterized complexity
UR  - http://arxiv.org/abs/1907.01495
N2  - An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for Sd-graphs and T-graphs, where Sd is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of Sd-graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of Sd-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper Sd- and T-graphs.
ER  -

AGAOGLU CAGIRICI, Deniz a Petr HLINĚNÝ. Efficient Isomorphism for Sd-Graphs and T-Graphs. \textit{ALGORITHMICA}. UNITED STATES: SPRINGER, 2023, roč.~85, č.~2, s.~352-383. ISSN~0178-4617. Dostupné z: https://dx.doi.org/10.1007/s00453-022-01033-8.

Podrobný výpis o publikaci