Optimization and optimality test for the Max-Cut Problem

Chr. Hohmann; Walter Kern

doi:10.1007/BF01415982

Optimization and optimality test for the Max-Cut Problem

Chr. Hohmann
, Walter Kern

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

700 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 language	English
Pages (from-to)	195-206
Number of pages	12
Journal	Zeitschrift für Operations Research
Volume	34
Issue number	3
DOIs	https://doi.org/10.1007/BF01415982
Publication status	Published - 1990

Keywords

IR-92529
METIS-140494

Access to Document

10.1007/BF01415982

art_10.1007_BF01415982

Cite this

@article{435362689d634ba7a6be7d82afacdc88,

title = "Optimization and optimality test for the Max-Cut Problem",

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.",

keywords = "IR-92529, METIS-140494",

author = "Chr. Hohmann and Walter Kern",

year = "1990",

doi = "10.1007/BF01415982",

language = "English",

volume = "34",

pages = "195--206",

journal = "Zeitschrift f{\"u}r Operations Research",

issn = "0340-9422",

publisher = "Physica-Verlag",

number = "3",

}

TY - JOUR

T1 - Optimization and optimality test for the Max-Cut Problem

AU - Hohmann, Chr.

AU - Kern, Walter

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

KW - IR-92529

KW - METIS-140494

U2 - 10.1007/BF01415982

DO - 10.1007/BF01415982

M3 - Article

SN - 0340-9422

VL - 34

SP - 195

EP - 206

JO - Zeitschrift für Operations Research

JF - Zeitschrift für Operations Research

IS - 3

ER -

Optimization and optimality test for the Max-Cut Problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this