The Strategic Objective

Deploy the minimal number of Sentinel Beacons to achieve 100% network coverage with zero interference between beacons.

1. Dominating Sets (Coverage)

In graph theory, a Dominating Set for a graph G = (V, E) is a subset of vertices D \subseteq V such that every vertex not in D is adjacent to at least one vertex in D. The smallest possible size of such a set is the domination number, denoted \gamma(G).

2. Independent Sets (Zero Interference)

An Independent Set requires that no two vertices in D share an edge. In SentinelLeft, adjacent beacons interfere with each other's radar frequencies. A set that is both dominating and independent is an Independent Dominating Set (or maximal independent set).

3. Fortified Sectors & Hashi Multi-Link Defense (k-Domination)

As missions advance, critical command sectors (marked with [2] and dual shield brackets) require more than one independent direct sentinel link (≥ 2) to be fully secured, synthesizing the classic Japanese puzzle Hashiwokakero (Hashi/Bridges) with k-Dominating Set Theory:

A fortified sector can be guarded either by placing a beacon directly on it (granting 1 defense point) plus 1 adjacent link, or by receiving 2 links from separate adjacent sentinels (which must never interfere with each other).

Computational Complexity

Finding the minimum dominating set is one of Richard Karp's classic NP-complete problems (1972). It has practical applications in sensor network coverage, facility location, and military defense perimeter optimization.