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

27.2

Rooted

Triangle Inequalities

427

On

the

other

hand,

all

Ca's

have

the

same volume. Indeed,

if

A denotes

the

set

of

positions

in

which

the

coordinates

of

a

and

b differ,

then

Cb

is

the

image

of

C

a

under

the

mapping

f!6(A)

(the analogue of switching, defined

in

(26.3.10)).

This

implies

that

vol C

a

= vol C

b

,

as

the

mapping

f!6(A) is

unimodular

(i.e., its

matrix

has

determinant

±1). Therefore,

We show below

that

n!

n-d

vol

Co

=

-(

),2 .

2n.

This

implies immediately

the

value

of

the

volume

of

Qn- Finally, as

MET~+l

=

~-l(Qn)

and

as

the

determinant

of

the

matrix

of

the

linear

mapping

~-l

is equal

to

2m

(in absolute value),

we

have

o n! n

vol METn+l =

-(

),2

2n.

We now proceed to computing

the

volume

of

Co.

Let

Co

:=

2Co

denote

the

polytope

Co

scaled by a factor

2.

Then, as

the

inequality (ii) becomes

redundant

in

the

description

of

Co,

the

polytope

Co

is defined by

the

inequalities (i)

and

o S Pii S 1 (for all i). Let

(Sn,

-<)

denote

the

partially

ordered set on

Sn

:=

{Pij

11

SiS

j S

n}

with

Pij

-<

Pii

and

Pij

-<

Pjj

as

partial

order.

Then,

Co

is

the

order

polytope

l

of

the

poset

(Sn,

-<).

Let

e(Sn,

-<)

denote

the

number

of

linear extensions

2

of

(Sn,

-<).

Then,

1

C

' _

e(Sn,

-<)

vo

0-

d!

.

Define

an

ordered

extension

to be a linear extension

of

(Sn,

-<)

in

which

Pll,

...

,

Pnn

occur

in

that

order. Hence,

an

ordered extension is a

permutation

of

the

Pij'S

in

which

Pll,

...

,Pnn

appear

in

that

order

and

Pij

appears

at

the right

of

both

Pii

and

Pjj.

Their

number

can

be

computed

as follows. Suppose

that

Pi,k+l

(i S k),

...

,Pin

(i S n -

1)

have already been positioned.

We

now

try

to place

Plk,'"

,Pk-l,k·

The

first element

Plk

should be placed

at

the

right

of

Pkk. As

there

are

already

fk

:=

(n

- k +

1)

+ k + (k +

1)

+ ... +

(n

-

1)

= n - k + 1 +

(;)

-

G)

elements of

Sn

placed

at

the

right of Pkk (including Pkk), there are

fk

possibilities

for chosing

the

position

of

Plk.

Then,

there are

fk

+ 1 possibilities for placing

1

The

order polytope P

of

a

partially

ordered

set

(E,

-<)

is

the

polytope

in

the

space

~E,

which

is

defined

by

the

inequalities:

0

::5

x.

::5

1

(e

E E)

and

x.

::5

x f

whenever

e

-<

f (e,

fEE).

2 A linear extension

of

a

poset

(E,

-<)

is

any

total

order

on

E

extending

the

partial

order

-<.

Stanley

[1986] proves

that

vol P =

'(I~'I~)'

if

e(E,

-<)

is

the

number

of

linear

extensions

of

(E,

-<)

and

P is

the

order

polytope

of

(E,

-<).

428

Chapter

27. Triangle Inequalities

P2k,

up

to

!k

+ k - 2 possibilities for placing

Pk-l,k.

In

total,

the

number

of

ordered

extensions is

which

can

be

easily checked

to

be

equal to

(2~)!2n.

Therefore,

e(Sn,

-<)

=

(~~j!2n,

as

the

number

of

linear

extensions is equal

to

n!

times

the

number

of

ordered

. H I C

f

-

n! 2

n

die

-

2-

d

I C

f

-

n! 2

n

-

d

I

extenSIOns. ence,

vo

a - (2n)!

an

vo a - vo a - (2n)! .

27.2.3

Additional

Notes

Chvatal

Cuts

of

Rooted

Triangle

Inequalities.

Boros,

Crama

and

Hammer

[1992]

show

that

the

Chvatal

closure

ofthe

polytope

~(RMET~+1)

is precisely

the

polytope

~(MET~+1);

we

mention

their

result

(without

proof)

in

Theorem

27.2.3

below. We recall

the

definition for

the

notion

of

Chvatal

closure.

Let

P

be

a

polytope

in

m,k

and

let

PI

denote

the

convex hull of

the

integral

points

of

P;

so,

PI

S;;;

P.

Given a E

7/.,k

and

0'

E

7/."

if

the

inequality

is valid for

P,

then

the

inequality

is valid for

PI.

This

second inequality is called a Chvlital cut

of

P.

Then,

pf

denotes

the

polytope

which is defined

by

all

the

possible

Chvatal

cuts;

it

is called

the

Chvlital closure

of

P.

Setting

pea)

:=

P

and

p(k+1)

=

(p(k))f

for k

2:

0, we

obtain

a decreasing sequence of polytopes:

p(O)

;;?

pel)

;;?

...

;;?

PI.

Chvatal

[1973]

(see, e.g., Schrijver [1986]) showed

that

there

exists a finite

index

k such

that

p(k)

=

PI.

The

smallest such k is called

the

Chvlital rank of

P.

Theorem

27.2.3.

The Chvlital closure

of

the rooted correlation

semimetric

polytope

~(RMET~+l)

is the correlation semimetric polytope

~(MET~+1);

that

is,

(~(RMET~+l))'

=

~(MET~+l)'

I

As

an

example,

we

indicate

how

to

obtain

the

unrooted

correlation

triangle

inequality:

Pn

+

P22

+

P33

-

P12

-

P13

-

P23

::; 1

27.2 Rooted Triangle Inequalities

429

as a

Chvatal

cut. Consider the following rooted correlation triangle inequalities:

Pll

+ P22

PI2

S 1,

PIl

+

P33

PI3

S 1,

P22 +

P33

P23 S 1,

-P12

SO,

-P13

SO,

-P23

SO.

Summing

them

up

and

dividing by

2,

we

obtain:

3

Pll

+ P22 + P33

PI2

PI3

P23 S 2 < 2

which yields

the

Chvatal cut:

Pll

+ P22 + P33

PI2

PI3

P23 S 1.

Similarly,

the

inequality:

-Pll

+

PI2

+

PI3

P23 S 0 arises as Chvatai

cut

from

the

following inequalities:

-PH

+

PI2

S

0,

-Pn

+ PI:! S 0,

-PH

+

PI3

S 0,

-P33

+

PI3

S 0,

P22 +

P33

- P23 S 1,

-P23

SO.

Observe

that

Theorem 27.2.3 does

not

hold on

the

"cut side", i.e.,

the

Chvatal

closure of

the

rooted semimetric polytope

RMET~+l

is

not

equal to

the

semi-

metric polytope

MET~+l'

.For

instance,

the

inequality

is

not

a

Chvatal

cut

of

RMET~+l'

Indeed,

the

inequality

is

not

valid for

R~vlE:T~:-l-

by

Xi,n+l

~

(1

SiS

XI2

+X13 +X23

< 3

as

it

is

violated by

the

point x E

RMET~+l

defined

andxij

l(lSi<jSn).

The

following lower

bound

on

the

Chvatal

rank

of

the

semimetric polytope

was given by Chvatai, Cook

and

Hartman

[1989J.

Theorelll

27.2.4.

The Chvcital rank

of

the

semimetric

polytope

MET~

is greater

than

or equal to

~(n

4). I

The

Roof

Duality

Bound.

Given weights c E

lRV"UE",

consider

the

uncon-

strained

quadratic

0-1

programming problem:

430

Chapter

27. Triangle Inequalities

(27.2.5)

max

Ll~i~j~n

CijX;Xj

s.t. x E

{O,

l}n

max cTp

s.t. pEcoR;;.

As

COR~

~

e(RMET~+1)'

the program

C2

:=

max(c

T

pip

E

e(RMET~+1))

gives

an

upper

bound

for the optimum value C

n

of (27.2.5).

The

bound

C2

is known as the roof duality bound. Several equivalent formulations of

C2

are

given in Hammer, Hansen and Simeone

[1984]. In fact, a sequence of bounds

Ck

(k =

2,

...

,n

-

1)

has been formulated, verifying:

and

having also several equivalent formulations; see Boros, Crama and Hammer

[19901,

also Adams

and

Dearing [1994]. In particular,

C3

is

the optimum value

obtained when optimizing over the polytope

e(MET~+l)'

Hence,

C2

and C

3

can

be

computed in time polynomial in n. More generally,

Ck

can be computed

by solving a linear programming problem whose size

is

polynomial

in

n

but

exponential in k. For more details

we

refer, e.g., to Boros and Hammer [1991],

Boros,

Crama

and Hammer [1992]

and

references therein.

27.3

Projecting

the

Triangle

Inequalities

Let G = (Vn,

E)

be

a graph on n nodes. Let MET(G) denote the projection of

the semi metric cone METn

on

the subspace RE indexed by the edge set

of

G;

MET(G)

is

called the semimetric cone of G. Similarly, let METD(G) denote

the

projection

of

MET~

on

RE; it is called the semimetric polytope of G.

In

the same

way,

CUT(G) (resp. CUTD(G)) denotes the projection

of

CUTn (resp.

CUT~)

on

RE.

By the definitions,

(27.3.1)

CUT(G)

~

MET(G) and CUTD(G)

~

METD(G).

We recall

that,

for 5

~

V

nl

oa(5) denotes the cut in G which

is

the

subset of

E consisting of

the

edges e E E having exactly one endnode in

5.

Hence,

the

cut

cone CUT( G) of G coincides with the cone in RE generated

by

the vectors

Xo

o

(8)

(for 5

~

V

n

) and

the

cut polytope CUTD(G) coincides with the convex

hull of the vectors

X

oo

(8)

(for 5

~

V

n

).

As

the collection of cuts in G

is

closed under the symmetric difference then,

by

the

results

of

Section 26.3, the switching operation applies to

the

cut polytope

CUT

D

(G) of

an

arbitrary graph G; it also applies to

the

semimetric polytope

METD(G). Namely, for any 5

~

V

n

,

Note

that

METD(G) contains no other integral vectors besides

the

incidence

vectors

of

the cuts oa(5)

(5

~

V

n

)

(this follows easily from Proposition 27.2.1).

27.3 Projecting

the

Triangle Inequalities

431

The

graphs G for which METD(G) has only integral vertices, i.e., for which

equality holds

in

(27.3.1), will be characterized

in

Theorem 27.3.6.

In

general,

METD

(G) has lots of nonintegral vertices.

It

is

easy to see

that

no vertex of

METD(G)

can

have denominator

2.

Hence, denominator 3

is

the

next case

after integrality. Laurent and Poljak

[1995a]

stud

y3 the graphs G for which all

the

vertices of METO(G) have denominator:::;

3;

such graphs are completely

characterized

up

to 7 nodes.

27.3.1

The

Semimetric

Polytope

of

a Graph

\Ve

present here a linear description for

the

semimetric cone

MET(

G)

and

poly-

tope

METD (G). As

we

know a linear description of the polytope

MET~,

a linear

description of METD(G)

can

be deduced from

that

of

MET~

by applying, e.g.,

the

Fourier-Motzkin elimination method. This method consists of combining

the

linear inequalities defining

MET~

so

as to eliminate

the

variables Xe

(e

E En \

E)

that

do

not

occur in CUTD(G); see, e.g., Schrijver

[1986],

Ziegler

[1995].

Computing explicitly the projection of a polyhedron is, in general, a difficult

task

as

the

Fourier-Motzkin elimination method becomes very often intractable

in practice. For instance,

the

correlation polytope

4

COR~

can be obtained as

the

projection of a simplex lying

in

the space of dimension 2

n

(namely,

of

the

simplex

COR~(2Vn);

recall Section 5.4). Even though finding

the

facial

structure

of

a

simplex

is

trivial, finding all

the

facets of

CO~

is a

hard

task!

However,

in

the

case of

the

semimetric polyhedra MET(G) and METD(G), explicit descriptions

can

be found fairly easily, as

the

results below indicate.

We

recall

that

a cycle is any

graph

which

can

be decomposed as

the

edge

disjoint union

of

circuits. Let C be a circuit

and

let e be

an

edge

that

does not

belong to C; then, e is said to

be

a chord of C if

it

joins two nodes

of

C.

The

circuit C is said to be

chord

less

if

it

has no chord.

Let C be a cycle in G

and

let F

~

C

be

a subset

of

C such

that

IFI

is odd.

The

inequality:

(27.3.2)

Xe

L

xe:::;

IFI

- 1

eEC\F

is called a cycle inequality. Note

that

the triangle inequalities are special cases

of

cycle inequalities (obtained for

IC!

= 3). Note also

that

the

class of cycle

inequalities is closed under the operation of switching by a cut. (This follows

from

the

fact

that

a cut and a cycle intersect in

an

even number of edges.)

Theorem 27.3.3 below shows

that

the

cycle inequalities form a linear description

of

the

semimetric polyhedra; (i) is proved in Barahona

[1993]

and (ii), (iii) in

Barahona

and

Mahjoub

[1986].

extension

in

the

context

of

binary

matroids

is considered in

Gerards

and

Laurent

[19951.

4Therefore,

up

to

a linear

transformation,

the

cut

polytope

CUT~

can

also

be

obtained

as

the

projection

of

a simplex.

We

will see

in

Example

27.4.4

another

construction

permitting

to

realize

any

cut

polytope

CUTD(G) as projection of a simplex.

432

Chapter

27. Triangle

Inequalities

Theorem

27.3.3.

Let G =

(Vn'

E)

be

a graph.

(i)

MET(G)

=

{x

E

ffi.~

I

Xe

-

x(C\

{e})::; 0 for C cycle

ofG,e

E

C},

METD(G)

=

{x

E

ffi.~

I xe::; 1 for e E

E,

x(F)

-

x(C

\

F)

::;

IFI-1

for C cycle

of

G, F

~

c,

IFI

odd}.

(ii) Let C

be

a cycle in G, e E

C,

and F

~

C with

IFI

odd.

The inequality

Xe

-

x(C

\ {e})

::;

0 (resp.

x(F)

-

x(C

\

F)

::;

IFI-

1)

defines a facet

of

MET

(G) (resp.

METD(G))

if

and only

if

C is a chordless circuit.

(iii) Let e E

E.

The inequality

xe::::

0 (resp. xe::;

1)

defines a facet

of

MET

(G)

(resp.

METD

(G))

if

and only

if

e

does

not belong

to

any triangle

of

G.

Proof. A first observation is

that,

due

to

switching,

it

is sufficient

to

prove

the

statements

relevant

to

the

cone

MET(G).

In

a first

step,

we

show

that,

if

C

is

a

cycle in G which

is

not

a chordless circuit,

then

the

inequality:

Xe

- x( C \ {e})

::;

o (where e E

C)

follows from

other

cycle inequalities

and

the

nonnegativity

condition

x

::::

o.

Indeed, suppose

that

C = C

l

U

...

U C

p

,

where

the

C;'s

are edge disjoint circuits. We

can

suppose

that

e E C

l

.

Then,

the

inequality:

Xe

-

x(

C \ {e})

::;

0 follows

by

summing

up

the

inequalities:

Xe

-

x(

C

1

\

{e})

::;

0

and

-x(C

i

)

::;

0 (i = 2,

...

,p). Suppose now

that

C is a circuit having a

chord

f.

Then,

this

chord

determines

a

partition

of C into two

paths

PI, P

2

such

that

Ci

:=

PiU{f}

is a circuit for i =

1,2.

Then,

assuming

that

e E PI,

the

inequality:

Xe

-

x(

C \ {e})

::;

0 follows

by

summing

up

the

inequalities:

Xe

-

x(

C

l

\

{e})

::;

0

and

xf

-

x(C

2

\

{f})

::;

o.

Proof

of

(i).

Set

Q(G):=

{x

E

ffi.~

I

xe-x(C\{e})::;

0 for C cycle

ofG,e

E

C}.

We first check

that

MET(G)

~

Q(G).

Let

x E

MET(G),

let C

be

a cycle

of

G

and

let e E

C.

We show

that

Xe

-

x(C

\ {e})

::;

o.

By

the

above observation,

we

can

suppose

that

C is a circuit, say, C =

(1,2,

...

,p)

and

that

e

:=

12.

By

the

definition of

MET(G),

there

exists Y E

METn

whose

projection

on

ffi.E

is x.

Then,

Xe

-

x(

C \ {e}) = X12 -

X23

-

...

- Xp-l,p = L

Yli

-

Yl,i+l

-

Yi,i+l

::;

o.

2:C;i:C;p-l

We show

the

converse inclusion: Q(G)

~

MET(G)

by

induction

on

lEI.

This

inclusion holds

trivially

if

G = Kn. Suppose now

that

G

=1=

Kn-

Let

e

:=

uv

be

an

edge

of

Kn

that

does

not

belong

to

E

and

let x E Q(G).

Then,

x

can

be

extended

to

a vector Y E ffi.EU{e} which belongs

to

Q(G

+

e)

(G + e

denoting

the

graph

obtained

by

adding

the

edge e

to

G). For this,

it

suffices

to

take

Ye

:=

a,

where

max

(xf

-

x(P

\

{f}))

::;

a::;

minx(Q),

PifEP

Q

where

P,

Q

run

over all

paths

joining u

and

v in G. (Such

an

a exists as x E

Q(G).)

By

the

induction

assumption,

Q(G

+ e) =

MET(G

+ e). Therefore, Y is

the

projection

on

ffi.EU{e} of some z E

METn.

Hence, x is

the

projection

of z

on

R

E

,

which shows

that

x E

MET(G).

27.3

Projecting

the

Triangle Inequalities

433

The

proofs

of

(ii),(iii)

can

be found

in

Barahona

and

Mahjoub

[1986];

in

fact,

it

is

shown

there

that,

under

the

same

assumptions,

the

inequality

in

question

defines a facet

of

the

cut

polytope

CUTD(G). I

The

list

of

inequalities

that

define

the

semimetric

polytope

METD (G)

can

be

exponentially

long

(in

terms

of

n). Nevertheless,

Barahona

and

Mahjoub

[1986]

showed

that

the

separation

problem

for

the

system:

(27.3.4)

{

0

<

Xe

< 1

x(F)

-

x(O

\

F)

:S

IFI-1

for e E

E,

for ° cycle

of

G, F

<;;;

0,

IFI

odd

can

be

solved

in

polynomial

time

(in

terms

of

n

and

the

size

of

x).

This

problem

can

be

formulated

as follows:

Given a vector x

E

cry;

, decide whether x satisfies all the inequalities

from the

system

(27.3.4).

If

not, find an inequality from (27.3.4) that

is violated by

x.

This

problem

can

be

solved

in

the

following way.

First,

check

whether

0

:S

Xe

:S

1

holds

for all edges e E

E.

If

not,

then

we

have found a violated inequality.

Otherwise,

we

can

suppose

that

0

:S

Xe

:S

1 for all e E

E.

Note

that

the

cycle

inequality

(27.3.2)

can

be

rewritten

as

2::

Xe

+

2::(1-

Xe)

:::::

l.

eEC\F

eEF

We form a

new

graph

G'

with

two nodes

i'

and

i"

for each

node

i

of

G. For each

edge

ij

E

E,

we

introduce

in

G'

the

edges

i'j',

i"j"

with

weight

Xij,

and

the

edges

i'

j",

i"

j'

with

weight 1 -

Xij.

So,

we

have defined a weight

function

on

the

edges

of

G'. Now, for each

node

i

of

G,

we

compute

a

shortest

(with

respect

to

this

weight function)

path

in

G'

from

i'

to

i".

Then,

the

minimum

over all

nodes

i

of

G

of

these

shortest

paths

gives

the

minimum

value

of

~eEC\F

Xe

+

~eEF(l-

Xe)

over all cycles

0,

F

<;;;

0,

IFI

odd.

If

this

minimum

is less

than

one,

then

we

have found a

violated

inequality; else, x satisfies all

the

cycle inequalities. As

the

computation

of

a

shortest

path

can

be

done

in

O(n

2

),

the

separation

problem

for

the

system

(27.3.4)

can

be

solved

in

O(n

3

).

As

an

application

(using

the

ellipsoid

method,

as

exposed

in

Gri:itschel,

Lovasz

and

Schrijver [1988]),

we

deduce

that

one

can

optimize

a linear objective

function

over

the

system

(27.3.4)

in

polynomial

time.

Proposition

27.3.5.

Given c E

cry;,

the optimization problem:

max(

c

T

x I x satisfies the

system

(27.3.4))

can

be

solved

in

polynomial

time

(polynomial

in

n and

in

the size

of

c). I

434

Chapter 27. Triangle Inequalities

In

fact, there is a much simpler argument for proving Proposition 27.3.5,

based on Theorem 27.3.3. Indeed, as METD(G) is the projection on

.IRE

of

MET~,

the

two problems:

where

we

extend c

to

.IRE"

by setting C

e

:=

0 if e E En \ have the same

optimum

value. Now,

the

latter

problem is a linear programming problem

with

(;)

variables

and

4G)

constraints. Hence,

it

can clearly be solved in polynomial

time.

27.3.2

The

Cut

Polytope

for

Graphs

with

no

K5-Minor

We

now

return

to

the

question of characterizing

the

graphs G for which equality

holds in

(27.3.1). Due to switching,

CUT(G)

= MET(G)

¢:::}

CUTD(G) = METD(G).

As was already mentioned earlier, equality does not hold

for

the

graph G = K

5

•

The

next result shows

that

K5 is

the

unique minimal (in

the

sense of

graph

minors) exception.

Theorem

27.3.6.

CUT(G) MET(G) or, equivalently, CUTD(G) = METD(G)

for

a graph G

if

and only

if

G does not have any K

5

-minor. I

Seymour [1981J proved

the

result concerning the cones

and

Barahona and

Mahjoub

[1986] derived the result for

the

polytopes using switching. Another

proof for Theorem

27.3.6 is given

by

Barahona

[U}83]i

it

is based on a decom-

position result due to Wagner

[1937] for

the

graphs

with

no K5-minor, together

with

a result showing how

to

derive a linear description

of

the

cut

polytope

of

a

graph

which is a clique k-sum of two smaller graphs (k S 3). As

an

application

of Proposition

27.3.5

and

Theorem 27.3.6,

we

obtain:

Theorem

27.3.7.

The max-cut problem:

(where

c E

to!

) can

be

solved

in

polynomial time for the class

of

graphs with no

K

5

-minor. I

In

particular,

the

max-cut problem

can

be solved in polynomial

time

for

the

class

of

planar

graphs.

As correlation polyhedra

and

cut polyhedra are in one-to-one linear corre-

spondence,

the

above results have immediate counterparts for

the

correlation

polyhedra

of

arbitrary

graphs.

Given a

graph

G =

(Vn,E),

its

correlation cone COR(G)

and

its correlation

polytope

CORD(G) are defined in

the

following way: COR(G) (resp. CORD(G))

27.4 Cycle Polytopes of Binary Matroids

435

is

the

projection

of

the

correlation cone

COR,."

(resp. of

the

correlation polytope

CO~)

on

the subspace llt

EUV

""

where

Vn

is identified with

the

set

of

diagonal

pairs

ii

for i E V

n

•

Let

V'

G denote

the

suspension graph of G obtained by adding a new node,

say

n +

1,

to G

and

making

it

adjacent to all nodes

in

V

n

•

Hence, the edge set

E(V' G)

of

V'

G is E U { (i, n +

1)

liE

V

n

}.

We

can

define a one· to-one mapping

~

between

the

space indexed by E(V'G)

and

the space indexed by E U

Vn

in the

following manner: For

x E

lltE(VG),

y E llt

EUV

",

, Y

~(x)

if

(27.3.8)

Yii

Xi,n+I

Yij

=

~(Xi,n+I

+

Xj,n+l

Xij)

for i E V

n

,

for

ij

E E.

Hence, when G is

the

complete graph Kn,

then

~

is

the usual covariance mapping

(pointed

at

position n+ 1), as defined in Section 26.1. Clearly, the

cut

polyhedra

for

V'G

and the correlation polyhedra

for

G are in one-to-one correspondence.

Namely,

COR(G)

=

~(CUT(V'G»

and

CORD

(G)

~(GCTD(V'G).

In

particular, Theorem 27.3.6 implies

the

following result for the correlation

polyhedra, established in Padberg

[1989].

Theorem

27.3.9.

For a

graph

G, COR(G) =

~(MET(V'G»

or, equivalently,

CORD(G)

~(METD(V'G»

if

and only

ifG

has no K

4

-minor. I

The

inequalities defining

the

polytope

~(METD(V'G»

arise as projections

of

the

correlation triangle inequalities. A linear system defining

the

polytope

~(METD(V'G»

can

be easily deduced from

the

linear description

of

METD(V'G)

presented

in

Theorem 27.3.3 (i) by applying

the

transformation

~

(an explicit

description

can

be

found, e.g., in

Padberg

[1989]).

As a direct application

of

Theorem 27.3.7,

the

unconstrained quadratic

0-1

programming problem (5.1.4)

can

be solved in polynomial time when the graph

supporting

the

linear objective function has

no

K4-minor.

27.4

An

Excursion

to

Cycle

Polytopes

of

Binary

Matroids

As

we

remarked earlier, some properties of the

cut

polyhedra are valid

for

more

general set families

than

cuts. Indeed,

we

saw in Section 26.3.1

that

the

switching

operation

applies to general set families under the only assumption

that

they are

closed under taking symmetric differences. Such set families are known

in

the

literature

as cycle spaces of binary matroids.

Cut

polyhedra are, thus, special

instances

of

cycle polyhedra

of

binary matroids. Cycles

in

graphs yield

other

interesting instances of binary matroids. Therefore, binary matroids constitute

a unified framework for a variety of combinatorial objects.

We

cannot

go

here too

much

in

detail into matroid theory as a detailed treatment falls

out

of

the scope

436

Chapter

27.

Triangle Inequalities

of

the

present

book. We will therefore

restrict

ourselves

to

presenting

without

proof

some

of

the

main

known results relevant

to

cycle

polyhedra.

We recall

in

the

first subsection some necessary definitions

5

about

binary

matroids.

Section 27.4.2 reviews results

about

the

cycle cone

and

polytope

of

a

binary

matroid.

We

then

group

in

Section 27.4.3 several

additional

questions

and

results

related,

in

particular,

to

the

lattice

and

the

integer cone

generated

by cycles of

binary

matroids.

27.4.1

Preliminaries

on

Binary

Matroids

Cycles,

Co

cycles

and

Representation

Matrix.

A binary matroid M con-

sists

of

a

pair

(E,C),

where E is a finite set

(the

groundset of

M)

and

C is a

collection

of

subsets

of

E

that

is closed

under

taking

symmetric

differences, i.e.,

such

that

CL.C'

E C for all C,

C'

E

C.

The

members

of

C are called

the

cycles

of

M

and

C is

the

cycle space

of

M.

Note

that

0 is always a cycle.

Two

examples

of

binary

matroids

can

be

constructed

from graphs. Let G =

(V,

E)

be

a

graph.

As

the

symmetric

difference of two

Eulerian

subgraphs

(cycles)

of

G

remains

a

Eulerian

subgraph

of

G,

we

have a first

matroid

on

E,

denoted

as

M(G)

and

called

the

graphic matroid

of

G, whose cycle space is

the

set

of

Eulerian

sub

graphs

of

G.

The

symmetric

difference

of

two

cuts

in G is

again

a

cut;

therefore, we have a second

binary

matroid

on

E,

denoted

as

M*(

G)

and

called

the

cographic matroid

of

G,

with

cycle space

the

set

of

cuts

of

G.

Let

M = (E,

C)

be

a

binary

matroid.

Set

C*

:=

{D

~

E:

IC n DI is even for all C E C}.

Then,

C* is obviously closed

under

the

symmetric

difference. Hence,

M*

:=

(E,C*)

is

again

a

binary

matroid,

called

the

dual matroid

of

M.

The

members

of

C*

(the

cycles

of

M*)

are

also called

the

cocycles

of

M.

One

can

check

that

the

dual

of

M*

coincides

with

M,

i.e.,

(M*)*

=

M.

As

an

example,

the

dual

of

the

graphic

matroid

M(G)

of

a

graph

G is its cographic

matroid

M*(G)

(since

a

cut

and

a cycle have

an

even intersection).

The

minimal

nonempty

cycles

of

M

are

called

the

circuits

of

M

and

the

minimal

nonempty

co cycles

are

called its cocircuits. Every

nonempty

cycle

can

be

decomposed

as a disjoint union

of

circuits.

The

matroid

M is

said

to

be

cosimple

if

no cocircuit has

cardinality

1 or

2.

Binary

matroids

can

alternatively

be

viewed as linear spaces over

the

field

with

two elements GF(2)

:=

{a,

I}.

Indeed, for

any

subsets

C,

C'

~

E,

X

C

,6C'

=

XC

+

Xc'

(modulo

2). Hence,

the

set family C is closed

under

the

symmetric

difference

if

and

only

if

the

set

{XC

ICE

C}

is a linear subspace

of

the

binary

5The

reader

may

consult

Welsh

[1976]

or

Oxley

[1992] for

general

information

about

ma-

troids.

We

do

not

consider

here

matroids

in

full

generality

but

only

binary

matroids.

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

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