Approximating Independent Set and Dominating Set on VPG graphs

April 16, 2020 Β· Declared Dead Β· πŸ› arXiv.org

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Esther Galby, Andrea Munaro arXiv ID 2004.07566 Category cs.DS: Data Structures & Algorithms Cross-listed cs.CG, cs.DM Citations 2 Venue arXiv.org Last Checked 4 months ago
Abstract
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$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted