Recognizing -graphs – beyond circular-arc graphs

2023
book section
conference proceedings
 cris.lastimport.scopus 2024-04-07T17:16:32Z dc.abstract.en 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, $K2$-graphs coincide with interval graphs, $K3$-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 $K3$-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 P 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. pl dc.affiliation Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej pl dc.affiliation Szkoła Doktorska Nauk Ścisłych i Przyrodniczych pl dc.conference 48th International Symposium on Mathematical Foundations of Computer Science pl dc.conference.city Bordoux dc.conference.country Francja dc.conference.datefinish 2023-09-01 dc.conference.datestart 2023-08-28 dc.conference.shortcut MFCS dc.contributor.author Ağaoğlu Çağırıcı, Deniz pl dc.contributor.author Çağırıcı, Onur pl dc.contributor.author Derbisz, Jan - 244282 pl dc.contributor.author Hartmann, Tim A. pl dc.contributor.author Hliněný, Petr pl dc.contributor.author Kratochvíl, Jan pl dc.contributor.author Krawczyk, Tomasz - 129445 pl dc.contributor.author Zeman, Peter pl dc.contributor.editor Leroux, Jérôme pl dc.contributor.editor Lombardy, Sylvain pl dc.contributor.editor Peleg, David pl dc.date.accessioned 2023-08-31T08:25:40Z dc.date.available 2023-08-31T08:25:40Z dc.date.issued 2023 pl dc.date.openaccess 0 dc.description.accesstime w momencie opublikowania dc.description.conftype international pl dc.description.physical 8:1-8:14 pl dc.description.series Leibniz International Proceedings in Informatics (LIPIcs) dc.description.seriesnumber 272 dc.description.version ostateczna wersja wydawcy dc.identifier.doi 10.4230/LIPIcs.MFCS.2023.8 pl dc.identifier.isbn 978-3-95977-292-1 pl dc.identifier.seriesissn 1868-8969 dc.identifier.uri https://ruj.uj.edu.pl/xmlui/handle/item/318172 dc.language eng pl dc.language.container eng pl dc.pubinfo Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pl dc.rights Dozwolony użytek utworów chronionych * dc.rights.licence CC-BY dc.rights.uri http://ruj.uj.edu.pl/4dspace/License/copyright/licencja_copyright.pdf * dc.share.type inne dc.subject.en $H$-graphs pl dc.subject.en intersection graphs pl dc.subject.en helly property pl dc.subtype ConferenceProceedings pl dc.title Recognizing $H$-graphs – beyond circular-arc graphs pl dc.title.container 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) pl dc.type BookSection pl dspace.entity.type Publication
Affiliations

Open Access