A polynomial-time approximation to a minimum dominating set in a graph
2021
Finding a dominating set with the minimum cardinality in a graph $G=(V,E)$ (a subset of vertices $S\subseteq V$ such that every vertex $v\in V\setminus S$ has at least one neighbor in set $S$) is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph $G$, which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for our algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters. The greedy algorithm of the first stage has essentially the same properties as the earlier known state-of-the-art algorithms for the problem. The second purification stage results in an essential improvement of the quality of the dominant set created at the first stage. We have measured the practical behavior of the algorithm of both stages on randomly generated problem instances. We have used two different random methods to generate our graphs, each of them yielding graphs with different structures. For the first class of instances the greedy algorithm of stage 1 already gave quite good solutions, hence the reduction at stage 2 was not so significant. For the second class of instances, the algorithm of stage 1 has delivered the solutions of a poor quality, however, the algorithm of stage 2 turned out to be very efficient: applied to the graphs of the second class, it has significantly reduced the size of the solutions delivered by stage 1 creating optimal or close to optimal solutions.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI