The 0-1 inverse maximum stable set problem

Yerim Chung () and Marc Demange ()
Additional contact information
Yerim Chung: CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique
Marc Demange: ESSEC Business School

Post-Print from HAL

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.

Keywords: NP-hardness; maximum stable set problem; performance ratio; perfect graphs; Combinatorial inverse optimization; perfect graphs.; graphes parfaits.; rapport d'approximation; stable maximum; Optimisation combinatoire inverse (search for similar items in EconPapers)
Date: 2006-12
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-00130507
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in 2006

Downloads: (external link)
https://shs.hal.science/halshs-00130507/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-00130507

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().