On approximation problems related to the independent set and vertex cover problems.

*(English)*Zbl 0554.68026Some open questions concerning the complexity of approximation algorithms for the Maximum Independent Set and Minimum Vertex Cover Problems are studied. It is shown that those questions are at least as hard as a sample of other open questions concerning approximating NP-hard problems, including Graph Coloring, Set Covering and Dominating Set Problems.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68R10 | Graph theory (including graph drawing) in computer science |

PDF
BibTeX
XML
Cite

\textit{R. Bar-Yehuda} and \textit{S. Moran}, Discrete Appl. Math. 9, 1--10 (1984; Zbl 0554.68026)

Full Text:
DOI

##### References:

[1] | Bar-Yehuda, R.; Even, S., A linear time approximation algorithm for the weighted vertex cover problem, J. algorithms, 2, 198-203, (1981) · Zbl 0459.68033 |

[2] | Bar-Yehuda, R.; Even, S., On approximating a vertex cover for planar graphs, Proc. 14th ann. ACM symp. theory of computing, 303-309, (1982) |

[3] | Bar-Yehuda, R.; Even, S., A local ratio theorem for approximating the weighted vertex cover problem, (), to appear in Annals Discrete Math · Zbl 0557.90072 |

[4] | Bar-Yehuda, R., Approximation algorithms for graph cover problems, () · Zbl 0554.68026 |

[5] | Chiba, S.; Nishizeki, T.; Satio, N., Applications of the lipton and Tarjan’s planar separator theorem, J. information proc., 4, 203-207, (1981) · Zbl 0477.68069 |

[6] | Chvátal, V., A greedy-heuristic for the set-covering problem, Math. operations res., 4, 3, 233-235, (1979) · Zbl 0443.90066 |

[7] | Even, S., Graph algorithms, (1979), Comp. Sci. Press Rockville, MD · Zbl 0441.68072 |

[8] | Garey, M.R.; Johnson, D.S., The complexity of near-optimal graph coloring, J. ACM, 23, 43-49, (1976) · Zbl 0322.05111 |

[9] | Garey, M.R.; Johnson, D.S., Computers and intractability, () · Zbl 0369.90053 |

[10] | Gavril, F., Computers and intractability, (), 134 |

[11] | D.S. Hochbaum, Efficient bounds for the stable set, vertex cover and set packing problems, School of Business Administration, Univ. of California, to appear in Discrete Appl. Math. |

[12] | Hochbaum, D.S., Approximation algorithms for the set covering and vertex cover problems, SIAM J. comput., 11, 3, 555-556, (1982) · Zbl 0486.68067 |

[13] | Johnson, D.S., Approximation algorithms for combinatorial problems, Jcss, 9, 256-278, (1974) · Zbl 0296.65036 |

[14] | Johnson, D.S., Worst case behavior of graph coloring algorithms, Proc. 5th southeastern conference on combinatorics, graph theory and computing, 513-527, (1974) |

[15] | Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041 |

[16] | Lipton, R.J.; Tarjan, R.E., Applications of a planar separator theorem, SIAM J. comput, 9, 3, 413-423, (1980) |

[17] | Nemhauser, G.L.; Trotter, L.E., Vertex packing: structural properties and algorithms, Math. programming, 8, 232-248, (1975) · Zbl 0314.90059 |

[18] | Paz, A.; Moran, S., Non deterministic polynomial optimization problems and their approximation, Theoret. comput. sci., 15, 251-277, (1981) · Zbl 0459.68015 |

[19] | Savage, C., Depth-first search and the vertex cover problem, Inform. process. lett., 14, 5, 233-235, (1982) · Zbl 0498.68041 |

[20] | Wigderson, A., A new approximate graph coloring algorithm, Proc. 14th ann. ACM symp. theory of computing, 325-329, (1982) |

[21] | A. Wigderson, Private communication. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.