论文标题
适当$ \ boldsymbol {u} $的识别和同构 - fpt time
Recognition and Isomorphism of Proper $\boldsymbol{U}$-graphs in FPT-time
论文作者
论文摘要
$ h $ -graph是固定图$ h $的合适细分连接子图的相交图。许多重要的图形类别，包括间隔图，圆形ARC图和和弦图，都可以表示为$ h $ graphs，尤其是，每个图都是合适的图形$ h $的$ h $ -graph。如果$ h $ graph的代表不正确包含另一个子图，则称为正确。我们考虑适当的$ u $ graphs的识别和同构问题，其中$ u $是一个独轮图。我们证明测试图形是否为（适当的）$ u $ graph，对于某些$ u $，是np-hard。在正面，我们给出了FPT时间识别算法，由$ \ vert u \ vert $进行参数。作为一个应用程序，我们获得了适用$ u $ graphs的FPT时间同构算法，由$ \ vert u \ vert $进行了参数。为了补充这一点，我们证明（适当的）$ h $ graphs的同构问题与每个固定的$ h $的一般同构问题一样困难，这不是独一的。
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 $\vert U \vert$. As an application, we obtain an FPT-time isomorphism algorithm for proper $U$-graphs, parametrized by $\vert U \vert$. 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.
