Some APX-completeness results for cubic graphs

摘要

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. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 25]