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

DOI10.1051/ITA:2005041zbMATH Open1085.68056arXivcs/0110025OpenAlexW2569714044MaRDI QIDQ3374757FDOQ3374757

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)

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.

Full work available at URL: https://arxiv.org/abs/cs/0110025

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

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)

Cites Work

• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• A Greedy Heuristic for the Set-Covering Problem
• The complexity of optimization problems
• Title not available (Why is that?)
• On the ratio of optimal integral and fractional covers
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of Kemeny elections
• 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
• On the hardness of approximating minimization problems
• More complicated questions about maxima and minima, and some closures of NP
• Bounded Query Classes
• The difference and truth-table hierarchies for NP
• Exact complexity of the winner problem for Young elections
• Exact analysis of Dodgson elections
• The strong exponential hierarchy collapses
• The Minimization Problem for Boolean Formulas
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• Complexity of the exact domatic number problem and of the exact conveyor flow shop problem
• Title not available (Why is that?)
• Title not available (Why is that?)

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)