## 3 PCC\({}^{2}\)LS for the Minimum Connected Dominating Set Problem
### The Local Search Procedure in PCC\({}^{2}\)Ls
#### 3.2.6 PCC\({}^{2}\)LS_Search Procedure  
After constructing the initial solution using the _InitConstructCDS_ procedure, the subsequent optimization in the local search procedure, PCC\({}^{2}\)LS_Search, aims to attain a smaller connected dominating set. To mitigate the cycling problem, we employ two two-level configuration checking strategies along with the tabu strategy. Additionally, it incorporates perturbation and vertex weighting strategies to guide the current candidate solution away from the local optimum. During vertex removal, solely selecting the vertex with the highest _Cscore_ value exacerbates the cycling problem within the PCC\({}^{2}\)LS_Search process. Thus, the introduction of the _Mscore_ function and noisy strategy [21] enhances vertex diversity, enabling the selection of vertices not previously considered in the candidate set. Moreover, a probability parameter, _\"fp\"_, decides whether to prioritize vertices with the largest _Cscore_ or the minimum _Mscore_ value. Finally, a candidate set, _CE_, is utilized to store the connected components of the current solution, ensuring that added vertices maintain solution feasibility. Based on these considerations, Algorithm 2 outlines the PCC\({}^{2}\)LS_Search procedure in detail.  
```
Input: the maximum number of iterations \(ITEM\_NUM\); an undirected, connected graph \(G(V,E)\) Output: a local best connected dominating set \(D^{\prime}\)
1.\(D^{*}\gets\)\(D\)\(\leftarrow\)InitConstructCDS (\(G\)) and \(it\)\(\leftarrow\) 1;
2. Initialize ConfChange[\(v\)] \(\leftarrow\) 1 for each \(v\) in \(V\);
3. While it \(<\) ITEM_NUM do
4. While\(D\) is a CDS do
5. if\(|D|<|D^{\prime}|\)then
6.\(D\)\(\leftarrow\)\(D\);
7.\(v\)\(\leftarrow\) select one vertex from \(D\) according to Remove_Rule;
8.\(D\)\(\leftarrow\)\(D\backslash\{v\}\);
9.\(v\)\(\leftarrow\) select one vertex from \(D\) randomly;
10.\(D\)\(\leftarrow\)\(D\backslash\{v\}\);
11.for\(i\)\(=\)1 to 0.05 \(*\)\(|\)\(V\)
12.\(v\)\(\leftarrow\) select one vertex from \(D\) according to Remove_Rule;
13.\(D\)\(\leftarrow\)\(D\backslash\{v\}\);
14. While \(D\) is not a CDS do
15. update CE;
16.\(v\)\(\leftarrow\) select one vertex from \(CE\) according to Add_Rule;
17.\(D\)\(\leftarrow\)\(D\cup\{v\}\);
18. tabu_vertex \(\leftarrow\)\(v\);
19.it++;
20. return\(D^{\prime}\);
```  
**Algorithm 2** PCC\({}^{2}\)Local_Search( )  
In the description of Algorithm 2, an initial solution is obtained in line 1 through the _InitConstructCDS_(\(0\)) function, and the number of iterative steps of the algorithm is initialized to 1. In line 2, the _ConfChange_(\(v\)) value of each vertex \(v\in V\) is initialized to 1. In lines 5-6, when the current candidate solution \(D\) is a connected dominating set, \(D\) is compared with the local optimal solution \(D^{\prime}\). If \(D\) is better than \(D^{\prime}\), then \(D^{\prime}\) is updated to \(D\). Then, in lines 7-8, the algorithm systematically removes vertices from the \(D\) until it becomes infeasible. At this stage, the algorithm selects vertices from the candidate solutions according to the **Remove rule**. In lines 9-10, when \(D\) is not a connected dominating set, randomly remove a vertex from the candidate solution. In lines 12-13, in order to expand the search space of the algorithm, \(0.05\times|V|\) vertices are removed from the candidate solutions according to the **Remove rule**. Next, in line 15, the set \(CE\) is updated. In lines 15-18, when \(D\) is not a connected dominating set, the algorithm adds some vertices to the candidate solution one by one until the candidate solution becomes a feasible connected dominating set. At this stage, the algorithm selects vertices from the set \(CE\) according to the **Add rule**. In line 18, add the vertices added to the candidate solution to the tabu list. Finally, in line 20, the locally best solution, \(D^{\prime}\), is returned.