Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP

DOI10.1016/S0020-0190(97)00219-6zbMath1338.68087OpenAlexW2005980753MaRDI QIDQ293222

Jörg Rothe, Edith Hemaspaandra

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002196?np=y

zbMATH Keywords

computational complexityapproximationmaximum independent set problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP ⋮ Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP ⋮ The complexity of Kemeny elections

Cites Work

• Unnamed Item
• It is hard to know when greedy is good for finding independent sets
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• The complexity of facets (and some facets of complexity)
• More complicated questions about maxima and minima, and some closures of NP
• The polynomial-time hierarchy
• Well-covered claw-free graphs
• Greed is good
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses

This page was built for publication: Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP