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

478

Chapter

29.

Clique-Web Inequalities

hence, F is

not

a Jacet

oj

CUT

n

.

ProoJ. Let 6(8) be a nonzero root

of

CW~(b)T

x

~

O.

We

can

suppose without

loss

of

generality

that

n

I/:

8;

then, b(8) E {I,

2,

...

,r

+ I}

by

Proposition 29.3.8.

Then,

the

set

{I,

2}

is not contained in 8 (else, b(8)

2:

b

i

+b

2

+

L~~+1

b

i

2:

T+2).

This

implies

that

6(8) is also a root

of

the

triangle inequality: XI2-Xln

-X2n

~

O.

I

The

inequality from Proposition 29.4.1 is best possible. For instance,

the

in-

equalities:

CW~(n

- 5,

2,

I,

1,

-1,

...

,

_1)T

x

~

0,

CW~(bl,n

2 -

bb

2,

-1,

...

,

-If

x::; 0

(where 2

::;

bi

::;

n -

4)

are facet defining; equality b

i

+

b2

- b

n

=

Lisispb;

- T

holds for

both

of

them

(with T = 1).

We

now present several classes of clique-web facets.

When

considering a

clique-web inequality

CW~(bf

x::; 0,

we

shall always assume

that

b is

an

integer

vector such

that

L~==I

bi

=

2T

+

1,

even if

this

condition is not

stated

explicitly.

Theorem

29.4.2.

(i)

(CW~)T

x

::;

0, i.e., the

pUTe

clique-web inequality (29.1.3), defines a Jacet

oj

CUTn

JOT

any T

2:

O.

(ii)

CW~(T,

...

,T,

-1,

...

,

_1)T

X

~

0 is Jacet inducing

JOT

all T

2:

1, p

2:

5.

(iii)

CW~

(2,

1,

...

,1,

-1,

...

,

_1)T

x

~

0 is Jacet inducing

JOT

all T

2:

1,

p

2:

2T

+ 3.

(iv)

CW~(r+2,T+

l,r+

1,-1,

...

,

-1)Tx::;

0 is Jacet inducing Jor all r

2:

1.

(v)

CW~(r

+

I,

r + 1, r, r,

-1,

...

,

_1)T

x

~

0 is Jacet inducing Jor all r

2:

1.

I

Theorem 29.4.2 (i)-(iii) is given in Deza

and

Laurent

[1992b]

and

(iv)-(v) in

Deza

and

Laurent

[1992c].

We

shall prove only the assertion (i).

The

proofs

for

(ii)-( v) are, indeed, along

the

same lines and with somewhat lengthy details.

In

order

not

to

interrupt

the

text,

we

delay

the

proof of Theorem 29.4.2 (i) till

Section 29.6.

Further

classes of clique-web facets can be obtained by applying

the

lifting

result from Theorem 29.4.3 below.

This

result follows as a direct application of

Theorem 26.4.4, after noting

that

the

two weighted antiwebs AW;(b

J

,

b2,

•..

, b

p

)

and

AW;(bi,b2,

...

,b

p

)

coincide if

bl,bi

2:

r.

The

class

of

facets from Theo-

rem 29.4.4 is given in Deza

and

Laurent [1992c].

Theorem

29.4.3.

Let

r

2:

1,

b

I

,

...

, b

p

> 0 >

bp+I,''''

b

n

with

Li'==1

bi

=

2r+

L

Suppose that,

JOT

some distinct

j,

k E {p + 1,

...

,

n},

bj =

b",

:=

d < 0 and that,

Jor

some

i E

{I,

...

,

n}

\ {j,

k},

either b

i

::;

d

OT

b

i

2:

r.

IJ the inequality:

CW~(bl,

...

, bn)T x::; 0

29.4 Facets

479

defines a Jacet

oj

CUT

n

,

then the inequality:

defines a Jacet

oj

CUT

n

+1'

I

Theorem

29.4.4.

Given integers p

;:::

3,

r

;:::

1,

b

I

,

...

,b

p

;:::

r, the Jollowing

assertions are equivalent.

(i)

CW~(bI"'"

b

p

,

-1,

...

,

_l)T

x::; ° is Jacet inducing.

(ii) p

;:::

5,

or

p 4 and b},

~

;:::

r + 1 (up to a cyclic

shift

on

[1,4]),

or

p = 3

and

bI

;:::

r +

2,~,

b3

;:::

r + 1 (up to a cyclic shift on [1,3]).

ProoJ.

The

implication (ti)

~

(i) is proved by iteratively using

the

lifting re-

sult

from Theorem 29.4.3 starting from

the

known facets from Theorem 29.4.2

(ii),(iv),(v). We now check the implication (i)

~

(ii). Suppose

that

the

in-

equality

CW~(b},

...

, b

p

,

-1

...

,

-1)T

X

::;

° is facet inducing with p = 3 or

4.

Consider first the case p =

3.

We

can suppose, for instance,

that

b

I

;:::

b

2

;:::

b3

(up to a cyclic shift on [1,3]). From Proposition 29.4.1 below,

we

must have

that

b3

;:::

r + 1. Suppose, for contradiction,

that

b

I

= r +

1;

so, b

I

= ~ = b

3

= r +

l.

Then,

every root

of

CW~(r

+

1,

r +

1,

r +

1,

-1,

...

,

_1)T

x

::;

°

is

a root

of

CW~(I,

1,

-1,

-1,0,

...

,

O)T

X

::;

0,

contradicting the fact

that

the

former in-

equality

is

facet defining. This shows

that

b

I

;:::

r +

2.

Consider now

the

case p

4.

One can check

that

the roots

ofthe

inequality

CW~(x,

r, r, r,

-1,

...

,_I)T

x::;

° (where x

;:::

r)

and of the inequality

CW~

(x, r, y, r,

-1,

...

,

_I)T

x

::;

° (where

x,y

;:::

r + 1) are also roots

of

the inequality

CW~(I,O,

1,0,

-1,0,

...

,O)T

x::;

OJ

hence, these two inequalities are not facet inducing. Therefore, up

to

a cyclic

shift on [1,4J,

we

must have

that

b

I

,

~

;:::

r + 1. I

The

following two further examples of lifting theorems for clique-web facets

can be found in Deza and Laurent

[1992cJ.

Theorem

29.4.5.

Given integers

bI,~,

...

,bp;:::

r;:::

1,

b

p

+1,

...

,b

n

< 0, we

assume

that (i) and (ii) hold.

(i)

CW~(b},

...

, bn)T x::; ° is Jacet inducing Jor

CUT

n

•

(ii) There exist n subsets T},

...

, Tn

oj

{I,

...

,n}

such that (iia)-(iic) hold:

(iia) T

j

n {I,

...

,p}

is an interval

oj

{I,

...

,p}

Jor

alII::;

j::;

n,

(lib)

b(Tj)

= r + 2 Jor

aliI::;

j

::;

n,

(tic) the incidence vectors

oj

the sets T

I

,

•..

, Tn

are

linearly independent.

Then,

CW~+HbI,

...

,bn,-2)TX::;

° defines a Jacet

oJCUT

n

+

I

.

I

Theorem

29.4.6.

Given integers b

I

,

...

, b

p

;:::

r

;:::

s

;:::

0, p

;:::

5, the inequality:

...

,

-1,

-2,

...

,

-2f

x::;

°

480

Chapter

29.

Clique-Web Inequalities

defines a facet

of

CUT

n

.

(Here, there

are

ponents equal to

-2,

with q n p and

- s components equal to

-1,

s com-

b;

-

(q

s)

2r + 1.) I

The

proof

of

Theorem 29.4.6 is based on

iterated

applications of

the

lifting pro-

cedure from

Theorem

29.4.5

starting

from

the

known clique-web facet

CW

T

(bl,

...

,b

p

,-I,

...

,

::;

O.

The

next result follows by applying Theo-

rem

26.'1.3.

Theorem

29.4.7.

Given integers b

i

,

...

, b

p

> 0 >

bp+l,""

b

n

with p

2:

3,

suppose that there exist two indices

i,j

E

{I,

...

,p}

such that

bj

= b

i

-

1 and

j i +

l(mod

p), e.g., i

l,j

2, for simplicity

in

the notation.

If

the two

inequalities:

are facet inducing for

CUT

n

,

then the inequality:

i,s

facet inducing for

CUTn+l'

I

This

is

about

all

the

information

we

have

about

clique-web facets. Probably,

some

other

classes of clique-web facets can be obtained by further applications

of

our

various lifting theorems. However,

it

would be interesting

to

have some

new

proof

techniques for constructing new classes of clique-web facets.

\Ve

con-

clude

this

section with a

few

more remarks.

The

class

of

clique-web faces from

Proposition

29.4.8 below is described in De Simone, Deza

and

Laurent [1994].

Proposition

29.4.8.

The inequality

CW;(n

-

6,2,2,1,1,

-1,

...

,

defines a face

of

CUTn

of

dimension

G)

- (n

4)

for all n

2:

8.

o

I

Consider

the

clique-web inequality

CW~(n-4,

r+

1,

r+

I,

-1,

...

,

::;

0.

It

is facet inducing for

(r

0, n

2:

3)

and

for

(r

2:

1,

n

2:

r + 6).

Its

number

of

roots

is equal

to

(;~;)

+ 2n

4.

Therefore,

it

is

a simplex facet only for

(r = 0, n

2:

3)

and

(r

2:

1, n = r + 6); actually, for r 0,

it

is

the

only class of

simplex hypermetric facets

that

we

know. Note also

that

the

number

of roots

is

in

O(nT), i.e., polynomial in n of

arbitrary

degree r.

Observe

that

the

three

clique-web facets defined by

the

inequalities:

CW;'(n

-

4,2,2,

...

;

::;

0,

CW;'(n

5,2,1,1,

...

,-I)T

X

::;O,

CW;'(n

6,1,1,1,1,-1,

...

, ::;0

(for

n

2:

7)

all have

the

same

number

of

roots, namely,

(n;-2)

+ 2n -

4.

Therefore,

these

three

facets are simplex facets for n = 7 (recall

that

they

are precisely

the

nonhypermetric clique-web facets

of

CUT

7

).

29.5

Separation

481

Finally, let us

mention

a generalization of

the

clique-web inequalities for

the

multicut

polytope. Let

rand

b =

(b

1

,

•••

, b

n

)

be integers such

that

(J

.-

L~=l

b

i

::::

2r + 1

and

b

1

,

...

, b

p

> 0 > b

p

+1,

.

..

,b

n

.

Then,

the

inequality:

(29.4.9)

is

valid for

the

multicut

polytope

MC~.

It

defines a facet

of

MC~

for several

classes of

parameters

b;

this

is

the

case, for instance, if

Ibil

= 1 for

alII

~

i

~

n.

We refer to Deza, Grotschel

and

Laurent

[1992]

for a detailed exposition.

29.5

Separation

of

Clique-Web

Inequalities

We address here

the

separation

problem for clique-web inequalities.

It

is

not

known how

to

separate

the

whole class,

but

a polynomial

algorithm

is

known for

separating

a

small

subclass.

Recall (see Definition 29.1.2)

that

the

pure

clique-web inequality

(CW~f

x

~

o is specified by two

parameters

which

can

be

nand

r or, equivalently, q

and

r,

with

n being

then

given by n = 2q + 2r +

1.

Gerards

[1985]

shows

that

the

subclass consisting

of

the

pure

clique-web inequalities

with

q = 2

can

be

separated

in

polynomial

time. Note

that

these inequalities

can

be

rewritten

as

(29.5.1)

Xuv

+ L

Xij

- L

(Xiu

+

Xiv)

~

0,

ijEE(C)

iEV(C)

where C

is

an

odd

circuit

and

u,

v are two nodes

that

do

not

belong to

C.

More precisely, given

an

integer

N,

let

S~)

denote

the

system

consisting

of

the

inequalities (29.5.1) (for C

odd

circuit

with

V(C)

~

VN

=

{I,

...

,

N}

and

u,v

E

VN

\

V(C))

and

the

triangle inequalities:

Xij

-

Xik

-

Xjk

~

0 (for

i,j,

k E VN).

The

separation

problem for

the

system

S~)

is

the

following:

Given a vector x E

jRN,

decide whether x satisfies all the inequalities

from the

system

S~).

If

not, find an inequality

in

S~)

which is

violated by

x.

This

problem

can

be solved

in

polynomial

time

(Gerards [1985]).

Proof.

Pick

two

distinct

elements

u,v

E VN. For

i,j

E

VN

\

{u,v},

set

(29.5.2)

If

C

is

a circuit

with

V(

C)

~

VN

\

{u,

v},

then

L

Yij

= - L

Xij

+ L

(Xiu

+

Xiv).

ijEE(C)

iEV(C)

482

Chapter

29. Clique-Web Inequalities

Hence,

x satisfies the inequality (29.5.1) if

and

only if

EijEE(C)

YiJ"

~

x"v

holds.

So, one can solve the separation problem over

S~)

in the following

way.

First,

check whether x satisfies all

the

triangle inequalities.

If

not, then a violated

triangle inequality has been found. Otherwise, this shows

that

Y is nonnegative.

Then,

one uses

the

polynomial algorithm from Grotschel

and

Pulleyblank [1981]

for finding an

odd

cycle on

VN

\ {u, v} of minimum weight, with respect to

the

weights Y (such a cycle will be, in fact, a circuit). Then, one verifies whether this

minimum weight

is

greater

than

or equal to the constant

X"v'

If

not,

then

one

has

found a violated inequality. This computation

is

repeated for every choice

ofu,v

E VN· I

In

the

same

way,

the class of bicycle

odd

wheel inequalities:

X"v

+ L

Xij

+ L

(x;"

+

Xiv)

$

2jV(O)1

ijEE(C)

iEV(C)

(where 0 is an

odd

circuit

and

u,v

E V

N

\

V(O» together

with

the triangle

inequalities:

X;j

+

Xik

+

Xjk

$ 2

(i,j,k

E VN)

can

be separated in polynomial

time. (The

proof

is identical;

it

suffices

to

replace (29.5.2) by

Yij

2

Xij

~(Xiu

+

Xiv

+

Xj"

+

Xjv).)

The

web Wro

More generally, given

an

integer q

~

2,

let

S~)

denote the system consisting

of

the

homogeneous triangle inequalities

and

of

the inequalities:

L

Xij

+ L

Xij

- L

Xij

$ 0,

ijEE(W)

ijEE(KQ)

iEV(W),jEQ

where W is a web

W~+2r+l

on

VN

and

KQ

is

a complete graph on Q

~

VN

\

yeW)

with

IQI

=

q.

In

order to separate the system

S~),

we

can

proceed in the same

way as

in

the case q = 2 treated above. Namely, let Q

be

a subset of cardinality

q

of

VN and, for

i,j

E VN \

Q,

set

Yij

29.6

An

Example

of

Proof

483

Then,

y is nonnegative whenever x satisfies all

the

triangle

inequalities.

If

W is

a web

on

q +

2r

+ 1 nodes

of

VN

\ Q

with

parameter

r,

then

L Yij = - L Xij + L Xiu'

ijEE(W) ijEE(W) iEV(W),uEQ

Hence,

if

we

can

compute

in

polynomial

time

the

minimum

weight web

(with

respect

to

the

weights

y)

on

q +

2r

+ 1 nodes

with

parameter

r,

then

we

can

solve

the

separation

problem

over

S~)

in

polynomial

time.

Unfortunately,

nothing

is

known

about

the

minimum

weight web

problem

if

q

=I-

2. For instance, for

q = 3,

the

web W

2rH

is

the

circular

graph

on

2r

+ 4 nodes where each

node

i

is

adjacent

to

nodes

r + 1 +

i,

r + 2 + i

and

r + 3 + i,

and

we

have

the

problem

of

finding

such

a

graph

structure

of

minimum

weight. We show below

the

web

WYo·

29.6

An

Example

of

Proof

for

Clique-Web

Facets

We give here

the

proof

of

Theorem

29.4.2 (i), i.e.,

we

show

that

the

pure

clique-

web

inequality

(CW~)T

x S 0 is facet

inducing

for

CUT

n

,

if

r

::?:

1.

(The

case

r = 0 was already

treated;

see, e.g.,

the

observation after Corollary 26.6.2 for

a proof.) We use

the

following two

lemmas

taken, respectively, from

Barahona

and

Mahjoub

[1986]

and

Barahona,

Griitschel

and

Mahjoub

[1985].

Lemma

29.6.1.

Let

a E

:IR

En

, i

=I-

j E {I,

...

,

n},

S

~

{I,

...

,

n}

\

{i,j}

such

that

the

cut

vectors

8(S),

8(SU{i}),

8(SU{j}),

8(SU{i,j})

satisfy

the equality

aT

x =

O.

Then,

aij

= 0 holds. I

Lemma

29.6.2.

Let

a E

:IR

En

,

I,

J,

Hand

S

be

disjoint

subsets

of

{I,

...

,

n}

such

that

the

cut

vectors

8(S

U

J),

8(S

U

H),

8(S

U I U

J),

8(S

U I U

H)

satisfy

the

equality

aT

x =

O.

Then,

L aij = L aih

iEI,jEJ iEI,hEH

holds.

In

particular,

if

1=

{i},J

=

{j},H

=

{h},

then

aij = aih holds. I

In

order

to

prove

that

(CW~)T

x S 0 is facet

inducing

for

CUT

n

, we consider

a valid

inequality

aT x S 0 for

CUT

n

such

that

a(

8(S))

= 0 for all

roots

8(S)

of

(CW~)T

x S

O.

We show

the

existence

of

a scalar a such

that

aT

x =

a(CW~)T

x.

For

this,

it

suffices

to

prove

the

following

statements:

(a) aij = 0 for all

ij

E

AW;.

(b) aij = a for all

ij

E Kp \

AW;.

(c) ai'j' = a for all

i'j'

E K

q

•

(d) aij' = a for all i E

{I,

...

,p},

j'

E [l',q'].

484

Chapter

29.

Clique-Web Inequalities

We

have chosen to denote the n nodes on which

CW~

is defined by [l,n] =

[l,p] U [1',

q']

(q

= n - pl.

We

prove the statements (a)-(d) through the following

Claims 29.6.3-29.6.8.

We

use the description

of

the roots

of

(CW~)T

x::;

0 given

in

Proposition 29.3.3.

Claim

29.6.3.

Assertion

(a)

holds,

aij

0

for

ij

E AW;.

Proof. Let

7L

be

an

integer such

that

2

::;

7L

::;

r + 1

and

set 8

:=

[2,7L

-

1];

so,

8 = 0 for

7L

=

2.

The

sets

8,8

U {I}, 8 U {u} and 8 U {I,

7L}

define roots (of type

1)

of

(CW~)T

x

::;

0 and, hence,

of

aTx

::;

O.

Therefore, Lemma 29.6.1 implies

that

al.., = 0

and

the general result follows by symmetry. I

Claim

29.6.4.

For

some

scalar 'I, aij'

'I

for

all i E

{I,

...

,p},

j'

E

[l',q'j.

Proof. Take two distinct nodes

i',j'

in

[l',q']

and

set

8:=

[2,r +

2].

Then,

the

sets

8u

{i'}, 8 u

{j'},

8 U {I,

ill,

8 U

{1,j'}

all define roots (of type 2). Therefore,

Lemma

29.6.2 implies

that

alii =

alj',

i.e.,

alii

=

...

=

al

q

'

=:

'11,

for some

scalar

'11.

Similarly,

ail'

...

=

aiq'

=:

'Ii, for some scalar 'Ii, for all i. Let i

be

an

integer such

that

r+2

::;

i

::;

p-r,

and set T

:=

[2,

i

-1]

U[2', (i

-r

-1)']

(with

T

[2,r+I]

ifi

r+2).

ThesetsTU{I},TU{i},TU{l,l'}

andTU{i,I'}

all define roots. Therefore, Lemma 29.6.2 implies

that

all

'

=

ail',

i.e.,

'11

'Ii.

So,

'11

'11'+2

'11'+3

...

=

'1p-1';

similarly,

'12

=

'11'+3

=

...

=

'1p-r+l

and,

therefore,

'11

'12.

By symmetry, 'II =

'12

=

...

=

'1p

=:

'I. I

Claim

29.6.5.

For

some

scalar

a,

ai'j' = a for

aliI'

::;

i'

<

j'

::;

q'.

Proof.

Take distinct nodes

i',j',

h'

in

[I',

q']

and

set 8

:=

[1,

r+2].

Then, the sets

8 U {j'}, 8 U

{h'},

8 U {if,

j'}

and

8 U {i

'

h'}

all define roots. Hence,

we

deduce

from Lemma 29.6.2

that

ai')'

=

ai'

hi

, henceforth stating the result. I

F'rom the fact

that

8(

{i})

is

a root for

aliI::;

i

::;

p,

we

have

that

aT

8(

{i})

O.

Using

the

above claims,

we

deduce

that

E

aij

=

_qAt

l:5j:5p

where

we

set, by convention, aii

:=

O.

Claim

29.6.6.

'I

=

-a.

Proof. Since

the

set

[1,

r+

I]U{I'} defines a root, equality aT 8([1,

r+1]U{I'})

= 0,

together with the above claims, yields:

E

(a1j+a2j+

...

+a

1'

+l,j)+(r+I)(q

1h+(p

r-1h+(q-l)oo=0.

l:5j:5p

Using relations (Sd,

...

, (8

r

+1),

we

deduce from the above identity

that

-q(r+1h+(r+1)(q

lh+(p

r

1h+(q

1)00=0,

29.6

An

Example

of

Proof

485

i.e.,

ry(p

-

2r

-

2)

+

a(q

-

1)

=

O.

Thus,

ry

=

-a

since p = q +

2r

+ 1

and

q

2:

2.

I

Claim

29.6.7.

a1,r+2

=

a.

Proof. Since

the

set

[1,

r +

2]

U {I'} defines a root,

we

deduce

the

relation:

L

(alj

+ ... + a

r

+2,j) - 2a1,r+2 -

a(r

+

2)(q

-

1)

-

a(p

- r -

2)

+

a(q

-

1)

= 0

l";j";p

which, using relations

(Sl),'"

,(Sr+2),

yields:

a1,r+2

=

a.

I

In

order

to

finish

the

proof,

we

must

show

that

condition (b) holds. For this,

it

suffices

to

show, for instance,

that

aij

= a for all 1

::::;

i < j

::::;

(Pil)

such

that

ij

!f-

AW;,

i.e., j

2:

i+r+1.

We prove

the

following

statement

(Hu)

by

induction

on

u r + 2 < u <

(pH):

, - - 2

aij

= a for all 1

::::;

i < j

::::;

u such

that

ij

!f-

AW;.

Assertion

(H

r

+

2

)

holds from

Claim

29.6.7. Take u

2:

r + 3

and

assume

that

(Hi)

holds for i

::::;

u-l;

we

show

that

(Hu)

holds, i.e.,

that

aiu = a for

1::::;

i

::::;

'u-r-l.

Claim

29.6.8.

aiu = a

for

all 1

::::;

i

::::;

u - r -

1.

Proof. Set S

:=

[i

+ 1,

u]

U

[I',

(u

- i - rl'l.

Then,

both

Sand

S U {i} define

roots, yielding:

0=

a(8(S

U {i})) -

a(8(S))

and,

hence,

the

following relation:

0=

L

aij-

L aij = L

aij-2(ai,i+1+'

..

+aiu)-a(q-u+i+r)+a(u-i-r).

jg'SU{i}

jES

l";j";p

Now, ai,i+1 + ... + aiu = ai,i+r+1 + ... + ai,u-1 + aiu =

a(u

- i - r -

1)

+ aiu,

the

latter

equality following from

the

induction

assumption

(Hi)

for i

::::;

u -

1.

Therefore,

the

above relation yields:

0=

qa

-

2a(u

- i - r -

1)

- 2aiu -

a(q

- u + i +

r)

+

a(u

- i -

r),

i.e., aiu =

a.

I

M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,

Chapter

30.

Other

Valid

Inequalities

and

Facets

We describe

in

this

chapter

the

other

main

known classes

of

valid inequalities

defining facets

of

the

cut

polytope.

The

complete linear description

of

the

cut

polytope

CUT~

is known only for n

:::;

7;

it

is presented

in

Section 30.6.

30.1

Suspended-

Tree

Inequalities

As a generalization

of

the

subclass

of

clique-web inequalities

CW;,(b)T

x

:::;

0

(the

case r = 1

of

CW~(b)T

x

:::;

0), Boros

and

Hammer

[1993]

have

introduced

the

following class

of

inequalities (30.1.1).

Let

r

2:

1

and

b =

(b

1

,

.•.

, b

n

) be integers such

that

2:i=l

b

i

= 2r + 1

and

suppose

that

b

2

,

...

, b

p

> 0 >

bp+b""

b

n

for some 2

:::;

P

:::;

n -

1.

(Note

that

the

sign

of

b

1

is

free.) Let T

be

a spanning tree on

the

p - 1 nodes

of

the

set

{2,

...

,p}

and,

for each node i E {2,

...

,p}, let d

i

denote

the

degree

of

node i

in

T. Consider

the

inequality:

(30.1.1)

'"

r(r

+ 1)

(~

"')

~

bibjXij

- 2

~(2

-

di)Xli

+

~

Xij

:::;

O.

l::;i<j::;n i=2

ijEE(T)

We call it a suspended-tree inequality

and

we

denote it by

ST~(T,

bf

x

:::;

0,

since

the

quantity

p

(30.1.2)

L(2

-

di)Xli

+ L

Xij

i=2

ijEE(T)

is

supported

by a suspended-tree (a tree plus a node joined

to

some nodes

of

the

tree). See below

an

example

of

a tree T

and

of

the

corresponding

quantity

(30.1.2) (weight 1 is indicated by a

plain

edge, weight

-1

by a

dotted

edge

and

no edge

means

weight 0).

488

Chapter

30.

Other

Valid Inequalities

and

Facets

In

the special case when T

is

the

path

(2,

...

,p),

then

d

2

d

p

1 while

di

= 2 for 3

.::;

'i

.::;

p

1.

Hence, the

quantity

(30.1.2) takes

the

form:

I:

Xi,iH

+

Xl

p ,

1:s;i5p-l

i.e., its

support

graph

is a circuit of length p. Therefore,

the

inequality (30.1.1)

coincides

with

the

inequality (29.3.7).

This

implies

that,

if

bl, .

..

,b

p

~

r,

then

ST~

(T,

b?

x

.::;

0 coincides

with

CW~

(b)T x

.::;

0;

otherwise,

ST~

(T, b)T x

.::;

0

is

dominated

by

CW~(b)T

x 0 and, therefore,

it

is

not

facet inducing (recall

the

observations after Proposition 29.3.6).

We

conjecture

that,

for

an

arbitrary

tree

T,

if

bi

< r for some i E {I,

..

. ,p},

then

the

suspended-tree inequality

STn(T,

b)T x

.::;

0

is

not

facet inducing.

We

saw above

that

this

is

indeed the case

if

T

is

a

path.

In

fact, the class

of

suspended-tree inequalities

ST~(T,b)Tx

.::;

0 with

bi

~

r for all positive

b;s

generalizes

the

class of clique-web inequalities

CW~(b?

x.::;

0 with

bi

2:

r for all

positive

b;s.

On

the

other

hand, recall

that

the

class of clique-web inequalities has

been

defined as collapsing of some pure clique-web inequalities.

'vVe

conjecture

the

existence of some large class

'I

of valid inequalities, generalizing

the

(pure)

clique-web inequalities, such

that

the suspended-tree inequality

ST~

(T, b)T x

.::;

0

with

bi

~

r for all positive

b;s

would occur

as

collapsing of some pure

member

of

while

ST~

(T, b)T x

.::;

0

with

b

i

< r for some positive

bi

would

be

dominated

by some

member

of 'I.

Proposition

30.1.3.

The inequality (30.1.1) is valid for

CUT

n

.

Moreover, the

roots

of

(30.1.1) are the cut vectors

6(S)

for which S

<;;;

{2,

...

,n},

b(S)

=

r,r+l

and such that the subgraph

of

T induced

by

S n {2,

...

,p}

is connected.

Proof.

Let S

be

a subset

of

Vn

\ {I}.

It

is easy to check

that

ST~(T,

b?

6(S)

=

b(S)(2r

+ 1 b(S»

r(r

+

l)c(S),

where

c(S)

denotes the

number

of connected components

of

the subgraph of T

induced by S n {2,

...

, p}. Hence,

ST~

(T,

b?

6(S)

.::;

0 if

c(

S)

~

1,

with equality

if

and

only if

c(S)

= 1

and

b(S) =

r,r

+ 1. Moreover,

ST~(T,b)T8(S)

< 0

if

c(S)

0 since, then, S n

{I,

2,

...

,p}

=

0,

implying

that

b(S) <

o.

I

Theorem

30.1.4.

Let r ?

1,

bl,""

b

n

be

integers such that

bi

2r +

I,

b2,""

b

p

~

r,

bp+l

...

= b

n

=

-1

for some p with 3

.::;

p

.::;

11.

-

1.

Let T

be

a spanning tree on

{2,

...

,pl.

Suppose that one

of

the two conditions (i),

Oi)

holds.

(i)

bi

.::;

11.

- P + r + 1 (or, equivalently, b

1

~

r)

and there exist two disjoint

sets

S2

{2,

...

)

p}

such that

b(

SI)

=

I:iES,

b

i

~

r + 1

and

the subgraph

of

T induced by

SI

is connected, for l =

1,2.

(ii) T is

not

a

star

and b(S)

.::;

11.

- P + r + 1

for

every subset S

<;;;

{2,

...

,p}

for which the subgraph

of

T induced by S is a path.

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

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