Optimization and optimality test for the Max-Cut Problem

Chr. Hohmann, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
181 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)195-206
Number of pages12
JournalZeitschrift für Operations Research
Volume34
Issue number3
DOIs
Publication statusPublished - 1990

    Fingerprint

Keywords

  • IR-92529
  • METIS-140494

Cite this