It is hard to know when greedy is good for finding independent sets

Hans L. Bodlaender; Dimitrios M. Thilikos; Koichi Yamazaki

doi:10.1016/s0020-0190(96)00208-6

It is hard to know when greedy is good for finding independent sets

Hans L. Bodlaender, Dimitrios M. Thilikos, Koichi Yamazaki

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

The classes A_r and S_rr 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 A_r is coNP-complete for any fixed r ≥ 1, and deciding whether a given graph belongs to S₁ is DP-hard, and belongs to Δ₂P. Also, the MIS problem remains NP-complete when restricted to S_r.

Original language	English (US)
Pages (from-to)	101-106
Number of pages	6
Journal	Information Processing Letters
Volume	61
Issue number	2
DOIs	https://doi.org/10.1016/s0020-0190(96)00208-6
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

Access to Document

10.1016/s0020-0190(96)00208-6

Cite this

@article{d632243b37574d70a4b0d5e5d996d0c9,

title = "It is hard to know when greedy is good for finding independent sets",

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.",

keywords = "Analysis of algorithms, Approximation algorithms, Combinatorial problems",

author = "Bodlaender, {Hans L.} and Thilikos, {Dimitrios M.} and Koichi Yamazaki",

year = "1997",

month = jan,

day = "28",

doi = "10.1016/s0020-0190(96)00208-6",

language = "English (US)",

volume = "61",

pages = "101--106",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - It is hard to know when greedy is good for finding independent sets

AU - Bodlaender, Hans L.

AU - Thilikos, Dimitrios M.

AU - Yamazaki, Koichi

PY - 1997/1/28

Y1 - 1997/1/28

N2 - 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.

AB - 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.

KW - Analysis of algorithms

KW - Approximation algorithms

KW - Combinatorial problems

UR - http://www.scopus.com/inward/record.url?scp=0041634828&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041634828&partnerID=8YFLogxK

U2 - 10.1016/s0020-0190(96)00208-6

DO - 10.1016/s0020-0190(96)00208-6

M3 - Article

AN - SCOPUS:0041634828

SN - 0020-0190

VL - 61

SP - 101

EP - 106

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

It is hard to know when greedy is good for finding independent sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this