License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.8
URN: urn:nbn:de:0030-drops-185420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18542/
Ağaoğlu Çağırıcı, Deniz ;
Çağırıcı, Onur ;
Derbisz, Jan ;
Hartmann, Tim A. ;
Hliněný, Petr ;
Kratochvíl, Jan ;
Krawczyk, Tomasz ;
Zeman, Peter
Recognizing H-Graphs - Beyond Circular-Arc Graphs
Abstract
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected graph H, the class of H-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of H. Such classes of graphs are related to many known graph classes: for example, K₂-graphs coincide with interval graphs, K₃-graphs with circular-arc graphs, the union of T-graphs, where T ranges over all trees, coincides with chordal graphs. Recently, quite a lot of research has been devoted to understanding the tractability border for various computational problems, such as recognition or isomorphism testing, in classes of H-graphs for different graphs H.
In this work we undertake this research topic, focusing on the recognition problem. Chaplick, Töpfer, Voborník, and Zeman showed an XP-algorithm testing whether a given graph is a T-graph, where the parameter is the size of the tree T. In particular, for every fixed tree T the recognition of T-graphs can be solved in polynomial time. Tucker showed a polynomial time algorithm recognizing K₃-graphs (circular-arc graphs). On the other hand, Chaplick et al. showed also that for every fixed graph H containing two distinct cycles sharing an edge, the recognition of H-graphs is NP-hard.
The main two results of this work narrow the gap between the NP-hard and ? cases of H-graph recognition. First, we show that the recognition of H-graphs is NP-hard when H contains two distinct cycles. On the other hand, we show a polynomial-time algorithm recognizing L-graphs, where L is a graph containing a cycle and an edge attached to it (which we call lollipop graphs). Our work leaves open the recognition problems of M-graphs for every unicyclic graph M different from a cycle and a lollipop.
BibTeX - Entry
@InProceedings{agaoglucagirici_et_al:LIPIcs.MFCS.2023.8,
author = {A\u{g}ao\u{g}lu \c{C}a\u{g}{\i}r{\i}c{\i}, Deniz and \c{C}a\u{g}{\i}r{\i}c{\i}, Onur and Derbisz, Jan and Hartmann, Tim A. and Hlin\v{e}n\'{y}, Petr and Kratochv{\'\i}l, Jan and Krawczyk, Tomasz and Zeman, Peter},
title = {{Recognizing H-Graphs - Beyond Circular-Arc Graphs}},
booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
pages = {8:1--8:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-292-1},
ISSN = {1868-8969},
year = {2023},
volume = {272},
editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18542},
URN = {urn:nbn:de:0030-drops-185420},
doi = {10.4230/LIPIcs.MFCS.2023.8},
annote = {Keywords: H-graphs, Intersection Graphs, Helly Property}
}
|
Keywords: |
|
H-graphs, Intersection Graphs, Helly Property |
|
Collection: |
|
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.08.2023 |
