THE 1-MATCHING/COVERING PROBLEM by Clovis Perin Technical Report 81-3 Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 March 1981. Research effort was supported by the Department of Industrial and Operations Engineering of The University of Michigan and by the Air Force Office'of Scientific Research, Air Force Systems Command, USAF, under grant no. AFOSR 78-4646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.

Abstract Consider an undirected network consisting of a finite nonempty set < _- > o N of n nodes partitioned as N-U N U NUN (where some of these subsets may be empty), a set E of m edges, and a vector of edge costs c. A 1-matching/covering is a subset of edges satisfying the properties: i) every node of N is incident with at most one edge of the subset; ii) every node of N is incident with exactly one edge of the subset; iii) every node of N- is incident with at least one edge of the subset. There are no constraints associated with a node of N. The minimum cost 1-matching/covering problem is to find a l-matching/ covering which minimizes the total cost of the edges in the subset. This paper discusses an algorithm for: solving this problem, which can be implemented with a worst case time complexity O(n ).

1 - Introduction In the late 60's, Edmonds [1,2] introduced the blossom algorithms for solving 1-matching problems which are defined on undirected networks with n nodes and m edges. The minimum cost 1-matching and the minimum cost 1-perfect matching problems have algorithms whose worst case time complexity is O(n m). This maximum effort can be further reduced to 3 0(n ) as shown in [6]. White and Gillenson [11] developed a blossom algorithm for the 2 minimum cost 1-edge covering problem with time complexity 0(nm ). Murty and Perin [9] designed another algorithm for the same problem 3 which can run in 0(n ). All the above problems constitute special cases of the minimum cost 1-matching/covering problem which is the subject of this paper. We 2 3 present an O(n m) algorithm which can run in O(n ). Edmonds, Johnson, and Lockhart [3,4] developed another blossom algorithm for solving a more general problem - the general matching. However, the time complexity of the algorithm is greater than O(n m) and the data structure needed for the implementation is much more complex than the one needed for implementing the algorithm presented in this paper. 1

2 - Formulation of the Problem Consider an undirected network G = (N,E,c) consisting of a finite nonempty set of n nodes N i: i = 1 to n, a set of m edges E = { (i; j): i i j E N 3, and an edge cost vector c = [c i]. It is < = > o given a partition NU N UN UN of the set of nodes where some of the subsets may be empty. Let x = [x. ] be a 0-1 vector defined over the set of edges. The minimum cost 1-matching/covering problem is formulated as follows: Problem I minimize.. [ c.. x..: (i;j) C E ] subject to the node constraints S 1 for i C N.i) = 1 for i E N > 1 for i E Nunconstrained for i E N and restricted to x.. = 0 or 1 for (i;j) C E 13 where x(i) =. [ x.: (i;j) C E ] for i C N. Note that x.., x.. are two representations of the same variable.'j j'

3 Figure 1 - Example of a 1-matching/covering for a network with 12 nodes. The symbols <, >, o identify the nodes of the subsets N-, N, N-, N, respectively.

4 Given a 0-1 edge vector x = [x. ], define the set of solution edges E(x) = { (i;j) C E: x.. = 1 E(x) is said to be a 1-matching/covering if every node of N (N, t) is incident with exactly (at most, at least) one solution edge (i.e., x satisfies the node constraints). Define S = { s N U N U N-: s has odd cardinality Isl > 3 J x (s) S.. [ x.: (i;j) joins a node inside to 3 node outside s ] + _. [ x(i): i E N inside s] + Z. [ -x(i): i E N~ inside s ] a 1= + IF nsl - JNnsI s Theorem 1 Every 0-1 edge vector x which is a feasible solution of problem I satisfies the blossom constraints x (s) > a for s S 5

5 Proof Each blossom constraint s can be written as follows:..1 [ x..: (i;j) joins a node inside to a node outside s ] + Z. [ x(i) - 1: i C N- inside s ] + Z. [ 1 - x(i): i E N inside s ] 1 1 It is easily seen that the left hand side must be a nonnegative integer because x is an integer feasible solution. Therefore, the left hand side equal to zero is the only remaining possibility for violating a blossom constraint. Since every s C S contains only nodes of N U N U N, it follows that every node inside s must be incident with exactly one solution edge, and there must be no solution edge joining a node inside with a node outside s. However, this situation cannot occur because every edge joins exactly two nodes and s has odd cardinality. Therefore, every feasible solution of problem I must satisfy the blossom constraints. The Optimality conditions of problem I are obtained by relaxing the integrality restrictions and introducing the blossom constraints. The algorithm presented in this paper constitutes a proof that the extreme points of the set of feasible solutions of this modified problem are the feasible solutions of the original problem.

6 Problem II: Primal minimize i.. [ c.. x..: (i;j) C E ] subject to < 1 for i E N x(i) = 1 for i C N r 1 for i E ND x (s) > a for s E S s 0 < x. < 1 for (i;j) C E 13 The dual problem is obtained by associating to the node and blossom constraints, node prices y [yi] and pseudonode prices z [z ], respectively. Problem II: Dual maximize [ y] + [ a Y ] + 2 [ ui ] subject to f 0 for for i C Nunrestricted for i C N y! < > i 1i > 0 for i Nf= 0 for i C N~ z > 0 for s S s u.. < 0 v.. for (i;j) C E y. + y. + Z [ (bS+bs): i or j inside s ] + u. + v. c.i for (i;j) C E Yi + Yj + 1J 1J 1 where ( -1 for i E N- inside s - s O0 for i C N inside s 1 for i C N~ inside s 1 for i C. N outside s

7 Defining for each (i;j) E E a relative cost S S d. + y + [ (b+b) z i or j inside s E S ] J 1 J S j s - C. U. - V.. 1J 1J 1J the complementary slackness conditions can be written as follows: Problem II: Complementary Slackness Conditions Yi ( x(i) - 1 ) 0 for i E N z ( x(s) - a ) = 0 for s E S S S d.. > c.. implies x. = 1 1J 13 13 ) for (i;j) E E d.. < c.. implies x.. = 0 1j 1j 1J Hence, a solution (x,y,z) is an optimum solution of problem II if: i) x is a 0-1 vector satisfiying the node constraints; ii) (y,z) is dual feasible; iii) (x,y,z) satisfies the complementary slackness conditions.

8 3 - Description of the Algorithm Let E = [ (i;j) E: i,j C N-U N, c.. 0 Suppose problem I has an optimum solution which does not include all edges of E; it is possible to construct an alternate optimum solution by introducing the edges of E which are not present because feasibility is maintainedand the objective value does not increase when nonpositive values are added to it. The algorithm maintains all edges of E in the solution set. During the execution of the algorithm, the set of solution edges is partitioned into matching and covering edges. Edges of E are always covering edges; solution edges which are adjacent to other solution edges are covering edges, too. The remaining solution edges are matching edges. So, components of the solution set consisting of a single edge which is not an edge of E constitute the set of matching edges. Note that such a classification leads to a partition of the set of nodes: those covered by matching edges; those covered by covering edges; and those which are not covered by the solution edges. This leads to the following classification of nodes (see figure 2): matched - nodes incident with a matching edge type 2 - nodes incident with two or more covering edges type 1 - nodes incident with exactly one covering edge < 0 type 0 - nodes of NU N with null node price incident with no solution edge <;> = exposed - nodes of N- with negative price and nodes of N-U N, incident with no solution edge

9 [1] [M] [0] > [2] [1] [ M] [O]Q@ [1] \ ExM] null price O G [E] [M] Figure 2 - Example of edge and node classification. Symbols inside the nodes define the node partition. Wavy edges are matching and straight edges are covering. Symbols in brackets identify the node classification: M - matched, 2 - type 2, 1 - type 1, 0 - type 0, E - exposed.

10 The algorithm works with all solution edges as a subset of E U E where the set of equality edges E is defined by E = ( (i;j) E E: d. - c. ] Alternating trees are rooted at exposed nodes and grown by incorporating equality edges in such a way that every path in a alternating tree connecting a node with the root is an alternating path of matching/nonsolution equality edges. Labels with three indices are assigned to the nodes in the alternating trees identifying: i) the tree a node belongs to; ii) the predecessor node in the alternating path to the root; iii) the even (outer't+") or odd (inner "-") length of the alternating path. The roots of the alternating trees receive outer labels with no predecessors. During the tree growing process, an odd alternating cycle of equality edges may be detected. The set of nodes in such a cycle define a partial network called simple blossom which is shrunken into a pseudonode. To shrink a simple blossom into a pseudonode is to introduce a pseudonode containing inside all nodes of the simple blossom; each node of the simple blossom is said to be inside the pseudonode; and every edge joining a node inside with a node outside the pseudonode is said to be incident with the pseudonode. The solution/nonsolution role of the edges in a simple blossom may change during the execution of the algorithm, but the following properties are always satisfied: i) there is an odd alternating cycle of solution/nonsolution

11 equality edges connecting all nodes of the simple blossom; ii) there is an unique node called the base of the simple blossom which is incident with either two solution edges or two nonsolution edges of the odd cycle; iii) every node of the simple blossom but the base is incident with a pair of solution-nonsolution edges of the odd cycle. The shrinking operation is carried out over simple blossoms which may contain pseudonodes shrunken before. So, it is possible to find a pseudonode inside other pseudonode. At this point, we introduce the terms original node (i.e., a node of N) and current node (i.e., original node or pseudonode which is not inside any pseudonode). Pseudonodes are classified as matched, type 1, type 0, or exposed. A matched (type 1) pseudonode is incident with a matching (covering) edge. An exposed (type 0) pseudonode is incident with no solution edge and contains inside it an exposed (type 0 or type 2) original node. Note that there are no "type 2" pseudonodes. See figure 2. The base and the apex of an original node are defined as the original node itself. The base of a pseudonode is the base of its simple blossom. The apex of a pseudonode is the apex of its base. Therefore, exposed, matched, type 1, and type 0 pseudonodes have bases which are exposed, matched, type 1, and (type 0 or type 2), in the same way that they have apices which are exposed, matched, type 1, and (type 0 or type 2), respectively.

12 matched type 1 matye ed type 1 PwwwO Q. —--— Q edges are covering Dased edges are equality. Symbols in O ^W^AAA/O. type 0 type 0 [0] exposed Figure 3 - Simple blossom classification. Wavy edges are matching. Straight edges are covering. Dashed edges are equality. Symbols in brackets identify the node classification of the base of the simple blossom. Simple blossom classification is given in terms of the corresponding pseudonode.

13 During the execution of the algorithm, nonexposed nodes (i.e., matched, type 2, type 1, type 0) remain nonexposed and at least one exposed node becomes nonexposed when an augmentation is performed, and this occurs when an augmenting path is detected. An augmenting path is an alternating path of solution/nonsolution equality edges connecting an exposed node to either another exposed node, a type 0 node, a type 1 node, a type 2 node, a matched node that can become type 2, or a matched node that can become type O; every augmenting path has odd length except the one connecting an exposed node to a matched node that can become type 0 which has even length. An augmentation consists of reversing the solution/nonsolution role of the edges in an augmenting path. Note that all edges in such a path are equality edges and that every nonextreme node of an augmenting path remains incident with one [but not the same] solution edge. Extreme nodes of an augmenting path either become incident with a solution edge or become type 0. After an augmentation, the apex of a pseudonode incident with a solution edge is the original node inside the pseudonode incident with this solution edge, and the apex of a type 0 pseudonode is a node of < > N UN with null node price. The base of a pseudonode is always the node of the simple blossom associated with the pseudonode which either is the apex or contains inside it the apex. The two edges of the odd cycle of equality edges of the simple blossom must be solution edges, if the pseudonode is type 0 and the base is a node of N; otherwise, these two edges must be nonsolution edges. Once the role of these two edges have been determined, the solution/nonsolution role of the remaining edges of the simple blossom is uniquely specified by the property that every node of the simple blossom but the base is incident with a pair of solution-nonsolution edges of the odd cycles

14 0 ---— ^ VVW^O i- Cp VE double [E] [E] + - + Q0 - - -Q type 0 [E] [0] + + 0o —-- O _0*'-_0'_ type 1 [E] [1] [F]- - - O-\w8 -0m type 2 [E] [2] + + + + Q. — OQ VV —Q o -m type 3 [E] [M] E M _WW- --- type 4 [E] [M] Figure 4 - Examples of augmenting paths. Wavy edges are matching. Straight edges are covering. Dashed edges are equality. Extreme nodes of augmenting paths have their node classification identified by the symbols in brackets. Classification of augmenting path is made in terms of the corresponding augmentation.

15 Properties I The following properties are satisfied throughout the execution of the algorithm. x.. -= 1 implies d.. t c. 1J 1J 1J x... 0 implies d.. < c. J 1J 13J x(i) > 1 implies i E N UN with y. =0 x(i) < 1 implies either 0 i 6 N2UN with y. 0 i is exposed < 0 for i Ny. f = 0 for i E N > 0 for i Nz s 0 for s 6 S s z > 0 implies either X (s) = a s i s exposed l s is exposed

16 Conditions I The following conditions are required before a dual solution change step be executed: 1) each current node which is exposed must be outer labelled. 2) every inner labelled node must be joined by a matching edge to an outer node. 3) no current equality edge joins an outer node to a noninner (outer or unlabelled) node. 0 < 4) no inner node of N U N has null price. 5) no inner pseudonode has null price. 6) no outer node of N~ UN has null price. 7) no outer pseudonode contains inside it a node of N U N with null price. In order to compute the relative cost d.. of an edge joining two current nodes, define for every original node < 0 ( iy i E N- UN y;= yi S [z z i inside s: S ] i E N i + 2 s [ z: i inside s E S] i Yi s s so that d.. y! + y' for every edge (i;j) E E joining two 13 - 1 J current nodes which may be the original nodes i, j or pseudonodes containing i, j inside them. Therefore, an edge with di. = y + y' = 0 joining two current nodes is an equality edge.

17 4 - Algorithm Step 1: Initialization Set r 0 for i E N- UN y = ye = I 1i i 1 minj. [ O, cjk: (j;k) E E } for i NWUN z = 0 for s E S s The set of solution edges is initialized with the edges of E = { (i;j) C E: c.. 0, i,j E NUN 3. Identify all exposed nodes. Assign outer labels to these nodes. They are the roots of the alternating trees. Push all such nodes into the list of unscanned nodes. Go to step 2: checking the list. Step 2: Checking the List If there are no exposed nodes, then terminate. If the list of unscanned nodes contains no current outer nodes, then empty the list and go to step 3: dual solution change. Select a current outer node from the list of unscanned nodes. For every equality edge incident with this node, perform procedure 1: edge scanning, while this node remains outer labelled. Go back to the beginning of step 2.

18 Step 3: Dual Solution Change Compute: 6 = min. { -y.: i E N with outer label } 62 = mini y: i E N with inner label } 63 = mini -y.: i E N inside s E S with outer label } 6 = min. y.: i E N inside s E S with outer label } 6 min [ z: s E S with inner label } 5 S S 66 = min. [(c. — y-y')/2:edge (i;j) joins two distinct outer nodes } 6 1ij J 1 J 6 = min. c.-y'-y': edge (i;j) joins an outer node to a current 7 ij i ji unlabelled node } 6 = min 61, 62, 63, 64, 65, 66, 67 3 If 6 = oo, then stop because the problem is infeasible. Otherwise, update the dual solution. Yi + 6 for i E N with outer label or i inside s S with outer label or i E N inside s E S with outer label yi - 6 for i C N with inner label Y -= (. or i C N- inside s C S with inner label > or i C N inside s E S with outer label y. for i E N current and unlabelled 1 or i C N noncurrent or i N inside s S current and unlabelled or i C N-U N inside s C S current and unlabelled

19 z + 6 for s E S with outer label z = z-6 for s S with inner label s S z for s E S noncurrent or unlabelled s y' + 6 for i C N with outer label 1 or i E N inside s E S with outer label y' - 6 for i C N with inner label Yi or i E N inside s E S with inner label YI for i C N current and unlabelled or i C N inside s E S current and unlabelled Go to step 4: Inspection. Step 4: Inspection If 6 = 61, then check whether there is an outer node of N- with null node price. While there is such a node, perform procedure 7: type 4 augmentation. If 6 = 62, then check whether there is an inner node of N- with null node price. TWhile there' is such a node, perform procedure 6: type 3 augmentation. If 6 = 63 or 6 = 64, then check whether there is an outer pseudonode containing inside it a node of N-U N with null node price. While there is such a node, perform procedure 7: type 4 augmentation.

20 If 6 = 65, then check whether there is an inner pseudonode with null pseudonode price. While there is such a pseudonode, perform procedure 9: pseudonode unshrinking. If 6 = 66, then check whether there is an equality edge joining two outer nodes. While there is such an edge, perform procedure 2: double augmentation if the outer nodes are in different alternating trees, otherwise perform procedure 8: simple blossom shrinking. If 6 = 66 or 6 = 67, then check whether there is an equality edge joining an outer node with an unlabelled node. While there is such an edge, perform procedure 1: edge scanning. Go back to step 2: checking the list. Procedure 1: Edge Scanning This procedure is performed when there is an outer node i joined by an equality edge to a current node j. If node j is outer labelled, and nodes i, j are in the same alternating tree, then perform procedure.8:. simple blossom shrinking, and return. If node j is outer labelled and nodes i, j are in different alternating trees, then perform procedure 2: double augmentation, and return.

21 If node j is a type 0 node, then perform procedure 3: type 0 augmentation, and return. If node j is a type 1 node, then perform procedure 4: type 1 augmentation, and return. If node j is a type 2 node, then perform procedure 5: type 2 augmentation, and return. If node j is a matched node, then let node k be the current node joined to j by a matching edge. Assign to nodes j, k inner and outer labels of the alternating tree of node i whose predecessors are nodes i, j. respectively. Push node k into the list of unscanned nodes. If j E NU N~ with y = 0,. then perform procedure 6: type 3 augmentation and return. If j E S with z. = 0, then perform procedure 9: pseudonode unshrinking. I k NU N with then perform procedure 7: type unshrinking. If k E NUN with Y ~ 0, then perform procedure 7: type 4 augmentation and return. If k E S and contains inside it a node of < > N U NS with null node price, then perform procedure 7: type 4 augmentation and return. Return. Procedure 2: Double Augmentation This procedure is performed when two outer nodes i, j of different alternating trees are joined by an equality edge. Let P(i), P(j) denote the alternating paths connecting nodes i, j to

22 with the roots of their alternating trees; such paths are obtained by backtracking the predecessor indices. The augmenting path determined by P(i) U ((i;j)3 U P(j) connects two exposed nodes. Reverse the solution/nonsolution role of the equality edges in this path. Every matched node remains matched, and the two exposed nodes become matched. Erase the label of all nodes in the alternating trees of nodes i, j. Push the remaining outer nodes into the list of unscanned nodes. Return. Procedure 3: Type 0 Augmentation This procedure is performed when an outer node i is joined by an equality edge to a current type 0 node j. Let P(i) be the alternating path connecting node i with the root of its alternating tree. The augmenting path determined by P(i) U ((i;j)I connects an exposed node with a type 0 node. Reverse the solution/nonsolution role of the edges in this path. Every matched node remains matched, and the exposed as well as the type 0 node become matched. Erase the label of all nodes in the alternating tree of node Ai. Push the remaining outer nodes into the list of unscanned nodes. Return. Procedure 4: Type 1 Augmentation This procedure is performed when an outer node i is joined by an equality edge to a current type 1 node j. Let P(i) be the alternating path connecting node i with the root of its alternating tree.

23 > ~ 0 If j E N UN with yj = 0, then the augmenting path determined by P(i) U ((i;j)} connects an exposed node with a type 1 node. Reverse the solution/nonsolution role of the edges in this path. Every matched node but node i remains matched. Node j becomes type 2. Node i becomes type 1. The exposed node, if other than node i, becomes matched. Otherwise, let node k be the type 2 node joined to node j by a covering edge. The augmenting path determined by P(i) U ((i;j), (j;k)3 connects an exposed node with a type 2 node and goes through a type 1 node. Reverse the solution/nonsolution role of the edges in this path. Every matched node remains matched. The exposed node becomes matched. Node j becomes matched. Node k becomes matched, type 1, or remains type 2 depending on the solution edges incident with it. Erase the label of all nodes in the alternating tree of node i. Pushing the remaining outer nodes into the list of unscanned nodes. Return. Procedure 5: Type 2 Augmentation This procedure is performed when an outer node i is joined by an equality edge to a current type 2 node j.. Let P(i) be the alternating path connecting node i with the root of the alternating tree. The augmenting path P(i) U ((i;j)} connects an exposed node with a type 2 node and does not goes through a type 1 node. Reverse the solution/nonsolution role of the edges in this path. Every matched node but node i remains matched. Node j remains type 2. Node i becomes type 1. The exposed node, if other than node i becomes: matched.

24 Erase the label of all nodes in the alternating tree of node i. Push the remaining outer nodes into the list of unscanned nodes. Return. Procedure 6: Type 3 Augmentation This procedure is performed when there is an inner matched node > 0 j N U N with y. = 0. Let P(j) denote the alternating path connecting node j with the root of the alternating tree. The augmenting path P(j) connects an exposed node with a matched node. Reverse the solution/ nonsolution role of the edges in this path. Node j becomes type 2. The node which was joined by a matching edge to node j and the node which was the predecessor of node j in the alternating path, both become type 1. The remaining matched nodes remain matched. The exposed node, if other than the predecessor of node j, becomes matched. Erase the label of all nodes in the alternating tree of node j. Push the remaining outer nodes into the list of unscanned nodes. Return. Procedure 7: Type 4 Augmentation This procedure is performed when there is an outer node i ~ NUN with y. = 0 or there is an outer pseudonode i E S containing inside it a node k E N-UN with y =0. Let P(i) be the alternating path connecting node i with the root of the alternating tree. The augmenting path P(i) connects an exposed node with a matched node. Reverse the solution/nonsolution role of the edges in this path. Node i becomes type 0; if node i is a pseudonode, then node k becomes the new apex of node i. Every other matched node remains matched. The exposed

25 node, it other than node i, becomes matched. Erase the label of all nodes in the alternating tree of node i. Push the remaining outer nodes into the list of unscanned nodes. Return. Procedure 8: Simple Blossom Shrinking This procedure is performed when two outer nodes i, j of the same alternating tree are joined by an equality edge. Let P(i), P(j) be the alternating paths connecting nodes i, j with the root of the alternating tree, respectively. The odd alternating cycle'of equality edges determined by [ P(i) u n(i;j)3 U P(j) \ P(i) n P() ] defines a simple blossom. Introduce a pseudonode containing inside all nodes and edges of this simple blossom. The base of this pseudonode is the only node incident with two distinct edges of P(i), P(j). The apex of this pseudonode is the apex of its base. The pseudonode receives an outer label of the same alternating tree and with the same predecessor of its base. The label of every node in the simple blossom is erased. Check whether there is a node of N-U N- with null node price inside the pseudonode. Perform procedure 7: type 4 augmentation. Return. Procedure 9: Pseudonode Unshrinking This procedure is performed when an inner pseudonode s has null pseudonode price. The pseudonode is eliminated from the network, so that the nodes in its simple blossom become current. Let node i

26 be the base of pseudonode s and let node j be the node in the simple blossom s which is incident with an equality edge joining it with the predecessor of pseudonode s. Let P(i;j) be the even length path on the edges of the simple blossom s connecting the nodes i, j. Assign inner/outer labels to the nodes in P(i;j) starting with an inner label for node j and finishing with another inner label for node i. Push all the newly labelled nodes into the list of unscanned nodes. Check whether any newly outer labelled node is a node of N with null price or is a pseudonode containing a node of NFUN-F with null price; perform procedure 7: type 4 augmentation and return. Check whether any newly inner labelled node is a node of N- with null price; perform procedure 6: type 3 augmentation and return. Check whether any newly inner labelled node is a pseudonode with null node price; perform this procedure 9. Check whether there was any equality edge joining a pseudonode s with an outer node other than its predecessor; for every such an edge perform procedure 1: edge scanning. Return.

27 ). PROOF 01' THE ALCORT'I'1M Theorem 2. If there is no exposed node at the end of the algorithm, the final solution is optimal. Proof. It can be easily verified that properties I are satisfied throughout the algorithm; since there is no exposed nodes at the end of the algorithm, the final solution is primal feasible, dual feasible, and satisfies the complementary slackness conditions. Therefore, it is an optimal solution for the problem. Theorem 3. At each execution of the dual solution change step, the dual objective value strictly increases. Proof. It can be easily verified that conditions I are satisfied before each execution of the dual solution step. It follows that the variable h is always strictly positive or some condition would be violated. By the way the dual solution change is performed, the dual objective value increases by the positive amount (# exposed nodes). 6 Theorem 4. If there is an exposed node at the end of the algorithm, then the problem is infeasible. Proof. The algorithm stops with exposed nodes only if 6 =oo. This implies that the dual problem is unbounded and therefore the primal problem is infeasible.

28 2 Theorem 5. The time complexity of the algorithm is at most O(n m). Proof. At each augmentation at least one original node becomes nonexposed and all nonexposed nodes remain nonexposed. Since there are at most n original nodes which are exposed at the beginning of the algorithm, it is possible to occur at most n augmentations during the execution of the algorithm. Based on the facts that between two consecutive augmentations: 1) there are at most n/2 pseudonodes at any time 2) a simple blossom shrinking produces an outer labelled pseudonode 3) a pseudonode unshrinking is performed on an inner labelled pseudonode and produces at least one inner labelled node 4) a node labelling produces an outer-inner pair of labelled nodes 5) labelled nodes remain labelled while they are current it follows that there are at most n/2 node labellings, at most n/2 simple blossom shrinkings, and at most n/2 pseudonode unshrinkings between two consecutive augmentations. Finally, between two operations of labelling, shrinking, or unshrinking, there is at most one execution of the dual solution change step, which requires an effort O(n+m) to be performed. In short, there are 0(n) augmentations, 0(n) dual solution changes per augmentation, and an effort 0(n+m) at each execution of the dual solution change step. So, the overall time complexity is at most 0(n m) [assuming m > n ].

29 C ommnent It is possible to have an implementation with time complexity O(n ). Such an implementation for the minimum cost 1-perfect matching is presented by Lawler [6] and the same approach can be applied for the minimum cost 1-matching/covering problem. Essentially, it consists of spending an effort O(n) at each dual solution change; this means that only the nodes are examined during the dual solution change step at the moment the variable 6 is computed. This implies that the examination of the edges should be done before, at the same time that the edges are being scanned during the tree growing process. Essential edge information must be transformed and stored as node information. In addition, the simple' blossom shrinking and the pseudonode unshrinking operations become more complex because more information associated with the nodes need to be updated. Finally, after each augmentation, all alternating trees must be erased and new alternating trees should be rooted and grown again.

UNIVE SITY OF MICHIGAN 3 9015 047 7468 REFERENCES 1 - J. Edmonds, "Paths, Trees, and Flowers", Canad. J. Math. 17(1965), 449-467. 2 - J. Edmonds, "Maximum Matching and a Polyhedron with 0,1 Vertices", J. Res. NBS 69B(1965), 125-130. 3 - J. Edmonds and E.L. Johnson, "A Well-Solved Class of Integer Linear Programs" in: "Combinatorial Structure and Their Applications", R. Guy (ed.), Gordon and Breach, New York, 1970, 89-92. 4 - J. Edmonds, E.L. Johnson, and S.C. Lockhart, "Blossom I: Computer Code for the Matching Problem", IBM T.J. Watson Center, Yorktown Heights, New York, 1969. 5 - J. Edmonds and W. Pulleyblank, "The Matching Problem and the Blossom Algorithm", lecture notes, The Johns Hopkins University (1975). 6 - E.L. Lawler, "Combinatorial Optimization: Networks and Matroids", Holt-Rinehart-Winston, New York, 1976. 7 - E. Minieka, "Optimization Algorithms for Networks and Graphs", Dekker New York, 1978. 8 - K.G. Murty - manuscripts for Combinatorial Programming. 9 - K.G. Murty and C. Perin, "A 1-Matching Blossom Type Algorithm for Edge Covering Problems", tech. rept. 79-6, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1979. 10 - C. Perin, "Matching and Edge Covering Algorithms", Ph.D. dissertation, Dept. of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1980. 11 - L.J. White and M.L. Gillenson, "An Efficient Algorithm for Minimum k-Covers in Weighted Graphs", Math. Prog. 8(1975),. 20-42.