Suppose I have an optimal solution to the maximum weight independent/stable set problem on an arbitrary graph. If I were to induce a clique among a subset of its vertices (and perhaps add in some additional nodes that are only adjacent to the nodes of the induced clique), does there exist an efficient way in which I use the original optimal solution (i.e. its structure as a starting solution) to find the new optimal maximum weight independent set in the modified graph??

  • $\begingroup$ Do you have any promises on how the instance is set up? The answer is a likely "no" in general. Otherwise, to find a maximal independent set in any graph $G=(V,E)$ one can just add in $2|V|$ vertices adjacent to all of $V$ but otherwise pairwise non-adjacent, call that your starting independent set, and let your algorithm find out what happens after you eliminate this synthetic independent set by transforming it into a clique. The new maximal independent set in your modified graph with $3|V|$ vertices is exactly the same as it was in the original graph, so you don't introduce anything extra. $\endgroup$ – Yonatan N Jan 4 at 10:27
  • $\begingroup$ I am specifically after a solution to the maximum weight problem where each node has a weight assigned to it and I want the independent set that has the largest weight. It's hard to describe but the structure of the graphs that I am working with, I do believe possess special structure. They can be characterized as a three-dimensional lattice of maximum cliques with the connection between any two cliques being some smaller sized clique contained in both. The size of the cliques and connections are always known with the sizes of the connections being smaller the further two cliques are away. $\endgroup$ – Student Jan 6 at 15:38
  • $\begingroup$ The promises on the instance would be that the induced clique structure basically always occurs at the peripheries of the graph and the nodes on which it is induced are already connected within a chordal sub-graph. $\endgroup$ – Student Jan 7 at 7:21
  • $\begingroup$ Additionally, the nodes on which the clique is induced on are always a star if that helps $\endgroup$ – Student Jan 7 at 13:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.