Tracking the P-NP boundary for well-covered graphs
✍ Scribed by Sankaranarayana, Ramesh S.
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 135 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Certain fundamental graph problems like recognition, dominating set, Hamiltonian cycle and path, and clique partition, which are hard for well-covered graphs in general, can be solved efficiently for very well covered graphs. We address the question of how far the class of very well covered graphs can be generalized before such problems become hard. In this context, we examine the complexity of such problems for two subclasses of well-covered graphs, one properly containing the other, with the smaller one properly containing the family of very well covered graphs. We show that the problems studied algorithmically separate the subclasses from each other and from the families of well-covered and very well covered graphs.