✦ LIBER ✦
On easy and hard hereditary classes of graphs with respect to the independent set problem
✍ Scribed by Vladimir E. Alekseev
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 162 KB
- Volume
- 132
- Category
- Article
- ISSN
- 0166-218X
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we introduce the concept of a boundary class, which is a helpful tool for classiÿcation of hereditary classes of graphs according to the complexity of the independent set problem. It is shown that in a class X deÿned by a ÿnite set of forbidden induced subgraphs, the problem is NP-hard if and only if X includes a boundary class. The paper presents a particular boundary class and establishes several new polynomially solvable cases for the independent set problem.