The 0–1 inverse maximum stable set problem

In this paper we study the 0–1 inverse maximum stable set problem, denoted by IS{0,1}IS{0,1}. Given a graph and a fixed stable set, it is to delete the minimum number of vertices to make this stable set maximum in the new graph. We also consider IS{0,1}IS{0,1} against a specific algorithm such as GreedyGreedy and 2opt2opt, aiming to delete the minimum number of vertices so that the algorithm selects the given stable set in the new graph; we denote them by IS{0,1},greedyIS{0,1},greedy and IS{0,1},2optIS{0,1},2opt, respectively. Firstly, we show that they are NP-hard, even if the fixed stable set contains only one vertex. Secondly, we achieve an approximation ratio of 2−Θ(1logΔ) for IS{0,1},2optIS{0,1},2opt. Thirdly, we study the tractability of IS{0,1}IS{0,1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of IS{0,1}IS{0,1} and IS{0,1},2optIS{0,1},2opt for some other classes of graphs.