论文标题
在VPG图上近似独立集和主导集
Approximating Independent Set and Dominating Set on VPG graphs
论文作者
论文摘要
我们考虑限于VPG图的独立集和主导集合（或等效地为字符串图）。我们表明，它们都保留$ \ Mathsf {np} $ - 在$ b_0 $ -vpg上硬示意表示表示形式，因此每个网格边缘最多属于一个路径，并且每个水平路径最多都有两个。另一方面，将著名的面包师的转换技术与有界的Mim宽度论点相结合，我们在VPG图上提供简单的Ptases，以承认表示每个网格边缘最多属于$ t $路径，并且每个路径的水平部分最多属于$ c $，对于一些$ c $，对于一些$ C \ geq feq feq feq \ geq 1 $。
We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain $\mathsf{NP}$-hard on $B_0$-VPG graphs admitting a representation such that each grid-edge belongs to at most one path and each horizontal path has length at most two. On the other hand, combining the well-known Baker's shifting technique with bounded mim-width arguments, we provide simple PTASes on VPG graphs admitting a representation such that each grid-edge belongs to at most $t$ paths and the length of the horizontal part of each path is at most $c$, for some $c \geq 1$.
