Grid recognition: Classical and parameterized computational perspectives
Grid recognition: Classical and parameterized computational perspectives
复制标题
网格识别：经典和参数化计算视角
DOI：
10.1016/j.jcss.2023.02.008
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Gupta S
中科院分区：
文献类型：
--
作者：
Gupta S
在过去的几十年里，大量的作品研究了网格图上的各种计算问题的（不）易处理性，这些问题通常产生比一般图快得多的算法。不幸的是，网格图的识别是困难的-它在1987年已经被证明是NP困难的。在本文中，我们提供了一些积极的结果在这方面的参数化复杂性的框架。具体而言，我们的贡献是三方面的。首先，我们证明了问题是由k+ mcc参数化的FPT，其中mcc是G的连通分支的最大尺寸。其次，我们提出了一个新的参数化，表示为G，关系图的距离几何距离。我们证明了该问题是由一个G参数化的para-NP-hard问题，但在树上是由一个G参数化的FPT问题，以及由k+一个G参数化的FPT问题。第三，我们证明了在路径宽度为2的图上识别k× r格图是NP-困难的，其中k= 3。
Over the past few decades, a large body of works studied the (in) tractability of various computational problems on grid graphs, which often yield substantially faster algorithms than general graphs. Unfortunately, the recognition of a grid graph is hard—it was shown to be NP-hard already in 1987. In this paper, we provide several positive results in this regard in the framework of parameterized complexity. Specifically, our contribution is threefold. First, we show that the problem is FPT parameterized by k+ mcc where mcc is the maximum size of a connected component of G. Second, we present a new parameterization, denoted a G, relating graph distance to geometric distance. We show that the problem is para-NP-hard parameterized by a G, but FPT parameterized by a G on trees, as well as FPT parameterized by k+ a G. Third, we show that the recognition of k× r grid graphs is NP-hard on graphs of pathwidth 2 where k= 3.