Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
42
Chapter
4.
The
Cut
Cone
and
l\-Metrics
(ii) (Vn,
d)
is
l\
-embeddable.
(iii) (Vn,
d)
is
L1
-embeddable.
(iv) There exist a measure space (0,
A,
J-G)
and
AI,
...
,An
E A such that d
ij
=
J-G(Ai6Ai) for all 1
~
i < j
~
n.
(v) (Vn'
d)
is an isometric subspace
offr·
I
At
this
point
let us observe a convexity
property
of
the
cut
semimetrics
entering
any decomposition
of
an
f
1
-embeddable distance. We need a definition.
Definition
4.2.7.
Let
(X,
d)
be
a distance space. A subset U
c::;
X is said to
be
d-convex
if
d(x,
y) =
d(x,
z) + d(z, y) and
x,
y E U imply that z E U.
Convex sets arise
naturally
in
the
context
of
f
1
-metrics. Namely,
Lemma
4.2.8.
Let
(X,
d)
be
an
f1
-embeddable distance space and suppose
that
d =
l:AcX
AA8(A) where
AA
2:
0 for all A
c::;
X.
Then, both sets A and X \ A
are d-corwex for every
cut
semimetric
8(A) entering the decomposition with a
positive coefficient
AA
>
o.
Proof.
The
result
follows from
the
fact
that
every triangle equality satisfied by
d is also satisfied by a
cut
semimetric 8(A) entering
the
decomposition
of
d.
I
We conclude
this
section
with
a
remark
on
how
the
equivalence (i)
~
(ii)
from
Proposition
4.2.4
can
be
generalized
in
the
context
of
Hamming
spaces
and
multicuts.
Let q
2:
2 be
an
integer
and
let
Sl,
...
,
Sq
be q pairwise disjoint
subsets
of
Vn
forming a
partition
of
V
n
, i.e., such
that
Sl
u
...
U
Sq
= V
n
.
Then,
the
multicut
semimetric
8(Sl'
...
,Sq)
is
the
vector of
ffi.En
defined by
8(Sl'
...
,Sq)ij
= 0
8(Sl,
...
,
Sq)ij
= 1
ifi,j
E
Sh
for some
h,
1
~
h
~
q,
otherwise
for
1
~
i < j
~
n.
The
following
can
be
easily checked.
Proposition
4.2.9.
Let
d E
ffi.E
n
,
let (Vn'
d)
be
the associated distance space
and
let
q1,
..
. ,qk
2:
1
be
integers. The following assertions are equivalent.
(1
·)
",k
,,(s(h) S(h)) h (S(h) S(h)) . . . f f
d =
L.h=l
vI'··
.,
%
,were
1'·
..
' %
zs
a partztwn 0 V
n
,
or
each h
=
I,
...
,k.
(ii) (Vn'
d)
is an isometric subspace
of
the
Hamming
space
(II~=dO,
1,
...
,qh
- I}, dH).
I
Hence,
we
obtain
again
the
equivalence (i)
~
(ii) from
Proposition
4.2.4
in
the
case
when
q1
=
...
=
qk
=
2.
Observe
that
the
Hamming
space
(II~=l
{O,
1,
...
,
qh
-I},
d
H
)
coincides
with
the
graphic
metric
space
of
the
graph
4.3 Realizations, Rigidity, Size
and
Scale 43
II~=1
Kqh
(the
graph
obtained
by
taking
the
Cartesian
product
of
the
complete
graphs
K
q1
,
•••
, K
qk
).
Note also
that
for every
partition
(8
1
,
...
,8
q
)
of
V
n
.
Therefore, every
Hamming
space is
1'1-
embeddable
with
scale 2 (see
the
definition below).
As
an
example, consider
the
distance d
:=
(1,1,1,2; 1,2,2;
2,
1;
1)
E
~E5.
Then
the
distance
space
(V5,
d)
is
an
isometric subspace
of
the
Hamming
space
(
{O,
1,2} x
{O,
I}, d
H
).
To see it, consider
the
isometric embedding
i E {1,2,3,4,5}
f-+Vi
E {0,1,2} x {0,1}
where
VI
= (0,0),
V2
= (1,0),
V3
= (2,0),
V4
= (0,1),
and
V5 = (2,1). Equiva-
lently,
d can be decomposed as
the
following
sum
of
multicut
semimetrics:
d=
8({1,4},{2},{3,5}) +8({1,2,3},{4,5}).
4.3
Realizations,
Rigidity,
Size
and
Scale
We
group
here several definitions
related
to
1'1-
and
hypercube
embeddability.
Namely, for
an
I'I-metric,
we
define
the
notions
of
realizations, rigidity, size
and
scale.
Realizations.
We define here
the
notions of
lilt-
and
Z+-realizations for
an
I'l-metric;
they
will
be
used especially in
Part
IV.
Definition
4.3.1.
Let
d
be
a distance
on
V
n
.
Any
decomposition:
d = L >'s8(8),
S~Vn
where
>'s
~
° (resp.
>'s
E
Z+)
for
all
8,
is called an lilt-realization (resp.
Z+-
realization)
of
d.
Hence, for
an
I'I-embeddable distance d
on
V
n
,
we
can
speak
alternatively
of
an
I'I-embedding of d (which consists of a
set
of n vectors
Vl,
...
,Vn
E
~m
(m
~
1)
such
that
d
ij
=11
Vi
-
Vj
III
for all
i,j
E V
n
),
or of
an
lilt-realization
of
d (which is a decomposition
of
d as a nonnegative linear
combination
of
cut
semimetrics) .
In
the
same
way,
if
d is hypercube embeddable,
we
can speak alternatively
of a
hypercube
embedding
of d (which consists of a
set
of n vectors
VI,
•..
,
Vn
E
{O,l}m
(m
~
1) such
that
d
ij
=11
Vi
-
Vj
III
for all
i,j
E V
n
),
or
of a
Z+-
realization
of
d (which is a decomposition of d as a nonnegative integer linear
combination
of
cut
semimetrics).
The
binary n x m
matrix
M whose rows are
44
Chapter
4.
The
Cut
Cone
and
iI-Metrics
the
vectors
VI,
...
,
Vn
(providing a hypercube embedding of d) is called
an
h-
realization matrix (or, simply, realization matrix)
of
d.
If
SI,
..
" Sm denote
the
subsets of
Vn
whose incidence vectors are the columns of
M,
then
d = EJ!=I o(Sj)
is a Z+-realization of
d.
This simple fact is the basic idea for the proof of
the
equivalence (i)
~
(ii) in Proposition 4.2.4.
If
VI,""
Vn
is
an
iI-embedding of
d,
then
the n x m
matrix
M whose rows
are
the
vectors
VI,
...
,V
n
is also called a realization matrix of
d.
Note, however,
that
the associated Ill,--realization of d cannot be read immediately from M as
in the hypercube case (we have seen in the proof of Proposition
4.2.2 how
to
construct
an
Ill,-
-realization).
As
an
example, consider the distance on V
4
defined by d
:=
(3,1,3;
4,
4;
2)
E
lIRE
•.
The
vectors
VI
=
(1,1,1,0,0),
V2
(1,0,0,0,1),
V3 =
(0,1,1,0,0),
V4 =
(0,1,1,1,1)
provide a hypercube embedding of
d,
corresponding to
the
following
Z+-realization of
d:
d o({1,2}) +2o({2}) +o({4}) +o({2,4}),
(
1 1 1 0
0)
.....
10001
wIth assOCIated realizatIon
matnx
0 1 1 0 0 .
o 1 1 1 1
Rigidity.
Let (Vn,
d)
be a distance space.
Then,
(Vn,
d)
is said
to
be
iI-rigid
if d
admits
a unique Ill,--realization. Similarly, (Vn'
d)
is said
to
be h-rigid
if
d
admits
a unique Z+-realization.
The
notion of iI-rigidity is, in fact, directly relevant to
the
existence of simplex faces for
the
cut
cone, as
the
next result shows.
Lemma
4.3.2.
Let C
:=
Ill,-(VI"'" v
p
)
~
wn
be
a cone, where each vector
Vi
lies on an extreme ray
of
C. Suppose, moreover, that the cone C is not a
simplex cone. Then, each point that lies
in
the relative interior
of
C admits at
least two (in fact, an infinity
of)
distinct decompositions
as
a nonnegative linear
combination
of
the generators
VI,
...
)
Vp.
Proof.
We
can suppose without loss of generality
that
C is full-dimensional.
Let
x E C lying
in
the interior of
C.
By Caratheodory's theorem,
we
have
x =
E~=I
).hVih
where
).1,
...
,).k
> 0
and
{Vii,"
.
,Vik}
is a linearly independent
subset of {VI,'" ,
V
p
}.
If
k
:::;
m -
1,
then
one
can
easily construct
another
decomposition of
x.
(Indeed, let H
be
a hyperplane containing
Vii"
..
,
Vik)
X.
As x is
an
interior
point
of C, H cuts C into two nonempty
parts
and, thus,
x = Y + z where y belongs to one
part
and
z to
the
other one.) Suppose now
that
k =
m.
As C is not a simplex cone,
we
have p
2':
k +
1,
there exists
Vk+I
E
{VI,
...
,V
p
} \
{Vi"""Vik}'
As
the set
{Vil'
...
,Vik,Vk+l}
is linearly
dependent, there exist
aI,
...
,
ak
E
lIR
such
that
E~=I
ahvih
+
Vk+l
O.
Then,
x =
E~=I
().h
+
).ah)vih
+
).Vk+l
is another decomposition of
x,
setting).
1
if
all
ah's
are nonnegative
and),
:=
mine -
~
I
ah
<
0)
otherwise. I
4.3 Realizations, Rigidity, Size
and
Scale
45
Corollary
4.3.3.
The following assertions
are
equivalent for a distance space
(Vn,
d).
(i) (Vn'
d)
is £l-rigid, i.e., there is a unique way
of
decomposing d
as
a non-
negative linear combination
of
nonzero cut semimetrics.
(ii) d lies on a simplex face
of
CUT
n
.
Proof.
The
implication (ii)
=}
(i) is obvious, while (i)
=}
(ii) follows from
Lemma
4.3.2 applied
to
the
smallest face of
CUTn
that
contains
d.
I
The
notion
of
h-rigidity
can
be
reformulated in
the
following way,
in
terms
of
h-realization matrices. Let
(Vn,
d)
be
a
hypercube
embeddable
distance space.
Let
M
be
an
h-realization
matrix
of
(Vn'
d).
The
following
operations
(a), (b),
(c)
on
M yield a new h-realization
matrix
for (Vn'
d):
(a)
Permute
the
columns of
M.
(b)
Add
modulo
2 a
binary
vector to every row
of
M.
(c)
Add
to
M,
or
delete from
M,
a column which is
the
zero vector or
the
all-ones vector.
Two
hypercube
embeddings of (Vn' d) are said to
be
equivalent if
their
associated
realization matrices
can
be
obtained
from one
another
via
the
above operations
(a),(b),(c).
Then,
(Vn,d) is h-rigid if
and
only if it has a unique
hypercube
embedding,
up
to
equivalence.
£1-
and
h-Size.
We now
turn
to
the
notions of £1-size
and
h-size.
Suppose
d
is a
distance
on
V
n
.
If
d = L0,tSCV
n
)..s8(S)
is
a decomposition
of
d as a linear
combination
of
nonzero
cut
semimetrics,
then
the
quantity
L0,tSCV
n
)..s
is
called
its
size. Moreover, if d
is
£1-embeddable
then
the
quantity
( 4.3.4)
Sf
l
(d)
:=
min(
2:
)..s
I d =
2:
)..s8(S)
with
)..s
2':
0 for all S)
0,tscv
n
0,tscv
n
is
called
the
minimum
£1-size of
d.
Similarly, if d
is
hypercube embeddable,
then
( 4.3.5)
sh(d)
:=
min(
2:
)..s
I d =
2:
)..s8(S)
with
)..s
E
Z+
for all
S)
0,tscv
n
0,tscv
n
is
called
the
minimum
h-size
of
d.
This
parameter
has
the
following
interpreta-
tion:
The
minimum
h-size
of
d
is
equal to
the
minimum
dimension
of
a
hypercube
in
which d
can
be
isometrically embedded.
One
can
easily
obtain
some
bounds
on
the
minimum
£1-size. Suppose
that
d = L0,tSCV
n
)..s8(S)
with
)..s
2':
0 for all S. As n - 1 S
L1~i<j~n
8(S)(i,j)
S
lI-'
III
for each
subset
S
i=
0,
V
n
,
we
obtain
(4.3.6)
46
Chapter
4.
The
Cut
Cone
and
C
1
-Metrics
Moreover, equality holds in
the
lower
bound
of
(4.3.6) if
and
only if
the
decom-
position
of
d uses only equicuts (i.e.,
>'s
¥-
0 only if
lSI
= l I
J,
II1)
and
equality
holds in
the
upper
bound
if
and
only if
the
decomposition uses only
star
cuts
(Le.,
>'s
¥-
0 only if
lSI
= 1).
Example
4.3.7.
Let
2:D.
n
denote
the
equidistant
metric
on
Vn
taking
the
value
2 on all pairs.
Then,
21
n
is
C
1
-rigid if
and
only if n =
3.
Indeed, 213
is
C
1
-rigid
because
the
cut
cone
CUT
3
is
a simplex cone,
and
21
n
is
not
C
1
-rigid for n
:::::
4
as
21
n
= L
8({i})
=
_1_
L
8({i,j})
l:'Oi:'On
n - 2 l:'Oi<j:'On
has
two
distinct
~-realizations.
On
the
other
hand,
21
n
is
h-rigid
if
and
only if n
¥-
4,
its unique
Z+-
realization being given by: 21
n
=
2:~1
8( {i}); see
Theorem
22.0.6.
The
metric
2:D.4
has one
additional
Z+-realization, namely,
2:D.4
= 8({1,2}) + 8({1,3}) +
8({1,4}).
Hence, Sh(21
n
)
= n for n
¥-
4
and
sh(2:D.
4
)
=
3.
On
the
other
hand,
Sf
1
(2:D.
n
)
=
4(nn-l)
if n
is
even
and
Sf
1
(2:D.
n
)
=
n:;l
if n
is
odd. I
Using
the
linear
programming
duality theorem,
the
minimum
C1-size
of
dean
also
be
expressed as
Clearly,
in
this
maximization
problem, it suffices to consider
the
vectors v E
JRE
n
for which
the
inequality v
T
x
:::::;
1 defines a facet
of
the
cut
polytope
CUT~.
As
an
illustration, let us
mention
an
exact formulation for
Sf1
(d)
in
the
case
n
:::::;
5.
All
the
facets
of
CUTn
are known for n
:::::;
5.
Namely, they are defined
by
the
triangle
inequalities (3.1.1) if n
:::::;
4,
and
they are defined by
the
triangle
inequalities (3.1.1) together
with
the
pentagonal
inequalities (6.1.9) if n =
5.
This
permits
to
obtain
that,
for d E
CUT
4
,
(d)
(
d(i,j)+d(i,k)+d(j,k)
1
1
<
..
k<4)
Sf,
=
max
2 _ l < J < _
and,
for d E CUT5,
S'l
(d)
=
max
(d(i,j)+d(i,kl+d(j,k)
11
< i < . < k <
5.
2:1<><i<5
d(i,j).
< 2 - J
-,
6 ,
2:1<;<i<5
d(i,j)-2
2:1<i<5
iii
d(i,j)
11
< i <
5)
.
2 - -
Scale.
The
following result
is
an
immediate
consequence of Propositions 4.2.2
and
4.2.4.
Proposition
4.3.8.
Let (Vn'
d)
be
a distance space where d is rational valued.
Then,
(Vn'
d)
is C
1
-embeddable
if
and only
if
(Vn'
TJd)
is hypercube embeddable for
4.3 Realizations, Rigidity, Size
and
Scale
47
some
scalar
'1'/.
I
Let d be a distance on
Vn
that
is iI-embeddable
and
takes rational values.
Every integer
'1'/
for which (Vn,
'l'/d)
is
hypercube embeddable is called a scale
of
(Vn,
d); then,
we
also say
that
d is hypercube embeddable with
the
scale r/.
The
smallest such integer
'1'/
is
called the
minimum
scale
of
(Vn, d)
and
is
denoted by
'I'/(d).
It
is
easy to see
that
all integer valued iI-embeddable distances on
Vn
admit
a common scale.
Lemma
4.3.9.
There exists an integer a
such
that
ad
is hypercube embeddable
for
every iI-embeddable distance d
on
Vn
that is integer valued.
Proof.
Let X
be
a set
of
linearly independent cut semimetrics on V
n1
let
Mx
denote the
matrix
whose columns are the members
of
X,
and
let
ax
denote the
smallest absolute value of
the
determinant
of
a
IXI
x
IXI
nonsingular
submatrix
of
Mx.
Then,
we
define a as the lowest common multiple
of
the integers
ax
(for X
arbitrary
set of linearly independent
cut
semimetrics). This integer a satisfies
the
lemma. Indeed, let d be
an
integer valued distance on
Vn
that
is iI-embeddable.
By Caratheodory's theorem,
d can
be
decomposed as d =
L6(S)EX
>"s8(S),
where
X is a set
of
linearly independent
cut
semimetrics
and
>"s
> 0 for all
S.
Let A
be a
IXI
x
IXI
nonsingular
submatrix
of A/x with IdetAI =
ax,
let E denote
the
index set for
the
rows of A
and
set dE
:=
(dij)ijEE.
Then,
A>"
dE, Le.,
>..
=
A-IdE.
Applying Cramer's rule,
we
obtain
that
(detA)>" is integer valued.
This shows
that
ad
is hypercube embeddable. I
We
deduce from
the
above proof the following (very rough) upper
bound
for
the
minimum
scale
of
an
integral iI-distance d on
Vn
(as
the
determinant
of
a k x k binary
matrix
is less
than
or
equal to
k!
in absolute value).
Let us define
'l'/n
as
the
smallest integer
'1'/
such
that
'l'/d
is
hypercube em-
beddable for every
ii-embeddable
distance d on
Vn
that
is
integer valued
and
satisfies:
d(i,j)
+d(i,k)
+d(j,k)
E 2Z
for
all
i,j,k
E V
n
•
(This condition ensures
that
d
can
be
decomposed as an integer
sum
of
cut
semimetrics,
an
obvious necessary condition for hypercube embeddabilitYi see
(~)
Proposition 25.1.1.) Hence, by
the
above,
'l'/n
:s;
II
k!.
In
fact, as
we
will see in
k=1
Section 25.2,
'l'/n
1 for n
:s;
5,
and
'fJ6
2.
48
Chapter
4.
The
Cut
Cone
and
£l-Metrics
4.4
Complexity
Questions
We
formulate here several basic problems
related
to
cut
semimetrics
and
we
indicate
their
complexity
status.
A typical way
to
show
that
a given
problem
(P)
is
NP-hard
is
to
show
that
some known NP-complete
problem
(PO) reduces
polynomially
to
it.
We
use as
starting
point
the
following well-known problem:
(PO)
The
partition
problem.
Instance:
A nonnegative integer vector b = (bi,
...
, b
n
).
Question:
Can
b
be
partitioned
?
That
is, does
there
exist S
~
Vn
such
that
LiES
b
i
=
LiEV
n
\S
b
i
?
Complexity:
NP-complete
(Karp
[1972]).
(PI)
The
max-cut
problem
(decision version).
Instance:
A vector w E
z!n
and
K E
Z+.
Question:
Does
there
exist S
~
Vn
such
that
w
T
t5(S)
~
K ?
Complexity:
NP-complete
(Karp
[1972]).
Proof.
It
is clear
that
(PI)
is in NP. To see
that
(PI)
is NP-complete, one
can
observe (following
Karp
[1972])
that
(PO)
polynomially reduces
to
it. Indeed,
given integers
b
1
, .
..
,b
n
EN,
define w E ZEn
and
K E Z+ by Wij
:=
bibj (for
ij
E
En)
and
K:=
i(L?=l
b
i
)2.
Then,
for S
~
V
n
, w
T
t5(S) =
(LiES
bi)(L;EVn\S
bi)
~
K
if
and
only
if
LiES
b
i
=
~
L?=l
bi, i.e.,
if
b
can
be
partitioned.
I
(P2)
The
max-cut
problem
(optimization
version).
Instance:
A vector W E
z!n.
Question:
Find
S
~
Vn
for which w
T
t5(S) is
maximum.
Complexity:
NP-hard.
While
NP-hard
in
general,
the
max-cut
problem
may
become easy for
certain
classes
of
weight functions.
It
is convenient
to
represent a weight
function
by
its
supporting
graph
(with
edges
the
pairs
with
nonzero weights). Note first
that
the
max-cut
problem
remains
NP-hard
when
restricted
to
0,
I-valued
weight func-
tions
and
to
each
of
the
following classes of graphs: cubic
graphs
(Yannakakis
[1978]),
graphs
having a
node
whose deletion results
in
a
planar
graph
(Bara-
hona
[1982]),
chordal
graphs,
tripartite
graphs, complements of
bipartite
graphs
(Bodlaender
and
Jansen
[1994]).
On
the
other
hand,
the
max-cut
problem
can
be
solved
in
polynomial
time
for several classes
of
graphs; for instance, for
planar
graphs
(Orlova
and
Dorfman
[1972], Hadlock [1975]), more generally for
graphs
with
no
K5-minor
(Barahona
[1983]), also for
graphs
of fixed genus
with
weights
±1
(Barahona
[1981]). (See also Section 27.3.2.)
Next, we look
at
the
complexity of
the
separation
problem
over
the
cut
cone
CUT
n
,
as
this
will
then
enable us
to
derive
the
complexity of
the
£1-
embeddability
problem.
(P3)
The
separation
problem
for
the
cut
cone.
Instance:
A
rational
distance d
on
V
n
.
4.4 Complexity Questions
49
Question: Does d belong to the cut cone CUTn ?
If
not, find a E
<qE"
such
that
aT
d > 0
and
a
T
6(S)
:$
0 for all S
~
V
n
.
Complexity:
NP-hard
(Karzanov [1985]).
Proof. Set P
n
:=
CUTn
n
{x
I
LijEE"
Xij
:$
I}.
We
first show
that
the problem
(PI)
can
be
polynomially reduced to an optimization problem over P
n
. For this,
let
W E
z!n
and K E
Z+
be
given. For s
i=
t E V
n
,
define a new weight function
w
st
E
ZEn
by
{
-Wij
wi}
:=
-Wij
+ M
-Wij
+ K - 1
M(n
2)
ifi,j
E
Vn
\ {s,t},
ifi
E
{s,t},j
E
Vn
\ {s,t},
if
ij
st,
for
ij
E
En,
where M
:=
LijEEn
Wij.
Note
that
(wst)T 6(S)
-w
T
6(
S) + K 1
if 6(S)st = 1 and
that
(wst)T 6(S)
2':
0 if 6(S)st =
O.
Hence, if 6(S)st 1,
then
w
T
6(S)
::::
K if and only if (w
st
?6(S)
<
O.
Therefore, in order to solve
(PI),
it
suffices
to
solve the problem:
min
(w
st
? x
s.t. x E P
n
for each of the
(~)
pairs
st
E
En
and to verify whether the minimum is negative.
As
(PI)
is
NP-complete,
we
obtain
that
the optimization problem over P
n
is
NP-hard. Using results from Grotschel, Lovasz
and
Schrijver
[1988]
(namely,
the polynomial equivalence between optimization
and
separation problems over
polyhedra),
we
deduce
that
the separation problem for P
n
is
NP-hard. As the
separation problem over
P
n
is
clearly equivalent to the separation problem over
CUT
n
,
we
obtain
that
(P3)
is
NP-hard. I
(PS)
The
C1-embeddability
problem.
Instance: A rational distance d on V
n
•
Question: Does d belong
to
the
cut
cone CUTn (i.e., is d C1-embeddable) ?
Complexity:
NP-complete (Avis
and
Deza [1991]).
Proof.
We
first check
that
(P5) is in NP. Indeed, if d E
CUT
n
,
then
dean
be decomposed as d
ai6(Si)
for some nonnegative scalars
a/s,
where
m
:$
(~)
(by Caratheodory's theorem). Thus, the polyhedron
{a
E
lR+
I d =
L~l
ai
6
(Si)}
is
nonempty. Therefore,
it
contains a rational vector a whose size
is
polynomially bounded by n and
the
size of d (use Theorem
10.1
in
Schrijver
[1986]). Hence, this
a provides a certificate
that
can
be checked in time poly-
nomial in
the
size of
d.
This shows
that
(P5) is
in
NP.
We
can now conclude
that
(P5) is NP-complete, since the separation problem (P3) is NP-hard. In-
deed, consider again
the
polytope P
n
CUTn n
{x
I
LijEEn
Xij
:$
I}
instead
of
CUT
n
•
As P
n
is a full-dimensional bounded polytope for which
we
know an
interior point (e.g.,
(~)+11n)'
it
follows from general results in Grotschel, Lovasz
and
Schrijver
11988]
that
the separation problem for P
n
reduces polynomially
to
50
Chapter
4.
The
Cut
Cone
and
R
1
-Metrics
the
membership
problem
for P
n
(use, in
particular,
(4.3.11)
and
Theorems
6.3.2
and
6.4.9 there). I
(P6)
The
hypercube
embeddability
problem.
Instance:
An
integer distance d on V
n
.
Question: Is d
hypercube
embeddable?
Complexity:
NP-hard;
NP-complete when d is a
distance
on
Vn
having a
point
at
distance
3 from all
other
points
and
all
other
distances belong to
{O,
2,
4,
6}
(Chvatal
[1980]; see
Theorem
24.1.8).
Many
other
problems related
to
cut
semimetrics are
hard
problems.
This
is
the
case, for instance, for
the
problem of
computing
the
minimum
R
1
-size SRI
(d)
for
an
R
1
-embeddable
distance
d,
or
that
of
computing
the
minimum
h-size sh(d)
for a
hypercube
embeddable
distance. As
an
example, consider
the
equidistant
metric
d = 2tlt2+t+1 (on t
2
+ t + 1 points).
Then,
computing
the
minimum
h-size
of
d would yield
an
answer
to
the
question of existence
of
finite projective
planes. Indeed,
it
can
be
shown
that
sh(d)
::::
t
2
+ t +
1,
with
equality if
and
only if
there
exists a projective plane of order t (see Section 23.3).
In
the
same
vein,
computing
the
minimum
scale of
dE
CUTn
is also
hard.
If
d
n
denotes
the
distance
on
Vn
that
takes value 1 for every
pair
except value 2 for a single pair,
then
7/(d
n
)
=
2min(t
14t
::::
sh(2tl
n
))
(see (7.4.5)). Hence,
we
meet again
the
question of
computing
the
minimum
h-
size of
the
equidistant
metric. More details
about
these examples
can
be
found
in
Section 7.4.
Finding
a complete linear description of
the
cut
cone
CUT
n (or of
the
cut
polytope
CUT~)
is
also a
hard
task.
Due
to
the
NP-completeness of
the
max-cut
problem,
it follows from a result of
Karp
and
Papadimitriou
[1982]
that
there
exists no polynomially concise linear description of
CUTn
(or
CUT~)
unless
NP
= co-NP.
Hence,
many
questions
about
the
cut
polyhedra
turn
out
to
be
hard.
Never-
theless,
we
will present
in
this
book
a
number
of results dealing
with
instances
where these questions become tractable. For instance, even
though
the
hyper-
cube
embeddability
problem
is
NP-hard
for general distances, it
can
be solved
in
polynomial
time
for some classes of metrics; several such classes are described in
Chapter
24. A complete linear description
of
the
cut
cone
CUTn
is
not
known
for general
n; yet, large classes of valid inequalities
and
facets are known (yield-
ing a complete description for
n
:S
7); see
Part
V. Moreover, for some classes
of metrics,
the
known classes
of
inequalities already suffice for characterizing R
1-
embeddability; see
Remark
6.3.5. For some restricted instances
of
weight func-
tions,
the
max-cut
problem
becomes polynomial-time solvable as
noted
above.
We will also
mention
several classes of valid inequalities for
the
cut
cone for which
the
separation
problem
can
be solved in polynomial
time
(e.g.,
in
Section 29.5);
hence, these systems
of
inequalities define
tractable
linear relaxations
of
the
cut
polytope
that
could
be
used for
approximating
the
max-cut
problem.
4.5
An
Application to Statistical Physics
51
4.5
An
Application
to
Statistical
Physics
We describe here
an
application of
the
max-cut problem
to
a problem arising
in
statistical
physics; namely,
the
problem of determining
ground
states
of
spin
glasses.
We
start
with
reformulating
the
max-cut problem (4.1.4) as
the
following
quadratic
±l-optimization
problem:
max
~
2::1~i<j~n
wij(l
-
XiXj)
s.t. x E
{±l}n.
( 4.5.1)
(Indeed,
setting
S
:=
{i
E
[l,nj
I
Xi
=
I}
for x E
{±l}n,
the
weight function
does
compute
the
weight w
T
8(S) of
the
corresponding cut.)
The
applied problem
that
we
discuss below will be
of
the form (4.5.1).
A
central
topic in physics
is
the
investigation
of
properties
of
spin glasses. A
number
of
theories have been developed over
the
years in order
to
model spin
glasses
and
try
to
explain
their
behaviour. One
of
the
most commonly used
models
is
the
Ising model
both
for its simplicity
and
its accuracy
in
representing
real world situations. Some aspects
in
this model yield to optimization problems
of
the
form (4.5.1) as
we
see below
4
.
A
spin
glass
is
an
alloy
of
magnetic impurities diluted
in
a nonmagnetic metal.
Alloys
that
show spin glass behaviour are, for instance, CuMn,
the
metallic
crystal
AuFe,
or
the
insulator EuSrS. At very low
temperature
the
spin glass
system
attains
a
minimum
energy configuration, referred
to
as a
ground
state.
This
state
can
be found by minimizing
the
hamiltonian
representing
the
total
energy
of
the
system;
this
problem
turns
out
to
be a max-cut problem in a
certain
graph.
Let us assume
that
the
given spin glass system consists
of
n magnetic impu-
rities (atoms). Each magnetic
atom
i has a magnetic orientation (spin) which,
in
the
Ising model,
is
represented by a variable
Si
E
{±1}
(meaning magnetic
north
pole
'up'
or 'down'). Between any
pair
i,j
of
atoms
there
is
an
interaction
Jij,
which
depends
on
the
nonmagnetic material
and
the
distance
Tij
between
the
atoms.
The
orientation
of
the
exterior magnetic fiel is represented by
So
E
{±1}
and
its
strength
by a constant
h.
Then
the
energy
of
the
system
is
given by
the
hamiltonian:
n
H
.-
- L
JijSiSj
- h L SOSi·
1~i<j~n
i=1
Finding
a
state
of
minimum
energy is the problem:
min
-
2::1~i<j~n
JijSiSj
- h
2::7=1
SOSn
s.t. S E
{±l}n+l,
'The
reader
may
consult
Barahona,
Grotschel,
Jiinger
and
Reinelt
[1988],
or
Godsil,
Grotschel
and
Welsh
[19951
for
more
details
on
this
topic
and
Mezard,
Parisi
and
Virasoro
[19871
for
an
introduction
to
the
general
theory
of
spin
glasses.