# Domination and Independent Domination in Extended Supergrid Graphs +
## 3 NP-Completeness Results  
The domination and independent domination problems on grid graphs have been shown to be NP-complete [2]; thus, they are NP-complete for extended supergrid graphs as well, as extended supergrid graphs contain grid graphs as a subclass of graphs (see Figure 2). However, their complexities for diagonal supergrid, triangular supergrid, and supergrid graphs remain unknown. In [28], we have provided a _rough_ proof to claim that they are NP-complete for supergrid graphs. In this section, we present a complete proof to show that they are NP-complete for diagonal supergrid graphs. We then expand this to verify that they are NP-complete for supergrid and triangular supergrid graphs as well. To demonstrate this, we establish a polynomial-time reduction from the domination problem on grid graphs. In [2], [PERSON] et al. provided the following theorem:  
**Theorem 1** (see [2]). : _The domination problem on grid graphs is NP-complete._  
Figure 3: (**a**) A rectangular grid graph \(G_{8\times 9}\), (**b**) a rectangular supergrid graph \(R_{8\times 9}\), and (**c**) a rectangular triangular-supergrid graph \(T_{8\times 9}\), where the set of eight arrow lines in (**b**) indicates a horizontal path \(P_{9}\) and the bold dashed lines in (**c**) indicate vertical and horizontal separations on \(T_{8\times 9}\). We reduce the domination problem on grid graphs to the domination problem on diagonal supergrid graphs. Consider a grid graph \(G_{g}\); a diagonal supergrid graph \(G_{d}\) is constructed to satisfy that \(G_{g}\) has a dominating set \(D\) of size \(|D|\leqslant k\) if and only if \(G_{d}\) contains a dominating set \(D^{\prime}\) of size \(|D^{\prime}|\leqslant k+2|E(G_{g})|\). The steps for constructing the diagonal supergrid graph \(G_{d}\) from the grid graph \(G_{g}\) are as follows. First, the input grid graph \(G_{g}\) is enlarged to transform each edge of \(G_{g}\) into a vertical or horizontal path with seven edges, that is, each edge of \(G_{g}\) is enlarged by a factor of seven. The enlarged grid graph is represented as \(G_{g}^{\prime}\). For example, Figure 3(b) shows the grid graph \(G_{g}^{\prime}\) enlarged from \(G_{g}\) in Figure 3(a). The second step is to replace each \((u,v)\)-path of the graph \(G_{g}^{\prime}\) with a special diagonal supergrid graph, where \(u,v\in V(G_{g})\). This special diagonal supergrid is a \((u,v)\)-path with seven edges, and contains at least one \(l\)-skewed and one \(r\)-skewed edges; we call it _snake \((u,v)\)-path_ and denote it as \(S(u,v)\). For a snake \((u,v)\)-path \(S(u,v)\), \(u\) and \(v\) are said to be the _connectors_ of \(S(u,v)\). Figure 3(c) shows a snake \((u,v)\)-path. Then, the constructed graph is a diagonal supergrid graph \(G_{d}\). For example, Figure 3(d) depicts a diagonal supergrid graph \(G_{d}\) constructed from the grid graph \(G_{g}\) in Figure 3(a). Next, we propose a method for placing snake paths on the enlarged grid graph \(G_{g}^{\prime}\) such that any two snake paths are vertex-disjoint except for their connectors. Consider a square of a grid graph \(G_{g}\) with vertices \((i,j)\), \((i,j+1)\), \((i+1,j)\), \((i+1,j+1)\). Then, these four vertices are the connectors of the corresponding snake paths. If \(i,j\) are both odd or even, we place the four snake paths as shown in Figure 4(a); otherwise, we place these snake paths as shown in Figure 4(b). Then, in a corresponding square of an enlarged grid \(G_{g}^{\prime}\), at most two snake paths are placed inside it and opposite each other. In addition, the two snake paths inside the corresponding square are separated by at least two integer points.