Deza M.M., Laurent M. Geometry of Cuts and Metrics

28.2 Facets

447

Hypermetric

inequalities are, by definition,

the

inequalities

of

the

form:

Q(bfx

~

0,

where b E

zn

and

the

sum

O"(b)

:=

Ei'=l

bi

of

its

components is equal

to

1.

One

may

wonder

what

happens

if

we

relax

the

condition

on

the

sum

O"(b)

or

if

we

allow a nonzero

right-hand

side.

Can

the

hypermetric

inequality be modified so

as to yield

another

valid

inequality?

This

question can

be

answered positively

in

several ways.

Maybe

we

should

start

with reminding

that

the

inequality Q(b)T x

~

°

in

the

case

O"(b)

= ° is nothing

but

the

negative

type

inequality, which is valid

but

not

facet defining for

CUTn

(recall Corollary 6.1.4).

If

b E

zn

has

an

arbitrary

sum

O"(b)

then

one

can

always

construct

an

in-

equality:

which

is

valid for

CUT~;

it

suffices to define

the

right-hand

side

Va

in

a

suitable

manner.

We have,

then,

the

class

of

gap

inequalities which will be discussed

in

Section 28.4.

On

the

other

hand,

if

O"(b)

::::

2

but,

yet, one wants to

construct

a homogeneous

inequality,

then

one

has

to modify

the

quantity

Q(b)T x

in

order

to preserve

validity. Clique-web inequalities

and

suspended-tree inequalities are inequalities

that

fall into

this

category.

There

is yet

another

way

of

generalizing hypermetric inequalities, which con-

sists

of

asking validity

not

for all

cut

vectors

but

only for a

restricted

subset

of

them.

For instance,

if

we

allow

O"(b)

::::

2

then

the

inequality Q(b)T x

~

° is no

longer valid for all

cut

vectors

but

it

remains valid for all

the

cut

vectors

8(8)

such

that

181

ft

{I,

...

,

O"(b)

- I}.

When

O"(b)

=

2,

the

inequality Q(b)T x

~

°

is

valid

(and,

sometimes, facet defining) for

the

even

cut

cone

ECUT

n

.

Other

such

examples will

be

given in Section 28.5.

28.2

Hypermetric

Facets

There

are several known classes

of

hypermetric

inequalities

that

define facets

of

CUT

n

. Here are some examples

that

can

be

derived from results

presented

later:

• Q3(1, 1,

_1)T

x

~

° (triangle facet),

• Q5(1, 1,

1,

-1,

_1)T

x

~

° (pentagonal facet),

• Q2k+l(I,

...

, 1,

-1,

...

,

-If

x

~

° for k

::::

1 (pure

hypermetric

facet),

• Qn(b

1

,

...

,b

p

,-I,

...

,-I)T

x

~

° for 3

~p

~

n-3,

b1,

...

,b

p

> 0,

•

Qn(2,

2, 2,

-2,

-2,1,1,1,

-1,

_1)T

x

~

0,

• Q15(3, 3,

-3, -3,

-3,

1, 1, 1, 1, 1,

1,

-1, -1,

_1)T

x

~

0,

• Q19(4, 4,

-4,

-4,3,3,

-3, -3,

-3,

1, 1, 1, 1, 1,

1,

-1, -1,

_1)T

x

~

0.

448

Chapter

28. Hypermetric Inequalities

Of

course, by permuting, switching,

and

O-lifting

we

can

produce whole classes

of

hypermetric

facets from these examples. For instance, for all

cut

polytopes

CUT~,

all triangle facets can

be

obtained from

Q(l,

1,

-lfx

s:

0 using these

operations.

In

this section

we

will provide a

number

of sufficient

and/or

necessary condi-

tions for a hypermetric inequality

to

define a facet of

CUT

n

. At present there is

no complete characterization of all hypermetric facets, i.e., of all integer vectors

b = (bl,

...

, b

n

)

with

L:'=l

b;

= 1

and

for which Q(b)T x

s:

0 is facet inducing.

However, a complete characterization

of

the

hypermetric facets

is

known for

the

following classes of

parameters

b =

(b

1

,

.•.

, b

n

):

• b

1

;:::

.•.

;:::

b

p

> 0 > b

p

+

1

;:::

•••

;::: b

n

with

b

n

-lor

with

-1

(see

Theorem

28.2.4)(i.e., all negative

bi'S

except at most one are equal

to

-1),

• b

i

E

{w,-w,I,-l}

for all i E

{l,

...

,n},

for some integer

w;:::

2 (see

Theorem

28.2.9).

There are infinitely

many

hypermetric inequalities. All

of

them

are sup-

porting

and, thus, define nonempty faces

of

CUT

n

.

However, since CUTn is a

polyhedral cone,

it

has

only finitely

many

faces, i.e., there are some faces

that

are

induced by infinitely many different hypermetric inequalities. Moreover, since

CUTn is full-dimensional, each of

its

facets is defined by

an

inequality

that

is

unique

up

to

positive scaling. Because of the condition

b;

1, no hyper-

metric

inequality is a positive multiple of another. Thus, among all

hypennetric

inequalities

Qn

(b)T X

s:

0, there are only finitely many ones

that

define facets

of

the

cut

cone

CUT

n

.

We

recall

the

following stronger result from Section 14.2:

The

hypermetric cone

is

polyhedral, i.e., among the hypermetric inequalities only

a finite

subset

of

them

is

not

redundant.

The

states

a necessary condition for a hypermetric inequality

to

define a facet

of

the

cut

cone.

Proposition

28.2.1.

Let b E

zn

with

Li~l

b

i

= 1. Suppose that b

i

,

bj

are

positive coefficients and that

bk

iii a negative coefficient

of

b.

Set P

:=

{r I b

r

>

O}

\

{i,j}.

If

L b

r

+b

k

< 0

rEP

then the face F

ofCUTn

defined

by

Q(b)T x

s:

0 iii not a facet and F is contained

in the facet defined

by

the triangle inequality:

Xij

-

Xik

-

Xjk

s:

O.

Proof.

Let

8(S) be any

cut

vector.

We

may

assume

that

k

tf.

s.

If

i,j

E

S,

then

b(S);:::

b;

+ bj b

k

+ Lrlbr<O b

r

b;

+ b

j

bk

+ 1 - Lrlbr>O br

bk

b

r

>

1.

Hence,

8(S)

is

not

a

root

of F since b(S)

tf.

{O,

I}. Therefore,

IS

n {i,j}1

s:

1 for

every root

8(S)

of

F.

This

shows

that

every root

of

F is a root

of

the

triangle

inequality:

Xij

-

Xik

Xjk

s:

O.

I

28.2 Facets

449

This

observation yields

that,

if Q(b)T x::; 0 is facet defining,

then

the

sum

of

the two largest coefficients

of

b and the absolute value

of

the

smallest coefficient

cannot

be larger

than

the

sum

of all positive coefficients of

b.

In

fact, using

general polyhedral theory (see Grotschel, Lovasz

and

Schrijver [1988]), one can

prove

that

the

coefficients b

i

cannot be larger

than

2n4. Using the fact

that

b(S) E

{O,

I}

for all roots 6(S) of a hypermetric inequality, one can improve

this

bound

to

n2n2. Let us recall

the

botmd: '

~~In-l)!

if the inequality Q(b)T x::; 0 defines a facet

of

CUTn;

it

was obtained in

Part

II

(see Proposition

14.2..1)

as a byproduct of the interpretation

of

hypermetrics

in

terms

of geometry of numbers. This

latter

bound

is

better

than

n2n2. Note, how-

ever,

that

for all

the

known hypermetric facets, maxl'Si'Sn

Ibil

is only quadratic

in

n (see Example 28.2.6).

The

main tool for constructing hypermetric facets is

the

lifting procedure

described in Section

26.5 and, more precisely,

the

Lifting Lemma 26.5.3. Assume

that

the

inequality:

v

T

x:=

Qn(bl,

...

,bn)T x::; 0

is facet inducing for CUTn and, given an integer c, consider the inequality:

(v'f

x:=

Qn+l(b

1

-

C,b2,.'" bn,c)T x::;

O.

Hence,

the

inequality (v')T x

::;

0

is

obtained from

the

inequality v

T

x

::;

0 by

splitting the node

1 into nodes 1, n +

1.

As

mentioned in Section 26.5, in order

to show

that

(v'f

x

::;

0 is facet inducing for CUTn+l,

it

suffices to verify

that

the

condition (iii) from Lemma 26.5.3 holds. Hence,

it

suffices to exhibit n subsets

Tk

(1

::;

k

::;

n) of

{2,

...

,n,

n + I} containing the element n +

1,

such

that

the

cut

vectors 6(Tk) are roots of

(v'f

x

::;

0 and such

that

the incidence vectors of

the

sets

Tk

are linearly independent.

We

mention below several lifting theorems for hypermetric facets which are

based on this procedure (see Lemma

28.2.3

and

Theorem 28.2.4).

As

an

appli-

cation,

we

can construct several classes of hypermetric facets. First, as a direct

application of Theorem

26.4.3,

we

have the following result.

Proposition

28.2.2.

Let b

1

,

...

,b

n

be

integers with

If

the inequality:

Qn(b

ll

b

1

1,

b3,

.

..

,bn)T x

::;

0

defines a facet

of

CUT

n1

then the inequality:

bi

1 and

b2

b

1

1.

Qn+l(b

1

l,bl

l,ba,

...

,b

n

,l)T

X

::;O

defines a facet

of

CUTn+l'

In

particular,

if

bi

= 2 and

if

the inequality:

450

Chapter

28.

Hypermetric

Inequalities

defines a

facet

of

CUT

n

,

then

the inequality:

defines a

facet

of

CUT

n+2.

I

We use

thereafter

the

notation

[p,

q]

to denote

the

set

of

all integers i

with

p

:::;

i

:::;

q,

where 1

:::;

p

:::;

q are some integers.

Lemma

28.2.3

and

Theorem

28.2.4

below are

due

to Deza [1973a](see also Deza

and

Laurent

[1992a] for full proofs).

Lemma

28.2.3.

Let

bl,

...

, b

n

be

integers with

E?=l

b

i

= 1. Suppose

that

b

2

2:

b

3

2:

...

2:

b

p

> 0

and

b

p

+

1

=

...

= b

n

=

-1

where p

2:

2,

n

2:

4.

Suppose

furthermore

that

Qn(b

1

,

•••

,

bnf

x

:::;

0 is

facet

inducing. Then,

(i)

Qn+l(b

1

+

1,

b

2

,

...

, b

n

,

-If

x:::;

0 is

facet

inducing.

(ii)

Qn+l

(b

1

-

C, b

2

,

...

, b

n

,

cf

x

:::;

0 is

facet

inducing,

for

any

integer

c E

[1,n-p-

b

2].

Proof.

Let

us give

the

proof

of

(ii)

in

order

to

illustrate

the

proof

technique.

Consider

the

n

cut

vectors 6(8), where

the

sets 8

are

as follows:

8 = {i, n +

I}

u

[p

+ 1, p + b

i

+ C -

1]

for 2

:::;

i

:::;

p,

8 = {2, n +

I}

U

[p

+

l,p

+ b

2

+

c]-

{i}

for p + 1

:::;

i

:::;

p + b

2

+ C - 1,

8 = {2, n +

I}

U

[p

+ 1, p + b

2

+ c -

1]

U { i } for p +

b2

+ c

:::;

i

:::;

n,

8 = {2,

3,

n + I} U

[p

+

l,p

+ b

2

+

b3

+

c].

These

n

cut

vectors 8(8) are roots of

Qn+l(b1-c,

b

2

,

•••

, b

n

,

cf

x:::; 0

and

one

can

check

that

the

incidence vectors

of

the

sets 8 are linearly

independent.

Therefore,

by

the

Lifting

Lemma

26.5.3, Qn+l

(b

1

-

C,

b

2

,

•••

,b

n

,

cf

x:::;

0

is

facet inducing.

The

proof

of

(i) is similar

but

with

more technical details, as one

must

distinguish

the

cases

when

b

2

= 1

and

when

b2

2:

2.

I

Theorem

28.2.4.

Let

bl,

...

,b

n

be

nonzero

integers

such

that

E?=l

bi

= 1

and

b

1

2:

b2

2:

...

2:

b

p

> 0 > b

p

+

1

2:

...

2:

b

n

, where p is

some

integer

with

2:::;p:::;n-1.

(i)

If

p =

2,

then

Q(bf

x

:::;

0 defines a facet

if

and

only

if

n = 3

and

b

1

=

b

2

= 1, b

3

=

-1.

(ii)

If

2

=1=

p = n - 1,

then

Q(bf

x

:::;

0 does

not

define a facet.

(iii) Suppose p = n - 2.

(iiia)

If

Q(

b f x

:::;

0 defines a facet,

then

b

1

= 1.

(iiib)

If

b

n

-

1

=

-1,

then

Q(b

f x

:::;

0 defines a

facet

if

and

only

if

b

n

-n

+ 4

and

b

1

=

...

= b

n

-2

= 1.

(iv) Suppose 3:::;

p:::;

n - 3

and

b

n

-

1

=

-1.

Then,

Q(bfx:::;

0 defines a

facet

if

and

only

if

b

1

+ b

2

:::;

n - p - 1 + sign(lb

l

- bpi)·

28.2 Facets

451

Proof.

Let

R denote

the

set

ofroots

of

the

inequality Q(b)T

x:::;

O.

(i) We

suppose

p =

2.

Assume

that

the

inequality Q(b)T x

:::;

0 is facet defining.

We show

that

it

coincides

with

a triangle inequality.

We

may

assume

that

1

f/.

S

and

2 E S for every

root

Ii(S) of

Q(b)T

x

:::;

O.

Set F

:=

{(I,

2), (1, 3), (2, 3)}.

The

set

Rp

of

the

projections

on

F

of

the

roots

in

R consists

of

the

two vectors

(1,0,1)

and

(1,1,0).

Hence,

the

set Rp

has

rank

2 which,

by

Lemma

26.5.2,

implies

that

the

projection

of

Qn(b)T

x:::; 0 on F is zero. Therefore,

Qn(b)T

x

:::;

0

is

the

triangle inequality X12

XI3

- XZ3

:::;

O.

(ii)

If

2

=I

p = n - 1,

then

R consists

of

the

cut

vectors Ii( {i})

with

bi

=

1.

Hence

the

rank

of

R is less

than

or

equal

to

n

1,

implying

that

Q(b)T x

:::;

0 is

not

facet defining.

(iii) Suppose

p = n -

2.

We

can

suppose

that

n

f/.

S for each

root

Ii(S) in

R.

If

b

i

> 1 then, for every

root

Ii(S), n - 1 S whenever 1 E

S.

Set

F:=

{(1,n

-I),(I,n),(n,n

-I)}.

The

set Rp consists

of

the

vectors

(0,0,0),

(0,1,1)

and

(1,0,1).

By

Lemma

26.5.2,

if

Q(b)T x

:::;

0 is facet defining,

then

the

projection

of

Qn(b)T

x

:::;

0 on F is zero, which yields a contradiction.

This

shows (iiia).

If

b

n

-

1

=

-1

then

one shows

that

Q(b)T

x

::;

0 is facet defining

by

applying iteratively

the

lifting procedure from

Lemma

28.2.3 (i),

starting,

e.g.,

from

the

triangle facet

Q3(I,

1,

_l)T

x

:::;

O.

We leave

the

details

of

the

proof

of

(iv)

to

the

reader. I

Corollary

28.2.5.

(i)

All

pure hypermetric inequalities are facet defining.

(U)

Let

b E zn such that

E:=1

bi

= 1.

If

b has at least 3 and at

most

n 3 pos-

itive entries and

if

all negative entries

are

equal to

-1

then the associated

hypermetric inequality

Q(b)T x:::; 0 is facet defining. I

Example

28.2.6.

(Avis

and

Deza [1991]) Given n

;:::

7, set m

:=

L!1f'

J

and

let

b E

zn

be

defined

by

m

m-I

-1

m(2+2m

for i =

1,

...

, n -

2m

- 1,

for

i = n -

2m,

for i = n -

2m

+ 1,

...

, n - 1,

n) + 1 for i = n.

2

Hence,

bi

1

and

Ei=llbil

2m(n - 2m) - 3

;:::

T -

4.

The

hyper-

metric

inequality Q(b)T x

:::;

0 is facet defining as

it

satisfies

the

conditions

of

Theorem

28.2.4 (iv). Therefore,

this

gives

an

example

of

a hypermetric facet

of

CUTn

which is k-gonal

with

k quadratic

in

n.

We

do

not

know examples

yielding larger values for

k. I

We now give a lifting result

permitting

to

identify all

hypermetric

facets

Qn(b)Tx:::; 0 where

bi

E

{w,-w,I,-I}

for 1:::;

i:::;

n, for some integer w

;:::

2.

452

Chapter

28.

Hypermetric Inequalities

Let

0:,

ci,

,8,

(3',

w

be

nonnegative integers such

that

(0:

o:')w +

(3

(3'

= L

'We

want to characterize hypermetric facets

of

the

form

(28.2.7)

Qn(w,

.

..

, w,

-w,

..

. ,

-w,

1,

...

, 1,

-1,

...

,

:s

0,

where there are a coefficients w,

0:'

coefficients

-w,

(3

coefficients 1,

and

(3'

coefficients

-1.

For short,

we

denote

the

above hypermetric inequality by

so, n

= a +

a'

+

(3

+

(3'.

We

first formulate a "double lifting" lemma. Namely,

we

prove

that

under

certain

conditions two coefficients of b can be "doubled"

in

such a way

that,

if

a hypermetric inequality Q(b)T x

:s

0 of

type

(28.2.7)

is

facet defining,

then

the

inequality associated

with

the

new vector also is.

As

an

application, one

can

characterize

the

hypermetric inequalities of type (28.2.7)

that

define facets.

Lemma

28.2.8, Theorem 28.2.9

and

Lemma

28.2.10 below

can

be

found in Deza

and

Laurent

[1992b].

Lemma

28.2.8.

Let

b (w(a),

-w(a

l

),

1

Ul),

-1

Cfl

f

»)

be

an integral vector with

0:,

a'

1,

(3,

(3'

satisfying

(a

a')w

+

(3

-

(3'

= 1. Suppose

that

Qn(b)TX

:s

0 is

facet defining and

that

either,

0:

>

a',

- or, a

0:'

and

(3

:2::

w

holds. Then, for

b'

:=

(w(a+1) ,

_w(a'H),

1 (fl),

-1

(fll»), the inequality

Qn+2(b')T

x

:s

0 is facet defining. I

Theorem

28.2.9.

Let

a,

a',

(3,

(3',

w:2::

2

be

integers satisfying

min(o:,a')

1

and

(0:

o:')w +

(3

-

(3'

= 1.

Set

b

:=

(w(a), _w(al),

l(fl)

,

-l(fll»)

and n

0:

+

0:'

+

(3

+

(3'

.

(i)

If

0:

0:'

(i.e.,

(3/

=

(3

-1),

then Qn(b)T x

:s

0 is facet ind1Lcing

if

and only

if

min«(3,

(3')

:2::

w.

(ii)

If

10:

0:/1

is a nonzero even number, then Qn(b)T x

:s

0

i.~

facet inducing

if

and only

if

min«(3,

,8')

:2::

1 or (min(,8,

,8/)

0 and

10:

0:/1:2::

4).

(iii)

If

la -

0:/1

is an

odd

number, then Qn(b)T x

:s

0 is facet inducing

if

and

only

if

10:

-

0:'1

:2::

3 or

(10:

-

0:/1

= 1 and

min«(3,

(3')

:2::

w).

I

Lemma

28.2.10.

If

the ineq1Lality:

Qn(w(a),

_w(a'),

l(fl)

,

_l(fll»)T

x

:s

0

defines a facet

of

CUT

n, then the inequality:

28.3

Separation

453

defines a facet

of

CUT

n

+2op

for

any

integer

l'

~

1.

I

Remark

28.2.11.

Some facets introduced by

Padberg

[1989]

for

the

correlation

polytope

correspond

(up

to

switching

and

via

the

covariance

mapping)

to

some

subclasses

of

the

hypermetric

facets

obtained

in

Theorem

28.2.4 (iii);

this

is

also

the

case for some classes

of

facets given by

Barahona

and

Mahjoub

[1986]

for

the

cut

polytope

(see Deza

and

Laurent

[1992a] for a precise description

of

the

connection). I

For various reasons, it

is

interesting

to

identify faces

that

are simplexes.

For instance, for

b =

(1,1,-1),

b =

(1,1,-1,0),

and

b =

(1,1,1,-1,-1),

the

inequality

Q(b)T

x

~

0 defines a simplex facet

of

CUT

3

,

CUT

4

,

and

CUT

5

,

respectively.

These

three

examples belong to

the

class

of

inequalities:

Q(n-

4,1,1,

-1,

...

, _1)T X

~

0

(n

~

3). Any such inequality defines a simplex facet

of

CUT

n

,

as

the

next result from Deza

and

Laurent

[1992a] shows.

Corollary

28.2.12.

Let

b =

(b

1

,

b

2

,

1, 1,

-1,

...

-

1)

E

zn

where b

1

,

b

2

are

integers

such

that

b

1

~

b

2

,

b

1

+ b

2

= n - 5

and

assume

that

n

~

6.

(i)

Qn

(b)T X

~

0 is facet

inducing

if

and

only

if

b

1

~

n - 4.

(ii)

The

face defined by Qn(b)T x

~

0

is

a

simplex

if

and

only

if

b

1

~

n - 4.

Proof. (i) follows by applying

Theorem

28.2.4

and

(ii) by checking

that

all

nonzero

roots

are linearly independent. I

28.3

Separation

of

Hypermetric

Inequalities

We consider in

this

section

the

separation

problem for

the

class of

hypermetric

inequalities.

This

problem

can

be formulated as follows:

(PO)

Separation

of

hypermetric

inequalities.

Instance:

An

integral distance d on n points.

Question: Does d satisfy all

hypermetric

inequalities?

If

not, find a

hypermetric

inequality violated by

d.

We do

not

know

what

is

the

exact complexity of

the

problem

(PO). However,

the

complexity of several

is

known.

This

indicates

that

(PO)

is

very likely to be a

hard

problem.

The

complexity results

for

the

problems

(PI),

(P2), (P3) have been established by Avis

and

Grishukhin

[1993].

(P1)

Testing

all

hypermetric

inequalities.

Instance:

An

integral distance d on n points.

Question: Does d satisfy all

hypermetric

inequalities?

Complexity: co-NP.

There

exists

an

algorithm solving

(PI)

whose

running

time

is

in

O(h(n)

(n

4

(log2(n))2 +

2n

3

log2(n)

log2(11

d

1100)))'

where h(n) denotes

the

454

Chapter

28.

Hypermetric

Inequalities

number

of

hypermetric

inequalities

that

define facets

of

the

hypermetric

cone

HYP

n

.

We recall (from

Proposition

14.2.4)

that,

if

Qn(bl

x S 0 defines a facet

of

the

hypermetric

cone

HYP

n

,

then

Hence, a

rough

estimate

of

h(n) is

Proof for

(Pl).

Let d be

an

integral distance

on

n points.

In

order

to

check

that

d satisfies all

hypermetric

inequalities, i.e.,

that

d E

HYP

n,

it

suffices

to

check

whether

Qn(bl

d S 0 holds for all b E

zn

with

sum

1

and

such

that

Ibil

S En for

all

i. Note

that

En can

be

represented by O(n

log2

n) bits. Hence,

computing

Qn(bl

d

can

be done

in

O(h(n)

(n

4

(log2(n))2 +

2n

3

Iog2(n)

log2(11

d

11(0)))

ele-

mentary

operations, which is polynomial in

the

size

of

the

input.

This

shows

that

(PI)

is

in

co-NP

and

the

announced

running

time

for solving

(PI).

I

The

separation

problem

l

for

hypermetric

inequalities is very likely

to

be

a

hard

problem, in view

of

the

complexity

status

of

the

next problems (P2)

and

(P3).

(P2)

Testing

all

(2m

+

I)-gonal

inequalities.

Instance:

An

integral distance d on n

points

and

an

integer

m.

Question: Does d satisfy all

(2m

+ I)-gonal

hypermetric

inequalities?

Complexity: co-NP-complete. Also co-NP-complete

if

one

tests

only

the

pure

(2m

+

I)-gonal

inequalities.

(P3)

Finding

the

smallest

violated

hypermetric

inequality.

Instance:

An

integral distance d

on

n points.

Question: Does d satisfy all

hypermetric

inequalities?

If

not,

find

the

smallest

integer

k

such

that

d violates a

(2k

+ I)-gonal inequality.

Complexity:

NP-hard.

In

what

follows,

we

prove

the

complexity

of

the

problems (P2)

and

(P3). For

this,

we

use

the

known complexity

of

the

next problems.

(P4)

Finding

an

induced

complete

bipartite

subgraph.

Instance: A

graph

G

on

n vertices

and

an

integer m such

that

2m

+ 1 S n.

1 A

heuristic

for

separating

hypermetric

inequalities

is

proposed

in

De

Simone

[1992]'

De

Simone

and

Rinaldi

[19941.

(The

main

idea

is

to

reformulate

the

separation

problem

for

hy-

permetric

inequalities

as

a

max-cut

problem

over

a

larger

complete

graph,

to

which

can

then

be

applied

any

good

heuristic

for

the

max-cut

problem.)

Hypermetric

inequalities

are

reported

there

to

be

effective

from

a

computational

point

of

view

for

solving

max-cut

problems

on

com-

plete

graphs

of

about

20-25

nodes.

28.3 Separation

455

Que.stion: Does G contain the complete bipartite

graph

Km,m+l

as an induced

subgraph?

Complexity: NP-complete (Garey and Johnson [1979]).

(P5)

Finding

the

largest

induced

complete

bipartite

subgraph.

Instance: A graph G on n nodes.

Question:

Find

the largest integer m such

that

G contains K

m

,m+1 as

an

induced

subgraph.

Complexity: NP-hard (Garey

and

Johnson [1979]).

We

show

that

(P4) reduces to (P2)

and

that

(P5) reduces

to

at

most n

z

l

questions

of

type (P3).

We

introduce some notation. Let G =

(V

n

,

E)

be a

graph

and

let t E

lJ4.

We

construct

the

distance dt(G) on

Vn

by setting

Given

bE

zn,

set

d

t

(

G)ij

d

t

(

G)ij

1 if

ij

E

E,

1 + t if

ij

E En \

E.

Let E(G,b) denote the edge set

of

the

subgraph

ofG

induced by V(b)

and

set

where

E(Kv+Cb),V_Cb))

denotes

the

edge set

of

the complete

bipartite

graph

with

node bipartition

(V+(b), V_(b)).

We

state

an

intermediate result.

Lemma

28.3.1.

Let

b E

zn

with

Ib;1

= 2k + 1. Then,

(28.3.2)

1)

_ t

L:

IMil.

ijEE

6

CG,b)

Proof. Suppose first

that

E6.(G,

b)

=

0.

Then,

Q(b)T dt(G) = L

Mj

+

(1

+

t)

( L

bibj

+ L bibj) .

iEV_(b),jEV+Cb)

i,jEV_(b),i<j

i,jEV+(b),i<j

Using the identity:

1 (

)2

L

bib

j

=

-(

L:

b

i

i,jEX,i<j

2

iEX

and

the

fact

that

LiEV+(b)

b

i

:=

k +

1,

LiEV_(b)

bi

=

-k,

we

obtain:

Q(b)T dt(G) =

-k(k

+ 1) +

t;

1 (k

2

+ (k + 1)2 - L (b.)2),

iEV(b)

456

Chapter

28.

Hypermetric

Inequalities

which coincides

with

the

sum

of

the

first

three

terms

of

(28.3.2).

If

E/:;(G,

b)

i=

0,

then

one easily checks

that

one more

term

should be added, which is equal to

-tLijEE"'(G,b)

IMjl· I

Corollary

28.3.3.

Let G = (Vn'

E)

be

a graph and let m

be

an integer such

that n

~

2m

+ 1. Set dm(G)

:=

m

3

d

t

(G), where t

:=

~

+~.

Then,

(i)

dm(G) satisfies all (2k + I)-gonal inequalities, for 1::; k

::;

m - 1.

(ii) dm(G) satisfies all (2m + I)-gonal inequalities except when G contains

Km,m+l

as

an induced 8ubgraph in which case dm(G) violates a pure

(2m+

I)-gonal inequality.

Proof.

Suppose

L~l

Ibil

= 2k + 1

with

k

::;

m -

1.

Then,

by

Lemma

28.3.1,

Q(b)T dt(G)

::;

k

2

t - k

::;

O.

Suppose now

that

k =

m.

By

Lemma

28.3.1,

Q(bf

dt(G)

::;

~

- (t +

1)

2:

Ibil(lb;l-

1)

- t

2:

Ibibjl.

l:<O':<on

ijEE"'(G,b)

If

Ibil

~

2 for some i

or

if

E/:;(G,

b)

i=

0,

then

Q(bf

dt(G)

::;

~-t

<

O.

Otherwise,

b is pure, G contains

an

induced K

m

,m+l

subgraph,

and

Q(b)T dt(G) =

~

>

O.

I

Proof for (P2). Let G

be

a

graph

on

n nodes

and

let m be

an

integer such

that

n

~

2m

+ 1. Consider

the

distance dm(G).

By

Corollary 28.3.3, G contains

an

induced Km,m+l

subgraph

if

and

only if dm(G) violates a (2m +

I)-gonal

inequality (or, equivalently, a pure (2m + I)-gonal inequality).

This

shows

that

(P2) is co-NP complete. I

Proof for (P3). Let G

be

a

graph

on

n nodes. Set k

:=

l n;-l

J.

Let m denote

the

largest integer such

that

G contains

an

induced Km,m+l subgraph. For 8

::;

k,

set

t

:=

~

+

~

and

consider

the

distance ds(G).

If

s >

m,

then

G contains

no

induced

Ks,s+l subgraph. Hence, by Corollary 28.3.3,

the

answer to (P3)

is, either

that

d

s

satisfies all hypermetric inequalities, or

that

d

s

(G) violates a

(2p + I)-gonal inequality for some p >

8.

If

8 =

m,

then

G contains Km,m+l

and

the

answer

to

(P3)

is

that

the

smallest inequality violated by ds(G)

is

(28 + 1)-

gonal. Therefore,

the

answers

of

(P3) applied successively

to

s =

k,

k -

1,

...

,

1,

give us

the

value

of

m.

This

shows

that

(P3)

is

NP-hard.

I

Remark

28.3.4.

In

contrast

with

the

hypermetric

case,

the

separation

problem

for

the

class

of

negative

type

inequalities

can

be solved

in

polynomial time.

An

easy way

to

see

it

is

by using relation (6.1.15), which

states

that

the

negative

type

cone NEGn+l

and

the

positive semidefinite cone

PSD

n

are

in

one-to-one

correspondence

via

the

covariance

mapping~.

In

other

words, let d

be

a

distance

on

n + 1 points. Define

the

n x n

symmetric

matrix

(Pij) by

setting

Pii

:=

d

i

,n+l

fori=I,

...

,n,

Pij

:=

~(di,n+l

+ dj,n+l - dij)

for i

i=

j = 1,

...

, n.

Deza M.M., Laurent M. Geometry of Cuts and Metrics

Подождите немного. Документ загружается.