# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**57**> 58 59 60 61 62 63 .. 156 >> Next

Set PartitioningA Survey 155

On the other hand, sp is a special case of spp; conversely, spp can be restated as

max {dm + c"x | Ax e, x,- = 0 or 1, j e N}

with c" = 0eAc; and again, for d sufficiently large, this problem has the same set of optimal solutions as spp, whenever the latter is feasible.

The equivalence of sp and spp is crucial to some of the results to be discussed.

Next we turn to a family of four interrelated problems defined on an undirected graph, two of which are special cases of sp.

7.1.3 Edge Matching and Covering, Node Packing and Covering

Let G = (N, E) be a finite undirected graph with n = |N| nodes and q = |E| edges. Let Aa be the n 'x q node-edge incidence matrix of G, en, and eQ the n -vector and q-vector respectively, whose components are all 1.

An edge matching in G is a subset E' of edges such that every node of G is incident with at most one edge in E'. If every node of G is incident with exactly one edge in E', then E' is a perfect matching. An edge cover (a covering of nodes by edges) in G is a subset E" of edges such that every node of G is incident with at least one edge in E". The edge matching problem, or the problem of finding a maximum-cardinality edge matching in G, is then

em max{eqy | AGy =?e, y, =0 or 1, i = 1,. .., q}

while the edge covering problem, or the problem of finding a minimum-cardinality edge cover in G, is

ec min {eqy | A0y =5 en, y; = 0 or 1, i,..., q}.

A node packing (vertex packing) in G is a subset N' of nodes such that every edge of G is incident with at most one node in N". The node packing problem, or the problem of finding a maximum-cardinality node packing (internally stable node set, independent node set) in G, is then

np max{ex | Ajx =? eq, x, =0 or 1, j = 1,. .., n}

while the node covering problem, or the problem of finding a minimum cardinality node cover in G, is

nc min{ex | Ajxs* eq, x( =0 or 1, j = 1,..., rc}.

If a0, (30, <*!, and (3, are the cardinality of a maximum node packing, minimum node cover, maximum edge matching, and minimum edge cover in G, respectively, then these four numbers are connected by the following simple formula.

156

Egon Balas and Manfred W. Padberg

Theorem 7.1 (Gallai 1958) For any nontrivial connected graph G with n nodes,

a0 + /30 = n = a1 + /31.

A maximum edge matching and a minimum edge cover are easily obtained from each other; the same is true of a maximum node packing and a minimum node cover.

Clearly, em and np are special cases of sp. The problem of finding a perfect edge matching, obtained from em by replacing the inequality with equality, is on the other hand a special c^se of spp.

When G is bipartite, AG is totally unimodular and the four integer programs listed above can be replaced by the associated linear programs. In the general case, however, the optimal solutions to these linear programs need not be integer. On the other hand, a basic result on convex polyhedra, due to Weyl (1935), implies that there always exists a finite system of linear inequalities whose solution set is the convex hull of feasible integer points. Identifying such a defining linear system is not an easy task in general. For the edge matching problem, this task was solved by Edmonds (1965a) (see also Edmonds, 1965b), who has also given an algorithm of complexity 0(n3) for solving em or its weighted version (in which eq is replaced by an arbitrary integer vector), based on Berges (1957) theorem of alternating chains and using the above mentioned defining linear system to prove optimality (for related work see also Balinski, 1969, 1972).

More recently, Pulleyblank and Edmonds (1973) have sharpened the characterization of the edge mathing polytdpe by identifying its (unique) minimal defining linear system.

An optimal solution to em also (trivially) yields an optimal solution to ec.

The pair of problems np, nc, is considerably more difficult. Balinski (1969) has characterized maximum node packings in terms of alternating subgraphs (see also Edmonds, 1962), but no polynomially bounded algorithm is known for the solution of this problem. More recently, several classes of facets of the node packing polytope have been identified (see Padberg, 1971, 1973a, 1975b; Chvatal, 1972; Nemhauser and Trotter, 1974; Trotter, 1974; Balas and Zemal, 1976a,b). Some algorithms have also been proposed (see Trotter, 1973; Balas and Samuelsson, 1973, 1974a), none of which is polynomially bounded.

7.1.4 Node Packing, Set Packing, Clique Covering

Denote by at the ;th column of the matrix A of sp. The intersection graph Ga = (N, E) of A has one node for every column of A, and one edge for every pair of nonorthogonal columns of A [i.e. (i,j)eE if and only if OiOj 1]. Let Aa be the node-edge incidence matrix of GA, and denote by

Set PartitioningA Survey

157

np the weighted node packing problem whose weights c, are the same for each node as those of sp, i.e.

np max {cx | Aj x =? eq, x, = 0 or 1, j = 1, . .., n}.

Remark 7.1 x is a feasible (optimal) solution to sp if and only if it is a feasible (optimal solution to np.

**57**> 58 59 60 61 62 63 .. 156 >> Next