Approximating Independent Set and Dominating Set on VPG graphs
share
We consider Independent Set and Dominating Set restricted to VPG graphs (or, equivalently, string graphs). We show that they both remain 𝖭𝖯-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 ≥ 1.
READ FULL TEXT