# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**59**> 60 61 62 63 64 65 .. 156 >> Next

Theorem 7.2 The inequality

I *«1

where K c N, is a facet of Pj if and only if K is the node set of a clique in GA.

As a direct consequence, the polytope

Pc={xeRn |AcX«ec,x30}

where Ac is, as before, the clique matrix of GA, satisfies P,cPcc p. In general, Pc is different from Pf as well as from P. There is, however, a large class of matrices A for which the three polytopes P, Pc, and Pj coincide, i.e. P = Pc = Pj. Zero-one matrices with this property are called perfect and can be characterized in terms of certain ‘forbidden’ submatrices.

Let A' be a mxfc zero-one matrix, with m^k. A' is said to have the property TTe k if the following conditions are met:

(i) A’ contains a k x k nonsingular submatrix A j whose row and column sums are all equal to /3.

(ii) Each row of A' which is not a row of A',, either is componentwise equal to some row of A[, or has row sum strictly less than /3.

Theorem 7.3 (Padberg, 1974a). The following two conditions are equivalent for an arbitrary m x n zero-one matrix A:

(i) A is perfect, i.e. P = PC =Pr.

(ii) For (3^2 and 3A does not contain any mxk submatrix A' having the property np k.

Perfect matrices are closely related to perfect graphs (Berge, 1970), and normal hypergraphs (Lovasz, 1972). They properly subsume nonnegative totally unimodular matrices, as well as balanced matrices (Berge, 1972). (For a discussion of their interrelationships see Padberg 1974b, c.) As

160

Egon Balas and Manfred W. Padberg

mentioned in Section 7.1.4, the clique-matrices of perfect graphs are all perfect. A unified treatment of perfect graphs and perfect matrices, from an algebraic point of view, is to be found in Padberg (1975a).

Whenever PC#P, a facet of Pr of the type characterized by Theorem 7.2 is absent from the constraint set defining P. Facets of Px of that type are easy to detect. In general, however, more complicated types of inequalities are needed in order to characterize P,. Since these inequalities are associated with certain subgraphs of Ga, the intersection graph of A, we will from now on use a notation which relates GA directly to the (unique) node packing/set packing polytope Pf defined by GA. Thus we will denote GA and Px by G and P(G) respectively.

The next few theorems are concerned with classes of graphs whose associated set packing polytopes have a facet with all (left-hand side) coefficients equal to 1. From Theorem 7.2, a first such class is that of complete graphs. The next theorem (whose part (i) is due to Padberg 1971, 1973a; part (ii) to Nemhauser and Trotter, 1974) specifies two further classes.

Theorem 7.4 If G is either (i) an odd hole, or (ii) an odd anti-hole, then

I

jeN

is a facet of P(G), with k = (n —1)/2 in case (i), and k= 2 in case (ii).

Two additional classes of graphs defining facets with coefficients equal to 1 are webs and their complements (Trotter, 1974). A web W(nM) = (N, E) is defined by |N] = n s* 3 and

(i, j) ˆ E O / = i + k, i + k +1,..., i + n — k

(where sums are taken modulo 1), with l=sk«[n/2]. The web W(nk) is regular of degree n — 2k + l, and has exactly n maximum node packings of size k. The anti-web W(„M), or complement of the web W(n k), is regular of degree 2(k - l)m and has exactly n maximum cliques of size k.

Theorem 7.5 (Trotter 1974)

(i) If G = W(n. k) is a web, the inequality

I

jeN

is a facet of P(G) if and only if n and k are relatively prime.

(ii) If G = W(n k) is an anti-web with n and k relatively prime, ks*2, the inequality

X x, =s[n/k]

jeN

is a facet of P(G).

Set Partitioning—A Survey

161

Note that for all the facets with left-hand side coefficients equal to 1 considered so far, the right-hand side coefficient was equal to the maximum cardinality of an independent node set (independence number) of the graph G associated with P(G), namely: 1 in the case of the complete graph or clique Kn; (n —1)/2 and 2 in the case of the odd hole H„ and odd anti-hole Hn, respectively; k and [n/fc] in the case of the web W(nk) and anti-web W(nk„ respectively. This raises the more general question as to when an inequality with left-hand side coefficients equal to 1, and right-hand side equal to a(G), the independence number of some graph G, is a facet of P(G).

We first state a sufficient condition due to Chvatal (1972). An edge u e E of G = (N,E) is called a-critical if its removal produces a graph with an independence number greater than «(G).

Theorem 7.6 (Chvatal, 1972) Let E* be the set of a-critical edges of G. If G*~(N,E*) is connected, then

® X*,S«(G)

jeN

is a facet of P(G).

It is easy to check that all the graphs examined so far which give rise to facets of the above form (i.e. cliques, odd holes and odd anti-holes, webs and anti-webs with n and k relatively prime), satisfy the condition of Theorem 7.6. Nevertheless, Chvatal’s condition is not necessary, as the following example shows.

Example 7.1 Let G = Hi, + Hi be the join of two (disjoint) odd holes, Hi, and Hj respectively; i.e. G consists of H5IIH5 and edges joining each node of H5 to each node of Hi (see Figure 7.1). Then the inequality

**59**> 60 61 62 63 64 65 .. 156 >> Next