1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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č.

$\endgroup$
2
  • $\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$
    – maliya
    Commented Nov 22, 2023 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 GD
    Commented Nov 22, 2023 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.