Recognition and Isomorphism of Proper H-Graphs for Unicyclic H
in FPT-Time

D 2024

Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time

AGAOGLU CAGIRICI, Deniz a Peter ZEMAN

Základní údaje

Originální název

Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time

Autoři

AGAOGLU CAGIRICI, Deniz a Peter ZEMAN

Vydání

Kanazawa, Japan, 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, od s. 304-318, 15 s. 2024

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Singapur

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/24:00139777

Organizační jednotka

Fakulta informatiky

ISBN

978-981-97-0565-8

ISSN

DOI

https://doi.org/10.1007/978-981-97-0566-5_22

UT WoS

001207267500022

EID Scopus

2-s2.0-85187789019

Klíčová slova anglicky

H-graph; recognition; isomorphism; FPT-time

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 3. 4. 2025 22:46, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

An H-graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H. Many important classes of graphs can be expressed as H-graphs, and in particular, every graph is an H-graph for a suitable graph H. An H-graph is called proper if it has a representation where no subgraph properly contains another. We consider the recognition and isomorphism problems for proper U-graphs where U is a unicyclic graph, i.e. a graph which contains exactly one cycle. We prove that testing whether a graph is a (proper) U-graph, for some U, is NP-hard. On the positive side, we give an FPT-time recognition algorithm for a fixed U, parameterized by |U|. As an application, we obtain an FPT-time isomorphism algorithm for proper U-graphs, parameterized by |U|. To complement this, we prove that the isomorphism problem for (proper) H-graphs is GI-complete for every fixed H which is not unicyclic nor a tree.

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

Citovat

AGAOGLU CAGIRICI, Deniz a Peter ZEMAN. Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time. In 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024. Kanazawa, Japan: Springer, 2024, s. 304-318. ISBN 978-981-97-0565-8. Dostupné z: https://doi.org/10.1007/978-981-97-0566-5_22.

@inproceedings{2488803,
   author = {Agaoglu Cagirici, Deniz and Zeman, Peter},
   address = {Kanazawa, Japan},
   booktitle = {18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024},
   doi = {https://doi.org/10.1007/978-981-97-0566-5_22},
   keywords = {H-graph; recognition; isomorphism; FPT-time},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Kanazawa, Japan},
   isbn = {978-981-97-0565-8},
   pages = {304-318},
   publisher = {Springer},
   title = {Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time},
   year = {2024}
}

TY  - CONF
ID  - 2488803
AU  - Agaoglu Cagirici, Deniz - Zeman, Peter
PY  - 2024
TI  - Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time
PB  - Springer
CY  - Kanazawa, Japan
SN  - 9789819705658
KW  - H-graph
KW  - recognition
KW  - isomorphism
KW  - FPT-time
N2  - An H-graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H. Many important classes of graphs can be expressed as H-graphs, and in particular, every graph is an H-graph for a suitable graph H. An H-graph is called proper if it has a representation where no subgraph properly contains another. We consider the recognition and isomorphism problems for proper U-graphs where U is a unicyclic graph, i.e. a graph which contains exactly one cycle. We prove that testing whether a graph is a (proper) U-graph, for some U, is NP-hard. On the positive side, we give an FPT-time recognition algorithm for a fixed U, parameterized by |U|. As an application, we obtain an FPT-time isomorphism algorithm for proper U-graphs, parameterized by |U|. To complement this, we prove that the isomorphism problem for (proper) H-graphs is GI-complete for every fixed H which is not unicyclic nor a tree.
ER  -

AGAOGLU CAGIRICI, Deniz a Peter ZEMAN. Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time. In \textit{18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024}. Kanazawa, Japan: Springer, 2024, s.~304-318. ISBN~978-981-97-0565-8. Dostupné z: https://doi.org/10.1007/978-981-97-0566-5\_{}22.

Přehled o publikaci