ǂThe ǂexact weighted independent set problem in perfect graphs and related classes
Abstract
The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes. We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudopolynomial time, while on some others it remains strongly NP-complete.In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.
Keywords
graf;neodvisna množica;popolni graf;dvodelni graf;graph theory;complexity;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2009 |
| Typology: | 1.08 - Published Scientific Conference Contribution |
| Organization: | UP - University of Primorska |
| UDC: | 519.17 |
| COBISS: |
1024190548
|
| ISSN: | 1571-0653 |
| Parent publication: | ǂThe ǂV Latin-American Algorithms, Graphs, and Optimization Symposium |
| Views: | 2694 |
| Downloads: | 116 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | Unknown |
|---|---|
| Secondary keywords: | graph theory;complexity; |
| Type (COBISS): | Not categorized |
| Pages: | Str. 317-322 |
| Issue: | ǂVol. ǂ35 |
| Chronology: | 2009 |
| DOI: | 10.1016/j.endm.2009.11.052 |
| ID: | 1493176 |
Recommended works:
ǂThe ǂexact weighted independent set problem in perfect graphs and related classes
2009,
no subtitle data available
Equistarable bipartite graphs
2016,
no subtitle data available
On Almost Well-Covered Graphs of Girth at Least 6
2018,
no subtitle data available
From DNA sequencing to exact weighted independent sets
2007,
Workshop on information theory and related fields, Bielefeld, December 03 - 06, 2007
On plane bipartite graphs without fixed edges
2007,
no subtitle data available