Approximating Independent Set and Dominating Set on VPG graphs

to-one correspondence with its vertex set such that two vertices are adjacent
if and only if the corresponding paths intersect on at least one grid-point. We
consider Independent Set and Dominating Set restricted to VPG graphs.
We show that they both remain NP-hard when restricted to VPG graphs admit-
ting a representation where each path is either a horizontal or vertical segment,
each grid-edge belongs to at most one path and each horizontal path has length
at most two. On the other hand, by combining the well-known Baker’s shifting
technique with bounded mim-width arguments, we provide simple PTASes for
both problems on VPG graphs admitting a representation where 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.

---------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.