Skip to Main content Skip to Navigation
Other publications

The 0-1 inverse maximum stable set problem

Abstract : Given an instance of a weighted combinatorial optimization problem and its feasible solution, the usual inverse problem is to modify as little as possible (with respect to a fixed norm) the given weight system to make the giiven feasible solution optimal. We focus on its 0-1 version, which is to modify as little as possible the structure of the given instance so that the fixed solution becomes optimal in the new instance. In this paper, we consider the 0-1 inverse maximum stable set problem against a specific (optimal or not) algorithm, which is to delete as few vertices as possible so that the fixed stable set S* can be returned as a solution by the given algorithm in the new instance. Firstly, we study the hardness and approximation results of the 0-1 inverse maximum stable set problem against the algorithms. Greedy and 2-opt. Secondly, we identify classes of graphs for which the 0-1 inverse maximum stable set problem can be polynomially solvable. We prove the tractability of the problem for several classes of perfect graphs such as comparability graphs and chordal graphs.
Document type :
Other publications
Complete list of metadatas

https://halshs.archives-ouvertes.fr/halshs-00130507
Contributor : Lucie Label <>
Submitted on : Monday, February 12, 2007 - 3:10:25 PM
Last modification on : Sunday, January 19, 2020 - 6:38:23 PM
Document(s) archivé(s) le : Tuesday, April 6, 2010 - 9:30:26 PM

File

B06089.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : halshs-00130507, version 1

Collections

Citation

Yerim Chung, Marc Demange. The 0-1 inverse maximum stable set problem. 2006. ⟨halshs-00130507⟩

Share

Metrics

Record views

291

Files downloads

660