An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
Éric Colin de Verdière and Thomas Magnard
我们考虑图 G 的可嵌入性问题,即将图形 G 嵌入到二维简单复合 C:给定 G 和 C,决定 G 是否承认拓扑嵌入 C。 问题是NP-hard,即使在C是顺态到表面的限制情况下。 我们通过提供 O(2^poly(c).n^2)-time 算法,在二维复合物的大小中证明问题是固定参数可处理的。 如果 G 嵌入到 C 中,我们可以在相同的时间内计算嵌入的表示。 此外,我们表明,几个已知的问题减少到这个,如交叉数和平面数问题,以及,在某些情况下,嵌入扩展问题。 我们的方法是减少G通过无关顶点方法限制分支宽的情况,并应用动态编程。 我们不依赖于现有线性时间算法的任何组件在固定表面上嵌入图形,而只依赖于图形小理论的算法。 然而,通过将我们的结果与用于在表面上嵌入图形的线性时间算法以及无关顶点方法的最近结果相结合,我们可以决定G是否在f(c).O(n)时间中嵌入到C中,对于某些函数f。
We consider the embeddability problem of a graph G into a two-dimensional simplicial complex C: Given G and C, decide whether G admits a topological embedding into C. The problem is NP-hard, even in the restricted case where C is homeomorphic to a surface. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing an O(2^poly(c).n^2)-time algorithm. If G embeds into C, we can compute a representation of an embedding in the same amount of time....