Connected positive influence dominating set in k-regular graph

The positive influence dominating set(PIDS) problem is a well-known APX-hard problem and there exists a greedy approximation algorithm with an approximation ratio of H(δ). However, the PIDS which is formed by this algorithm is not connected. This paper proposes an algorithm with an approximation ratio of H(12) to find the connected PIDS in a cubic graph. Furthermore, this paper also proposes an algorithm with an approximation ratio of H(9) to find the partial positive influence dominating set(PPIDS). Both of these two algorithms have a time complexity of O(n³). In addition, we prove that for every node in the PIDS(or PPIDS) which is formed by our algorithms, there exists at least one node in the PIDS(or PPIDS) that is its two-hop neighbor. We also proved that in a cubic graph, the subgraph induced by PIDS is connected. These conclusions are also true in k-regular graphs.