Abstract
The classes Ar and Srr are defined as the classes of those graphs, where the minimum degree greedy algorithm always approximates the maximum independent set (MIS) problem within a factor of r, respectively, where this algorithm has a sequence of choices that yield an output that is at most a factor r from optimal, r ≥ 1 a rational number. It is shown that deciding whether a given graph belongs to Ar is coNP-complete for any fixed r ≥ 1, and deciding whether a given graph belongs to S1 is DP-hard, and belongs to Δ2P. Also, the MIS problem remains NP-complete when restricted to Sr.
Original language | English (US) |
---|---|
Pages (from-to) | 101-106 |
Number of pages | 6 |
Journal | Information Processing Letters |
Volume | 61 |
Issue number | 2 |
DOIs | |
State | Published - Jan 28 1997 |
Keywords
- Analysis of algorithms
- Approximation algorithms
- Combinatorial problems
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications