Publication . Cardoso, Domingos M.; Lozin, Vadim V.; Luz, Carlos J.; Pacheco, Maria F.
The paper begins with a new characterization of (k,τ)-regular sets.
Then, using this result as well as the theory of star complements, we
derive a simplex-like algorithm for determining whether or not a graph
contains a (0,τ)-regular set. When τ = 1, this algorithm can be applied to
solve the efficient dominating set problem which is known to be NP-
complete. If −1 is not an eigenvalue of the adjacency matrix of the graph,
this particular algorithm runs in polynomial time. However, although it
doesn’t work in polynomial time in general, we report on its successful
application to a vast set of randomly generated graphs.
