Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

DOI10.1051/ITA:2005041MaRDI QIDQ3374757zbMATH OpenOpenAlexFDO

Authors Edith Hemaspaandra, Jörg Rothe, Holger Spakowski

Publication date 22 February 2006

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0110025, http://www.numdam.org/item?id=ITA_2006__40_1_75_0, https://eudml.org/doc/92790

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which either of these heuristics can find an optimal solution remains NP-hard.

Recommendations

• scientific article; zbMATH DE number 1953099
• scientific article; zbMATH DE number 8779
• A graph approximation heuristic for the vertex cover problem on planar graphs
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• A list heuristic for vertex cover

Cites work

• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2080215 (Why is no real title available?)
• scientific article; zbMATH DE number 1759396 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Approximation algorithms for combinatorial problems
• Bounded Query Classes
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Exact analysis of Dodgson elections
• Exact complexity of the winner problem for Young elections
• It is hard to know when greedy is good for finding independent sets
• More complicated questions about maxima and minima, and some closures of NP
• On the hardness of approximating minimization problems
• On the ratio of optimal integral and fractional covers
• Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
• The Minimization Problem for Boolean Formulas
• The complexity of Kemeny elections
• The complexity of optimization problems
• The difference and truth-table hierarchies for NP
• The strong exponential hierarchy collapses
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

Cited in

(3)

• Stability, vertex stability, and unfrozenness for special graph classes
• 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

This page was built for publication: Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3374757)