.
and
.
and one endpoint in
.
[
24
].
Variation in which the degree of
G
is bounded by a constant
B
for
is still A
PX
-complete [
284
] and [
4
].
The weighted problem, where every edge is assigned a nonnegative weight
and the objective is to maximize the total weight of the edges in the cut is
also approximable within 1.1383 [
135
].
Maximum Bisection
, the weighted problem with the additional
constraint that the partition must cut the graph into halves of the
same size, is approximable within 1.54
[
116
] and [
265
].
Variation in which some pairs of vertices are restricted to be on the
same side (or on different sides) is still approximable within 1.138
[
135
].
Viggo Kann