A neural design for solution of the maximal independent set problem

A new, artificial neural structure is presented for generating maximal independent sets of a graph. Although other authors have attempted to solve the maximum independent set problem with analog neural networks, the paper focuses herein on the problem of generating all, or several, maximal independent sets so that the likelihood of ‘covering’ all nodes in a graph is high. The design proposed is extremely fast, even in simulation on a conventional computer, and does not encounter difficulty determining both maximal and independent sets (as conventional approaches may). Empirical results suggest that the neural approach easily generates several maximal independent sets, and tends to cover all nodes of the graph in the sets generated. In comparison with a heuristic for finding the maximum independent set, the approach also works well; more often than not, it finds larger sets than does the heuristic.