The Hardness of Embedding Grids and Walls
The Hardness of Embedding Grids and Walls
复制标题
DOI：
10.1007/978-3-319-68705-6_14
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Yijia Chen;Martin Grohe;Bingkai Lin
中科院分区：
文献类型：
--
作者：
Yijia Chen;Martin Grohe;Bingkai Lin
参数嵌入问题的二分法猜想表明，如果一类有界树宽的图是一类有界树宽的图，则判定一类“模式图”中的一个图G是否可以嵌入到一个给定的图H(即同构于H的一个子图)中的问题是固定参数易处理的.利用这个猜想，我们证明了嵌入问题是-完备的，如果它是所有网格的类，或者是所有墙的类.
The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graphGfrom some classof “pattern graphs” can be embedded into a given graphH(that is, is isomorphic to a subgraph ofH) is fixed-parameter tractable ifis a class of graphs of bounded tree width and-complete otherwise.Towards this conjecture, we prove that the embedding problem is-complete ifis the class of all grids or the class of all walls.