Show simple item record

dc.contributor.authorChaplick, Steven
dc.contributor.authorGolovach, Petr
dc.contributor.authorHartmann, Tim
dc.contributor.authorKnop, Dusan
dc.PublishedLeibniz International Proceedings in Informatics. 2020, 180 8:1-8:15.
dc.description.abstractWe investigate the parameterized complexity of the recognition problem for the proper H-graphs. The H-graphs are the intersection graphs of connected subgraphs of a subdivision of a multigraph H, and the properness means that the containment relationship between the representations of the vertices is forbidden. The class of H-graphs was introduced as a natural (parameterized) generalization of interval and circular-arc graphs by Biró, Hujter, and Tuza in 1992, and the proper H-graphs were introduced by Chaplick et al. in WADS 2019 as a generalization of proper interval and circular-arc graphs. For these graph classes, H may be seen as a structural parameter reflecting the distance of a graph to a (proper) interval graph, and as such gained attention as a structural parameter in the design of efficient algorithms. We show the following results. - For a tree T with t nodes, it can be decided in 2^{𝒪(t² log t)} ⋅ n³ time, whether an n-vertex graph G is a proper T-graph. For yes-instances, our algorithm outputs a proper T-representation. This proves that the recognition problem for proper H-graphs, where H required to be a tree, is fixed-parameter tractable when parameterized by the size of T. Previously only NP-completeness was known. - Contrasting to the first result, we prove that if H is not constrained to be a tree, then the recognition problem becomes much harder. Namely, we show that there is a multigraph H with 4 vertices and 5 edges such that it is NP-complete to decide whether G is a proper H-graph.en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleRecognizing Proper Tree-Graphsen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2020 The Authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2020, 180, 8:1-8:15en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal