Hardness of approximating problems on cubic graphs
| Author(s) : | Viggo Kann Dip Informatics Sistemistica Paola Alimonti, |
| Publisher : | N/A |
| Publication Date : | 1997 |
| ISSN : | N/A |
| Abstract : | Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. This means that unless P=NP these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three. 1, |