Loading…
The 0–1 inverse maximum stable set problem
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...
Saved in:
| Published in: | Discrete Applied Mathematics 2008-07, Vol.156 (13), p.2501-2516 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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
−
Θ
(
1
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. |
|---|---|
| ISSN: | 0166-218X 1872-6771 |
| DOI: | 10.1016/j.dam.2008.03.015 |