## 3 PCC\({}^{2}\)LS for the Minimum Connected Dominating Set Problem
### Initial Solution Construction Procedure
#### 3.1.1 Simplification Rules  
In this subsection, we employ two operations--fixing and deletion--to simplify the original graph, thereby reducing the overall search space of the algorithm and obtaining a high-quality initial solution. The fixing and deletion operations we conduct ensure that certain vertices are guaranteed to be included in the optimal solution while also ensuring that certain other vertices will certainly not be part of the optimal solution. Next, I will introduce the three simplification rules in detail.  
**Degree-1 Simplification Rule 1:** If there exists a vertical vertex \(v\) in graph \(G\), i.e., \(d(v)=1\) with \(N(v)=[u]\), then vertex \(u\) is fixed in the solution, and vertex \(v\) is subsequently deleted to simplify the original graph.  
**Degree-2 Simplification Rule 2:** If graph \(G\) includes vertices \(v_{1}\), \(v_{2}\), and \(u\), such that \(N(v_{1})=\{v_{2},u\}\) and \(N(v_{2})=\{v_{1},u\}\), then vertex \(u\) is fixed in the current solution, and vertices \(v_{1}\) and \(v_{2}\) are subsequently deleted to simplify graph \(G\).  
**Degree-2 Simplification Rule 3:** If graph \(G\) contains vertices \(v_{1}\), \(v_{2}\), and \(u\), where \(N(v_{1})=\{v_{2},u\}\) and \(v_{2}\in N(u)\), then the original graph \(G\) is simplified by deleting vertex \(v_{1}\).  
To better understand these three simplification rules, we use Figure 1 as an aid. Our goal is to find a connected dominating set of small size, so we want to add as few vertices as possible to the candidate solutions. Observe the following: \(v_{1}\) and \(v_{8}\) have degree 1 (\(d(v_{1})=d(v_{8})=1\)), and their neighbors are \(N(v_{1})=\{v_{2}\}\) and \(N(v_{8})=\{v_{9}\}\), respectively. If \(v_{1}\) and \(v_{8}\) are added to the solution, \(v_{2}\) and \(v_{9}\) must also be added to the solution in order to ensure the connectivity of the solution. On the other hand, directly adding \(v_{2}\) and \(v_{9}\) to the solution can equally dominate \(v_{1}\) and \(v_{8}\). Based on this observation, we propose **Degree-1 Simplification Rule 1**: fixing \(v_{2}\) and \(v_{9}\) in the solution and deleting \(v_{1}\) and \(v_{8}\) from the original graph. Furthermore, we consider that \(v_{7}\) and \(v_{10}\) have degree 2 (\(d(v_{7})=d(v_{10})=2\)) and their neighbors \(N(v_{7})=\{v_{6},v_{10}\}\) and \(N(v_{10})=\{v_{6},v_{7}\}\). Whether we choose to add \(v_{7}\) or \(v_{10}\) to the solution, \(v_{6}\) must be added to the solution at the same time in order to ensure the connectivity of the solution, again because \(v_{6}\) can dominate \(v_{7}\) and \(v_{10}\). Therefore, we propose **Degree-2 Simplification Rule 2**: fix \(v_{6}\) in the solution and remove \(v_{7}\) and \(v_{10}\) from the original graph. Finally, we observe that the degrees of \(v_{3}\) and \(v_{5}\) are 2 (\(d(v_{3})=d(v_{5})=2\)), and their neighbors are \(N(v_{3})=\{v_{2},v_{4}\}\) and \(N(v_{5})=\{v_{4},v_{6}\}\), where \(v_{2}\) is a neighbor of \(v_{4}\) and \(v_{4}\) is a neighbor of \(v_{6}\). When adding \(v_{3}\) and \(v_{5}\) to the solution, their neighboring vertices must be considered in order to ensure the connectivity of the solution. Whether we choose to add \(v_{2}\) or \(v_{4}\) and \(v_{4}\) or \(v_{6}\), we are able to dominate \(v_{3}\) and \(v_{5}\). Therefore, we propose effectively dominated by their neighboring vertices. By applying these rules, we obtain the simplified graph on the right-hand side. Next, we will look for a smaller connected dominating set in this simplified graph.