Volume 21, No 4, 2014, P. 3-11

UDC 519.2+621.391
A. A. Ageev, A. V. Kel’manov and A. V. Pyatkin
Complexity of the euclidean max cut problem

Abstract:
We consider the following problem: given a complete edge-weighted undirected graph whose vertices are points of a q-dimensional space, find a cut of maximum total weight. Two special cases are analyzed where the edge weights are equal to (i) the Euclidean distances between points representing the vertices, (ii) the squares of these distances. We prove that both cases of the problem are strongly NP-hard do no permit FPTAS unless P≠NP.
Bibliogr. 17.

Keywords: graph, cut, Euclidean space, NP-hard problem.

Ageev Alexander Alexandrovich ¹
Kel’manov Alexander Vasilievich ^1,2
Pyatkin Artem Valerievich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: ageev@math.nsc.ru, kelm@math.nsc.ru, artem@math.nsc.ru