ISSN:
1432-5217
Keywords:
Max-cut
;
decision problem
;
optimization problem
;
polynomial transformation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Wir zeigen, daß folgende Probleme polynomial äquivalent sind: 1) Gegeben ein (gewichteter) GraphG, ein cutC vonG. Entscheide obC optimal ist oder nicht. 2) Gegeben ein (gewichteter) GraphG, ein cutC vonG. Entscheide, obC optimal ist oder nicht, und falls nicht, finde einen besseren cutC′. Eine Konsequenz hiervon ist, wie wir sehen werden, daß ein Optimalitätstest Orakel einen polynomialen Algorithmus zur approximativen Lösung von Max Cut Problemen liefert. Insbesondere folgt, daß das Erkennen von maximalen cuts in ungewichteten Graphen NP-schwer ist.
Notes:
Abstract We show that the following two problems are polynomially equivalent: 1) Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not. 2) Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not, and in case it is not, find a better solutionC′. As a consequence, an optimality testing oracle may be used to design a polynomial time algorithm for approximately solving the (weighted) Max-Cut Problem. This in turn implies that recognizing optimal cuts in an unweighted graph is NP-hard.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01415982
Permalink
