Recognizing Proper Tree-Graphs

DOI10.4230/LIPICS.IPEC.2020.8arXiv2011.11670OpenAlexW3115462601MaRDI QIDQ6089652FDOQ6089652

Dušan Knop, Petr A. Golovach, Steven Chaplick, Tim A. Hartmann

Publication date: 13 November 2023

Abstract: We 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'o, 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^{mathcalO(t^{2}logt)}cdot{n}^3$ 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.

Full work available at URL: https://arxiv.org/abs/2011.11670

zbMATH Keywords

intersection graphsfixed-parameter tractabilityrecognition\(H\)-graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Graph Classes: A Survey
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Representations of chordal graphs as subtrees of a tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• The leafage of a chordal graph
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Precoloring extension. I: Interval graphs
• A characterisation of rigid circuit graphs
• Topology of Thin Film RC Circuits
• Extending partial representations of subclasses of chordal graphs
• Mim-width. II. The feedback vertex set problem
• Chordal graphs and their clique graphs
• Combinatorial problems on \(H\)-graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• On the tractability of optimization problems on \(H\)-graphs
• On \(H\)-topological intersection graphs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs

Cited In (3)

• Recognition and isomorphism of proper \(H \)-graphs for unicyclic \(H\) in \textit{FPT}-time
• Recognizing Greedy Structures
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs

This page was built for publication: Recognizing Proper Tree-Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089652)