Recognition and Isomorphism of Proper U-graphs in FPT-time
share
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.
READ FULL TEXT
