Recognition and Isomorphism of Proper H-Graphs for Unicyclic H in FPT-Time
| Authors | |
|---|---|
| Year of publication | 2024 |
| Type | Article in Proceedings |
| Conference | 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1007/978-981-97-0566-5_22 |
| Keywords | H-graph; recognition; isomorphism; FPT-time |
| Description | An H-graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H. Many important classes of 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 unicyclic graph, i.e. a graph which contains exactly one cycle. 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 for a fixed U, parameterized by |U|. As an application, we obtain an FPT-time isomorphism algorithm for proper U-graphs, parameterized by |U|. To complement this, we prove that the isomorphism problem for (proper) H-graphs is GI-complete for every fixed H which is not unicyclic nor a tree. |
| Related projects: |