2016/08/08 by Chaplick, Steven, Töpfer, Martin, Voborník, Jan +1 · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1608.02389
Biró et al. (1992) introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a graph H. They are related to many classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs. We negatively answer the 25-year-old question of Biró et al. which asks if H-graphs can be recognized in polynomial time, for a fixed graph H. We prove that it is NP-complete if H contains the diamond graph as a minor. We provide a polynomial-time algorithm recognizing T-graphs, for each fixed tree T. When T is a star Sd of degree d, we have an O(n3.5)-time algorithm. We give FPT- and XP-time algorithms solving the minimum dominating set problem on Sd-graphs and H-graphs parametrized by d and the size of H, respectively. The algorithm for H-graphs adapts to an XP-time algorithm for the independent set and the independent dominating set problems on H-graphs. If H contains the double-triangle as a minor, we prove that H-graphs are GI-complete and that the clique problem is APX-hard. The clique problem can be solved in polynomial time if H is a cactus graph. When a graph G has a Helly H-representation, the clique problem can be solved in polynomial time. We show that both the k-clique and the list k-coloring problems are solvable in FPT-time on H-graphs (parameterized by k and the treewidth of H). In fact, these results apply to classes of graphs with treewidth bounded by a function of the clique number. We observe that H-graphs have at most nO(‖H‖) minimal separators which allows us to apply the meta-algorithmic framework of Fomin et al. (2015) to show that for each fixed t, finding a maximum induced subgraph of treewidth t can be done in polynomial time. When H is a cactus, we improve the bound to O(‖H‖n2).