The 0-1 inverse maximum stable set problem

Yerim Chung; Marc Demange

doi:10.1016/j.dam.2008.03.015

The 0-1 inverse maximum stable set problem

Yerim Chung, Marc Demange

Department of Business Administration

Research output: Contribution to journal › Article › peer-review

10 Citations (Scopus)

Abstract

In this paper we study the 0-1 inverse maximum stable set problem, denoted by 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 I S_{{0, 1}} against a specific algorithm such as G r e e d y and 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 I S_{{0, 1}, g r e e d y} and 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 - Θ (frac(1, sqrt(l o g Δ))) for I S_{{0, 1}, 2 o p t}. Thirdly, we study the tractability of I S_{{0, 1}} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of I S_{{0, 1}} and I S_{{0, 1}, 2 o p t} for some other classes of graphs.

Original language	English
Pages (from-to)	2501-2516
Number of pages	16
Journal	Discrete Applied Mathematics
Volume	156
Issue number	13
DOIs	https://doi.org/10.1016/j.dam.2008.03.015
Publication status	Published - 2008 Jul 6

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2008.03.015

Cite this

@article{dd350ee5a5784a0aa93fa86d13d3f905,

title = "The 0-1 inverse maximum stable set problem",

abstract = "In this paper we study the 0-1 inverse maximum stable set problem, denoted by 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 I S{0, 1} against a specific algorithm such as G r e e d y and 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 I S{0, 1}, g r e e d y and 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 - Θ (frac(1, sqrt(l o g Δ))) for I S{0, 1}, 2 o p t. Thirdly, we study the tractability of I S{0, 1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of I S{0, 1} and I S{0, 1}, 2 o p t for some other classes of graphs.",

author = "Yerim Chung and Marc Demange",

year = "2008",

month = jul,

day = "6",

doi = "10.1016/j.dam.2008.03.015",

language = "English",

volume = "156",

pages = "2501--2516",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "13",

}

TY - JOUR

T1 - The 0-1 inverse maximum stable set problem

AU - Chung, Yerim

AU - Demange, Marc

PY - 2008/7/6

Y1 - 2008/7/6

N2 - In this paper we study the 0-1 inverse maximum stable set problem, denoted by 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 I S{0, 1} against a specific algorithm such as G r e e d y and 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 I S{0, 1}, g r e e d y and 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 - Θ (frac(1, sqrt(l o g Δ))) for I S{0, 1}, 2 o p t. Thirdly, we study the tractability of I S{0, 1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of I S{0, 1} and I S{0, 1}, 2 o p t for some other classes of graphs.

AB - In this paper we study the 0-1 inverse maximum stable set problem, denoted by 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 I S{0, 1} against a specific algorithm such as G r e e d y and 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 I S{0, 1}, g r e e d y and 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 - Θ (frac(1, sqrt(l o g Δ))) for I S{0, 1}, 2 o p t. Thirdly, we study the tractability of I S{0, 1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of I S{0, 1} and I S{0, 1}, 2 o p t for some other classes of graphs.

UR - http://www.scopus.com/inward/record.url?scp=49749125944&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=49749125944&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2008.03.015

DO - 10.1016/j.dam.2008.03.015

M3 - Article

AN - SCOPUS:49749125944

SN - 0166-218X

VL - 156

SP - 2501

EP - 2516

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 13

ER -

The 0-1 inverse maximum stable set problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this