Minimum k-Hop Dominating Sets in Grid Graphs.

Omrit Filtser; Erik Krohn; Bengt J. Nilsson; Christian Rieck; Christiane Schmidt

doi:10.48550/ARXIV.2308.00334

Minimum k-Hop Dominating Sets in Grid Graphs.

Omrit Filtser
, Erik Krohn
, Bengt J. Nilsson
, Christian Rieck
, Christiane Schmidt

מדעי המחשב

פרסום מחקרי: נייר עבודה / גרסה מוקדמת › גרסה מוקדמת

תקציר

We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k.
In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3×3 block of cells) for all k ∈ N.

שפה מקורית	אנגלית
מספר עמודים	17
כרך	abs/2308.00334
מזהי עצם דיגיטלי (DOIs)	https://doi.org/10.48550/ARXIV.2308.00334
סטטוס פרסום	פורסם - 2023

הערה ביבליוגרפית

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

גישה למסמך

10.48550/ARXIV.2308.00334

https://dblp.org/rec/journals/corr/abs-2308-00334

פורמט ציטוט ביבליוגרפי

@techreport{206efd5e477c44a48e7e26a688b10bfa,

title = "Minimum k-Hop Dominating Sets in Grid Graphs.",

abstract = "We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3×3 block of cells) for all k ∈ N.",

keywords = "Art Gallery problem, k-hop visibility, polyominoes, VC dimension, approximation, k-hop dominating set",

author = "Omrit Filtser and Erik Krohn and Nilsson, \{Bengt J.\} and Christian Rieck and Christiane Schmidt",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2023",

doi = "10.48550/ARXIV.2308.00334",

language = "אנגלית",

volume = "abs/2308.00334",

edition = "V2",

type = "WorkingPaper",

}

TY - UNPB

T1 - Minimum k-Hop Dominating Sets in Grid Graphs.

AU - Filtser, Omrit

AU - Krohn, Erik

AU - Nilsson, Bengt J.

AU - Rieck, Christian

AU - Schmidt, Christiane

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2023

Y1 - 2023

N2 - We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3×3 block of cells) for all k ∈ N.

AB - We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3×3 block of cells) for all k ∈ N.

KW - Art Gallery problem

KW - k-hop visibility

KW - polyominoes

KW - VC dimension

KW - approximation

KW - k-hop dominating set

U2 - 10.48550/ARXIV.2308.00334

DO - 10.48550/ARXIV.2308.00334

M3 - פרסום מוקדם

VL - abs/2308.00334

BT - Minimum k-Hop Dominating Sets in Grid Graphs.

ER -

Minimum k-Hop Dominating Sets in Grid Graphs.

תקציר

הערה ביבליוגרפית

גישה למסמך

טביעת אצבע

פורמט ציטוט ביבליוגרפי