The 01 inverse maximum stable set problem ?
In this paper we study the 01 inverse maximum stable set problem, denoted by IS{0,1} I S { 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} I S { 0 , 1 } against a specific algorithm such as Greedy G r e e d y and 2opt 2 o p t , 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},greedy I S { 0 , 1 } , g r e e d y and IS{0,1},2opt I S { 0 , 1 } , 2 o p t , 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 ? ? ( 1 l o g ? ) for IS{0,1},2opt I S { 0 , 1 } , 2 o p t . Thirdly, we study the tractability of IS{0,1} I S { 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} I S { 0 , 1 } and IS{0,1},2opt I S { 0 , 1 } , 2 o p t for some other classes of graphs.
maximum stable set problem approximation ratio perfect graphs inverse combinatorial optimization np-hardness