Recognition and Isomorphism of Proper $\mathbf{U}$-graphs in FPT-time

Abstract

An $H$-graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph $H$. Many important classes of graphs, including interval graphs, circular-arc graphs, and chordal graphs, can be expressed as $H$-graphs, and, in particular, every graph is an $H$-graph for a suitable graph $H$. An $H$-graph is called proper if it has a representation where no subgraph properly contains another. We consider the recognition and isomorphism problems for proper $U$-graphs where $U$ is a unicylic graph. We prove that testing whether a graph is a (proper) $U$-graph, for some $U$, is NP-hard. On the positive side, we give an FPT-time recognition algorithm, parametrized by $|U|$. As an application, we obtain an FPT-time isomorphism algorithm for proper $U$-graphs, parametrized by $|U|$. To complement this, we prove that the isomorphism problem for (proper) $H$-graphs, is as hard as the general isomorphism problem for every fixed $H$ which is not unicyclic.