Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139777" target="_blank" >RIV/00216224:14330/24:00139777 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-981-97-0566-5_22" target="_blank" >http://dx.doi.org/10.1007/978-981-97-0566-5_22</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-981-97-0566-5_22" target="_blank" >10.1007/978-981-97-0566-5_22</a>
Alternative languages
Result language
angličtina
Original language name
Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA20-04567S" target="_blank" >GA20-04567S: Structure of tractable instances of hard algorithmic problems on graphs</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024
ISBN
9789819705658
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
15
Pages from-to
304-318
Publisher name
Springer
Place of publication
Kanazawa, Japan
Event location
Kanazawa, Japan
Event date
Jan 1, 2024
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
001207267500022