Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
1 Answer
$\begingroup$
$\endgroup$
2
Yes, most algorithms for enumerating maximal cliques are based on exactly this principle. Since a clique is just an independent set in the complement, you could simply take $\overline G$ and enumerate cliques. Of course, if your graph is very sparse, this might in practice not be a good idea.
The trivial branching algorithm would just try to add a new vertex to the solution, and delete all its neighbors in the solution.
On the other hand, there is a class of problems called reconfiguration problems in which we want to go from one solution to another with certain restrictions, e.g., we want to go from solution to solution with only adding and deleting vertices, or we want to move solutions along edges, etc. There is a paper on this for independent set, Complexity of independent set reconfigurability problems, by Kamiński, Medved, and Milanič.
-
$\begingroup$ the reconfiguration problems assume a graph with two feasible solutions (Independent sets) and tend to find the sequence of independent sets to reach the given feasible solution from the initial one. I want to know is there an algorithm that, from a feasible solution can generate an other feasible solution through adding and deleting vertices. In other words, given a graph and one independent set IS1 (not two), how to add or delete vertices in a way that the new set is also independent? $\endgroup$– maliyaNov 22 at 4:24
-
$\begingroup$ Yes, deleting any vertex from the solution will be another solution. Adding any vertex to the solution and then deleting its neighbors from the solution is yet another solution. $\endgroup$– Pål GDNov 22 at 9:35