The Patchy GA and Domination Problems

摘要

Let G = (V,E) be an undirected graph. A dominating set is any subset S is contained V such that, for all v ∈ V― S, v is adjacent to at least one element of S. The problem of determining, for arbitrary G and integer K, whether or not G has a dominating set of size less than or equal to K, is NP-complete (Garey & Johnson 1979); we denote this decision problem and the corresponding optimization problem by DOM. This paper represents a first attempt to apply genetic algorithms to the dominating set problem. We identify two classes of graphs―random geometric graphs and lattice-partitioned degree-4 graphs―for which GAs significantly outperform the greedy heuristic. Random geometric graphs have been well-studied in the computer science and mathematics literature. A lattice-partitioned random degree-4 graph is constructed as follows: form a p X q lattice of cells, each containing three vertices. Within each pair of horizontally and vertically adjacent cells, construct a random matching between the three vertices in each cell (wrap around for cells at the boundaries of the lattice).