Recognizing H-Graphs - Beyond Circular-Arc Graphs

Deniz Agaoglu Çagirici, Onur Çagirici, Jan Derbisz, Tim A. Hartmann, Petr Hliněný, Jan Kratochvil, Tomasz Krawczyk, Peter Zeman

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

26 Downloads (Pure)

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, 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.
Original languageEnglish
Title of host publicationProceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Volume272
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2023
Pages8:1-8:14
ISBN (Print)978-3-95977-292-1
DOIs
Publication statusPublished - 2023
Event48th International Symposium on Mathematical Foundations of Computer Science - Bordeaux, France
Duration: 28 Aug 20231 Sept 2023

Conference

Conference48th International Symposium on Mathematical Foundations of Computer Science
Country/TerritoryFrance
CityBordeaux
Period28/08/202301/09/2023

Keywords

  • H-graphs
  • Intersection Graphs
  • Helly Property

Fingerprint

Dive into the research topics of 'Recognizing H-Graphs - Beyond Circular-Arc Graphs'. Together they form a unique fingerprint.

Cite this