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

Edith Hemaspaandra; Jörg Rothe; Holger Spakowski

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2006)

  • Volume: 40, Issue: 1, page 75-91
  • ISSN: 0988-3754

Abstract

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

How to cite

top

Hemaspaandra, Edith, Rothe, Jörg, and Spakowski, Holger. "Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 40.1 (2006): 75-91. <http://eudml.org/doc/245796>.

@article{Hemaspaandra2006,
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 $\text\{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.},
author = {Hemaspaandra, Edith, Rothe, Jörg, Spakowski, Holger},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {computational complexity; completeness; minimum vertex cover heuristics; approximation; parallel access to NP},
language = {eng},
number = {1},
pages = {75-91},
publisher = {EDP-Sciences},
title = {Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP},
url = {http://eudml.org/doc/245796},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Hemaspaandra, Edith
AU - Rothe, Jörg
AU - Spakowski, Holger
TI - Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2006
PB - EDP-Sciences
VL - 40
IS - 1
SP - 75
EP - 91
AB - 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 $\text{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.
LA - eng
KW - computational complexity; completeness; minimum vertex cover heuristics; approximation; parallel access to NP
UR - http://eudml.org/doc/245796
ER -

References

top
  1. [1] H. Bodlaender, D. Thilikos and K. Yamazaki, It is hard to know when greedy is good for finding independent sets. Inform. Process. Lett. 61 (1997) 101–106. Zbl1336.68094
  2. [2] V. Chvátal, A greedy heuristic for the set-covering problem. Math. Oper. Res. 4 (1979) 233–235. Zbl0443.90066
  3. [3] T. Eiter and G. Gottlob, The complexity class Θ 2 p : Recent results and applications, in Proc. of the 11th Conference on Fundamentals of Computation Theory. Lect. Notes Comput. Sci. 1279 (1997) 1–18. 
  4. [4] U. Feige, A threshold of ln n for approximating set cover. J. ACM 45 (1998) 634–652. Zbl1065.68573
  5. [5] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979). Zbl0411.68039MR519066
  6. [6] R. Graham, D. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley (1989). Zbl0668.00003MR1397498
  7. [7] L. Hemachandra, The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39 (1989) 299–322. Zbl0693.03022
  8. [8] E. Hemaspaandra and L. Hemaspaandra, Computational politics: Electoral systems, in Proc. of the 25th International Symposium on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 1893 (2000) 64–83. Zbl0996.68065
  9. [9] E. Hemaspaandra, L. Hemaspaandra and J. Rothe, Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. J. ACM 44 (1997) 806–825. Zbl0904.68111
  10. [10] E. Hemaspaandra, L. Hemaspaandra and J. Rothe, Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28 (1997) 2–13. Zbl0904.68111
  11. [11] E. Hemaspaandra and J. Rothe, Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP. Inform. Proc. Lett. 65 (1998) 151–156. Zbl06590681
  12. [12] E. Hemaspaandra, H. Spakowski and J. Vogel, The complexity of Kemeny elections. Theor. Comput. Sci. Accepted subject to minor revision. Zbl1086.68046MR2183163
  13. [13] E. Hemaspaandra and G. Wechsung, The minimization problem for boolean formulas. SIAM J. Comput. 31 (2002) 1948–1958. Zbl1008.68054
  14. [14] D. Johnson, Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9 (1974) 256–278. Zbl0296.65036
  15. [15] J. Kadin, P N P [ log n ] and sparse Turing-complete sets for NP. J. Comput. Syst. Sci. 39 (1989) 282–298. Zbl0693.68027
  16. [16] M. Krentel, The complexity of optimization problems. J. Comput. Syst. Sci. 36 (1988) 490–509. Zbl0652.68040
  17. [17] J. Köbler, U. Schöning and K. Wagner, The difference and truth-table hierarchies for NP. RAIRO-Inf. Theor. Appl. 21 (1987) 419–435. Zbl0642.03024
  18. [18] L. Lovász, On the ratio of optimal integral and fractional covers. Discrete Math. 13 (1975) 383–390. Zbl0323.05127
  19. [19] C. Lund and M. Yannakakis, On the hardness of approximating minimization problems. J. ACM 41 (1994) 960–981. Zbl0814.68064
  20. [20] C. Papadimitriou, Computational Complexity. Addison-Wesley (1994). Zbl0833.68049MR1251285
  21. [21] C. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall (1982). Zbl0503.90060MR663728
  22. [22] C. Papadimitriou and S. Zachos, Two remarks on the power of counting, in Proc. of the 6th GI Conference on Theoretical Computer Science. Lect. Notes Comput. Sci. 145 (1983) 269–276. Zbl0506.68039
  23. [23] T. Riege and J. Rothe, Complexity of the exact domatic number problem and of the exact conveyor flow shop problem. Theory of Computing Systems (2004). On-line publication DOI 10.1007/s00224-004-1209-8. Paper publication to appear. Zbl1100.68085MR2256634
  24. [24] J. Rothe, H. Spakowski and J. Vogel, Exact complexity of the winner problem for Young elections. Theory Comput. Syst. 36 (2003) 375–386. Zbl1061.90084
  25. [25] H. Spakowski and J. Vogel, Θ 2 p -completeness: A classical approach for new results, in Proc. of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science. Lect. Notes Comput. Sci. 1974 (2000) 348–360. Zbl1044.68062
  26. [26] K. Wagner, More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51 (1987) 53–80. Zbl0653.03027
  27. [27] K. Wagner, Bounded query classes. SIAM J. Comput. 19 (1990) 833–846. Zbl0711.68047

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.