M A T C H I N G S W I T H A SIZE C O N S T R A I N T Bo Zhou B. Sc., Beijing Institute of Technology A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E O F M A S T E R OF SCIENCE in T H E F A C U L T Y O F G R A D U A T E STUDIES DEPARTMENT OF MATHEMATICS We accept this thesis as conforming to the required standard T H E UNIVERSITY O F BRITISH COLUMBIA September, 1990 © Bo Zhou In presenting this degree at the thesis in partial fulfilment of University of British Columbia, I agree freely available for reference copying of department this or publication of and study. this his or her Department The University of British Columbia Vancouver, Canada DE-6 (2/88) that the representatives. may be It thesis for financial gain shall not permission. requirements I further agree thesis for scholarly purposes by the for an advanced Library shall make it that permission for extensive granted is by the understood be that allowed without head of my copying or my written Abstract We study the matching problem and some variants such as 6-matching and (g, /)-factors. This thesis aims at polynomial algorithms which in addition have other properties. In particular, we develop a polynomial algorithm which can find optimal solutions of each possible size for weighted matching problem, and a strongly polynomial algorithm which can find a (g, /)-factor of fixed size. 11 Table of Contents Abstract ii ACKNOWLEDGEMENTS v 1 , Introduction 1 2 1.1 Introduction 1 1.2 Definitions 1 1.3 Outline of The Thesis 4 Fixed Size Weighted Matching 6 2.1 Preliminaries 6 2.2 Variable Size Weighted Matching 10 2.3 Fixed Size Weighted Matching 17 2.4 A Transformation Approach 21 3 The Fixed Size Weighted 6-matching Problem 3.1 3.2 23 The Weighted 6-matching Problem 23 3.1.1 Introduction and Definitions 23 3.1.2 Characterization of the Optimal Solution 25 3.1.3 The Blossom Algorithm 27 3.1.4 About Complexity 34 The Fixed Size Wighted 6-matching 35 3.2.1 35 A Possible Generalization iii 3.2.2 A Transformation Approach 36 4 Fixed Size (g, /)-Factor Problem 4.1 4.2 4.3 4.4 39 Preliminaries 39 A n /-Factor Algorithm 40 4.2.1 Network Flow Formulation 40 4.2.2 Symmetrizing a Directed/-Factor 41 4.2.3 Algorithm for Finding an Alternating Walk 44 4.2.4 /-Barrier 47 Fixed Size (g, /)-Factor 48 4.3.1 Network Flow Formulation 48 4.3.2 Symmetrizing a Directed Size 2p (g, /)-Factor: Phase One . . . . 48 4.3.3 Symmetrizing a Directed Size 2p (g, /)-Factor: Phase Two . . . . 51 4.3.4 Fixed Size (g, /)-Barrier 54 Augumenting Walk Theorem 57 Bibliography 61 iv ACKNOWLEDGEMENTS I am greatly indebted to my advisor, R.P. Anstee for suggesting this topic, for his guidance and criticism, and his patience with me throughout the preparation of this work. I also thank S. Thomas McCormick for reading the manuscript, and providing much constructive advice. I express my gratitude to the University of British Columbia and the Natural Sciences and Engineering Research Council of Canada for their generous financial support. v Chapter 1 Introduction Introduction 1.1 The renowned weighted matching, weighed b-matching, and (g, /)-factor problems are all well solved in literature, and a number of algorithms for each of these problems already exist. The motivation of this thesis is to add a constraint to each of these problems which forces our optimum solutions to have a fixed size. We study how this extra constraint affects the original problems. Algorithms are established or modified to handle these new problems, and transformation techniques are also explored either to solve the new problems or prove some theorem. 1.2 Definitions This section will present notation and definition of many concepts used throughout this thesis. • A graph G = (V(G), E(G)) is a finite set of vertices V(G), and a finite set of edges E(G). Each edge e,j in E(G) is a set of two vertices {vi,Vj}. Each edge e,j is said to be incident to v, and Vj. Edge is called a loop if u, = Vj. Usually we denote a graph by G = (V, E). • A graph without loops is called a simple g r a p h . If we allow more than one edge between any pair of vertices u, and Vj, then a simple graph with such multiple edges is called a m u l t i g r a p h . The Figure 1.1 shows a multigraph with a loop. 1 Chapter 1. Introduction 2 Figure 1.1: A multigraph with a loop To simplify the exposition, we assume G has no loops throughtout this thesis, this does not fundamentally change the problem. • A weighted g r a p h G = (V, E, c) is a graph with a real number c associated with tJ each edge e,j, where c = (c,j : e,_, G E) is understood as a vector. • A walk in G is a non-null sequence w = u e u e V2 • • • ^k ki whose terms are alterv 0 nately vertices and edges, where edge 1 1 2 = {u , t for each i. We say that w is a walk from vq to Vk of length k. Vertex vq is called the o r i g i n of w, and Vk is called the t e r m i n u s of w. • A walk is called a t r a i l , if the edges e , e-i,..., t of w are distinct. It is called a p a t h if, in addition, the vertices Vo, u u , . . . , Vk are also distinct. l 5 2 • A walk is called a cycle if vq = Vk and the vertices v\, V2,..., Vk are all distinct. • A graph H = {V{H),E(H)) is a s u b g r a p h of G = (V,E) if V(H) = V, and E(H) C E. For V C V , a graph with vertex set Vo, and whose edge set is the set 0 of edges of G that have both ends in V is called the subgraph of G i n d u c e d by V 0 and is denoted by G[VQ]. 0 er 1. Introduction 3 Two vertices u and v of G are said to be c o n n e c t e d if there is a path from u to v in G. Connection is an equivalence relation on the vertex set V. Thus there is a partition of V into nonempty subsets V i , V2, V3,V such that two vertices u r and v are connected if and only if both u and v belong to the same set Vj-. The subgraphs G^Va], G/fV^L • • • >G[V ] are called c o m p o n e n t s of G. If G has exactly r one component, G is connected. The d e g r e e degc(v) of a vertex v in G is the number of edges of G incident to v. It is a fundamental fact that half of the sum over all the vertex degrees is equal to the number of edges in G. This fact will be used in the last chapter. The a d j a c e n c y m a t r i x of a graph G = (V, E) is the |V\ x | V | matrix A(G) — (a,j), in which a tJ is the number of edges joining u, and Vj. If G has no loops, then A(G) has zeros entries on the diagonal. A subset M of E is called a m a t c h i n g in G = (V, E) if no two edges of M are incident to the same vertex. A b - m a t c h i n g of G — (V, E) is an assignment of integers to the edges of G so that the sum of the weights on the edges incident to a vertex v is at most b (b denotes v the vectors of 6„'s). When b = 1 for all vertices v in G , then 6-matchings are the v usual matchings. An / - f a c t o r is a subgraph of G with degree /,• at the ith vertex for i = 1,2,..., n. A /)-factor is a subgraph of G with degree di at the ith vertex, where < <f, < /,, for i = 1,2, . . . , n . A vertex v is M - m a t c h e d if there is some edge of M incident to v, otherwise v is M-unmatched. Chapter 1. Introduction • A n M - a l t e r n a t i n g p a t h in G is a path whose edges are alternately in E\M 4 and in M. • A n M - a u g u m e n t i n g p a t h in G is an M-alternating path whose origin and terminus are M-unmatched. In general, we just say it is an augumenting path if no confusion may occur. If M is a b-matching in G, this concept can be generalized to M - a u g u m e n t i n g W a l k . If the given graph is not a weighted graph, we usually call a matching (or 6-matching) M a cardinality matching (or 6-matching), otherwise we call it a weighted matching (or 6-matching). A l l of the optimization problems discussed here are finite and thus enumeration would always find an optimum solution, but with increasing problem size, enumeration is impractical. At present it is well accepted that a practical algorithm should have its elementary computation steps bounded by a polynomial in term of the problem size. We call such algorithm a p o l y n o m i a l a l g o r i t h m , which were called good algorithms by Edmonds in 1965. For graph related problems, a good measure of problem size is their natural sizes such as the number of vertices, or the number of edges or the size of weighted vectors . . . etc. A polynomial algorithm for a graphical problem is called a s t r o n g l y p o l y n o m i a l a l g o r i t h m if the polynomial is in term of only the number of vertices and the number of edges in graph G . Further details on Complexity Theory can be found in Papadimitriou and Steiglitz [9]. 1.3 O u t l i n e of T h e Thesis Algorithms, complexity analysis, and transformation techniques for the Fixed Size Matching problems are presented in this thesis. The contents of each chapters is summarized Chapter 1. Introduction 5 below. • Chapter Two deals with the fixed size weighted matching problem. A primal-dual algorithm is demonstrated to solve the variable size weighted matching problem in polynomial time. The algorithm has the property that at any step, if there are p edges in the matching, then those p edges constitute an optimum matching of size p. Thus p is regarded as a variable in the algorithm. Then we show how to use this algorithm to find a fixed size optimum matching, and a small example is worked out. Finally an alternative approach to solve the fixed weighted matching problem is also given. • Chapter Three tackles the fixed size weighted b-matching problem. First, we rewrite Pulleyblank's [8] blossom algorithm for the weighted 6-matching problem to obtain experience . Then we transform our fixed size weighted fr-matching problem into a weighted 6-matching problem which thus can be solved by the blossom algorithm. • Chapter Four is devoted to fixed size (g,/)-factor problems. We first review Anstee's [1] /-factor algorithm, then apply his ideas to our fixed size (g, /)-factor problems. We consider our approach a direct one and hence perhaps more practical than a transformation approach. We can either find a fixed size (<?, /)-factor or display a fixed size (g, /)-barrier showing that no fixed size (g, /)-factor exists and do this in 0 ( n ) operations, where n is the number of vertices of a multigraph. 3 At the end we prove an augumenting walk theorem which leads to a conclusion that the size of all feasible (g, /)-factors forms an interval, that is, we can start with a (<7, /)-factor found by any known algorithm and apply our augumenting (or decreasing) walk algorithm to achieve the fixed size p if a (g, /)-factor of size p exists. In particular, we can find the largest and smallest cardinality (g,/)-factor. Chapter 2 Fixed Size Weighted Matching 2.1 Preliminaries Given a weighted graph G — (V,E,c) with weight vector c = (c,j : {i,j} G E) and | V | = n, the general weighted matching problem is to find a matching of G with the largest possible sum of weights. The problem can also be stated as an integer program as below. Max c x T subject to: xij e{o, l}, where x,j = 1 iff edge {i,j} constraints x tJ Vx {j e E is in the matching. We cannot ignore these explicit integer G {Oil} and solve the problem via linear program since we may obtain a nonintegral solution which does not correspond to a matching. See Figure 2.2 for an example. If we let c = 1 on our pentagon, then the unique maximum weighted solution without integer constraints is x\2 = %23 — £ 3 4 = ^45 = £51 = 0.5, which has weight 2.5. However the weight of a maximum weighted integer matching is clearly 2. It is well known that the odd cycles of a graph cause this problem. Edmonds [5] found that the following set of linear constraints are sufficient to ensure integrality. For any subset of 2r + 1 vertices there can be at most r matched edges with both ends in the 6 Chapter 2. Fixed Size Weighted Matching 7 Figure 2.2: subset. This leads to a linear programming (LP) without explicit integrality constraints whose associated polyhedron has only integer vertices. The L P formulation is: Max c x T subject to: E,-j s x - < s , WS C V,\S \ = 2s + l (2) Xij > 0, (3) e fc 0 fc k Vxn e E, k k We choose Sk to be any subset of { l , 2 , . . . , n } which has cardinality that is odd and greater than one, so we have N = 2 n _ 1 — n subsets in total. One may not feel comfortable with these exponentially large number of new constraints. However, this causes no trouble for Edmonds' primal-dual algorithm in which all but a polynomial number of the dual variables have zero value throughout the algorithm. Before moving on we need to review some result and concepts about the cardinality matching problem. Theorem 2.1 (Berge 1957): A matching M is of maximum cardinality if and only if there exists no augumenting path. The proof is not hard, but we will skip it because it is a special case of the augumenting walk theorem that we prove in Chapter 4. Definitions: Chapter 2. Fixed Size Weighted Matching 8 - t Figure 2.3: A n example of augumenting tree A n a l t e r n a t i n g tree w.r.t. a matching M is a tree that satisfies conditions 1, 2 and 3 below. 1. Exactly one vertex of the tree is unmatched, which is called a base (or root) of the tree. 2. A l l paths from the base are alternating paths. 3. A l l maximal paths from the the base are of even length. 4. At least one path from the base is an augumenting path. A tree which satisfies conditions 1, 2 and 4 is called an a u g u m e n t i n g tree (see Figure 2.3). Throughout this thesis we always use straight lines to denote the edges not in the matching and zigzag lines to denote the edges in the matching. A n i n n e r vertex of an alternating(or augumenting) tree is a vertex which is at the end of a path of odd length from the root, and an outer vertex of an alternating (or augumenting) tree is a vertex which is at the end of a path of even length from the root. A blossom B w.r.t. a given matching M is an odd cycle consisting of 2r -f 1 edges and 2r + 1 vertices, where r of the edges are in M. Chapter 2. Fixed Size Weighted Matching 9 d> Existing Blossom New Blossom Figure 2.4: A n example of blossom construction In the cardinality matching algorithm, when a blossom is found it is shrunk into one vertex which is called pesudovertex. We could have a nest of blossoms, and a blossom not contained within some other blossom is called an outermost blossom. A n example is given in Figure 2.4. A blossom tree is an alternating tree with one additional edge joining two outer vertices of the tree. A H u n g a r i a n tree is an alternating tree for which any edge incident to an outer vertex is also incident to another vertex of the tree. The cardinality matching algorithm is initialized by specifying an initial matching, possibly empty, and proceeds by searching for an augumenting path. A tree rooted at an unmatched vertex r is grown by adding non-matched and matched edges alternately, shrinking blossoms whenever encountered. Finally we either find an augumenting path or end up with a Hungarian tree. In the first case we can produce a new matching with cardinality increased by one by tracing the augumenting path (expanding a pseudovertex, if discovered, into the original blossom) back to the root and then interchanging the role Chapter 2. Fixed Size Weighted Matching 10 of matched and non-matched edges along the path. In the second case, we know that no augumenting paths starting from r will exist any more. Clearly one iteration of the algorithm takes 0(|-£|) operations since we need only to look at each edge 0 ( 1 ) times. To find a maximum cardinality matching, we only need to grow n trees, so the total complexity is 0(|V~||£|). In this chapter we add a size constraint to the weighted matching problem, and we explore the primal-dual procedure with an extra dual variable a . 0 Our algorithm has the property that at any step if there are p edges in the matching, then these p edges form an optimum matching of p edges. Urquhart [10] (1967) briefly explained a weighted matching algorithm with this property using geometric intuition in his P h . D . thesis; this algorithm is actually the same as the one in Lawler's book [6], (1976). However another primal-dual version of the weighted matching algorithm given by Papadimitriou and Steiglitz [9] doesn't have this property, and one can find a counterexample with no difficulty. 2.2 V a r i a b l e Size W e i g h t e d M a t c h i n g We add a size constraint to the weighted matching problem and formulate the new problem into L P form as: (P): Max c x T subject to: <*o : Ei<j *ij = P • (4) E" i^+2/i = l, VieV (5) = nt : Etjgs* H + k = 8 , X VS C V, \Sk\ = 2s + 1 (6) z k xn > 0, yi > 0, k z > 0, k k Vi,j,k. Chapter 2. Fixed Size Weighted Matching 11 Here p is any positive integer which can be thought as an variable, y,-,^ are slack variables, and oro, a,, rjt are the corresponding dual variables. The dual (DP) of the above (P) is: (DP): Min pctQ + £<*< + £ s^k subject to: V { M ' } 6 E : ct + oti + aj + J2 0 a free; 0 a,- > 0 Vi; r i<jeSk k >c {j (7) > 0 Vfc. Now we define •Je = ( = '• <*o + <*i + « j + E.jes,, * = c } e r e J = {fc r = 0} 6 J m : (8) (9) k = {i : a,- = 0} (10) Here J is called a set of admissible edges, and Jb is called a set of admissible odd e sets. We use Jb to denote the set of all odd sets not in Jj,. Our algorithm will solve the problem by starting from the feasible dual solution a = max{cij} 0 7T : < a, = 0 Vt 6 V r = 0 \/k k Then we consider the following restricted primal (RP). (RP): Max-xg subject to: Chapter 2. Fixed Size Weighted Matching 12 Et<j ij ~r o — P (11) E?=i xn + Vi + xi = 1 (12) x x (13) 3^ = 0 V i = 0 z = 0 k *u > 0 (14) V{i,j}eJ e Vi € 7 (15) m V5 € 7 fc (16) 6 Vi, j € V ( G ) x > 0 a Note that (RP) is in fact a Phase I L P , and the x°'s are Phase I artificial variables. We know by the Complentary Slackness (C.S.) that a feasible x = ( x tJ : {i,j} G E) in (P) is optimal if and only if it satisfies (C.S.): Exn=p <W0 xn = 0 V{i,;}^J Vi = 0 Vi £ J zk = 0 V5 g J e (18) (19) m fc (17) 6 (20) So we attempt to solve (RP); if we find an optimal solution of (RP) with zero value then this solution is feasible in (P) and satisfies the above C.S. conditions (17-20). Thus it must be an optimal solution of (P). If we find the optimal solution of (RP) is strictly negative then we will adjust our initial feasible dual solution 7r to a new feasible dual solution 7r' S O that the new (RP) induced by n' will have an improved optimal solution. We keep performing this cycling process until we find an optimal solution of (RP) with zero value or we end up with an optimal solution of (RP) with nonzero value which implies that no matchings of size p exist. Note our algorithm always preserves primal and dual feasibility as well as the C.S. conditions, except (4). When the algorithm terminates, if (4) is satisfied then we obtain an optimum matching of size p, otherwise we conclude Chapter 2. Fixed Size Weighted Matching 13 there doesn't exist a matching of size p. Before solving (RP), we need to present its dual as follows. (DRP): Min p a + E «i + £ Sk?k 0 subject to: Ve = {i,j} a ^ -1; 0 o7 > 0 eJ : a + 67, + a,- + Ei,,es* r* > 0 e 0 a, > - 1 ; Vi G J ) 0 m (21) r > -1; k r >0 k Vfc G J . 0 We solve (RP) as maximum cardinality matching problem and preserve the following assumptions: (a) : x G {0,1}, i.e., x corresponds to a matching M. e (b) : r > 0 G[S ] has precisely s edges of M. k k k (c) : r,-, r, > 0 and S f| Sj ^ 0 =• 5,- C Sj or 5 7 C 5,-. t We work in an admissible g r a p h Gj corresponding to J and Jj. Graph Gj consists of e the graph (V, J ) after shrinking all odd sets in J&. We call a matching of G = (V, J ) e e e p r o p e r if all odd set in Jb are full (assumption (b) holds). A maximum proper matching of G need not be a maximum matching of G . e e The following lemma ensures that we can find a maximum proper matching in G by finding a maximum matching in Gj. e L e m m a 2.2: There is a matching in Gj with d unmatched vertices iff there is a proper matching in G with d unmatched vertices. e P r o o f : From a proper matching in G , we can go to a matching in Gj by simply e shrinking maximal odd sets in J j ; this doesn't change the number of unmatched vertices since we start with a proper matching in which all odd sets in J j are full. Conversely, a matching in Gj can be turned into a proper matching of G by expanding odd sets e and filling them with matching edges as appropriate. Since each odd set comes from Chapter 2. Fixed Size Weighted Matching 14 the shrinking of a nest of blossoms, an odd set is unmatched only if some blossom of those contains an unmatched vertex. A n alternating path from the unmatched vertex will allow any specified vertex in the odd set to be unmatched when the blossoms are expanded; the lemma then follows. Q.E.D. Now we can apply cardinality matching algorithm on Gj to find a maximum cardinality matching, but how is this matching related to the optimal solution of (RP)? T h e o r e m 2.3: A n optimal solution {xij} of (RP) is just a maximum proper matching of G , namely, a maximum cardinality matching of Gj. e P r o o f : Suppose we have found a maximum matching of Gj by the cardinality matching algorithm. Thus we have failed to discover an augumenting path in a current graph G , resulting from Gj by shrinking a number of blossoms (be aware of the sequence c G e = (V, J ) e — > Gj —• G )c The vertex set of G consists of pseudovertices. A c pseudovertex can be any of following: 1. A vertex of V . 2. A maximal odd set in J j . 3. Several vertices of V and maximal odd sets in Jf, merged into an outermost blossom. A pseudovertex of G can be either outer or inner or neither. Let 0 be the vertex set of c outer pseudovertices, and I be the vertex set of inner pseudovertices. We then partition the vertices of G that are not vertices of V into <J>o ( maximal odd sets corresponding c outer pseudovertices or blossoms), (maximal odd sets corresponding to inner pseu- dovertices), and the rest. L P theory says if a primal feasible solution and a dual feasible solution both have the same objective value, then both are optimal. We are going to prove the optimality of Chapter 2. Fixed Size Weighted Matching 15 (RP) by exhibiting a feasible solution of (DRP) that achieves the same cost. We define our solution of (DRP) as: W = ( a o , ^ , . . . , c 7 „ , r i , r , . . . ,r ) 2 where N a = -1 0 i a, = < 1 i 1 O G G k -1 / else 1/2 S G $o 0 else. This definition of W is different from that in the primal-dual algorithm given in [6] and [9]. Why is this feasible? The constraint (21) can be violated only if Vi,Vj G O, but this means V{ and Vj belong to the same outer pseudovertex (they cannot belong to different outer pseudovertices since then the two pseudovertices would form a blossom), hence rk — 1 offsets d7 = —1 and salvages its validity. A l l the other constraints of (RP) are 0 obviously satisfied. Why is this optimal? With the assumption (a), we may forget about the constraint (12) in (RP). Since if i £ J , m vertex i is matched, t/,- = xf — 0. If i G J , we can let m Hi = 1 to fill the gap and still have = 0. Thus we can always let = 0. Similarly, with assumption (b) we may forget about constraint (13) in (RP) and always assume n+k x = 0- Now consider the objective value of (RP): Yl i x —H n+k x -XQ = — (p — number of edges in the matching) = ~(P ~ E « i - E^jfeFfc) = Po + E « i ' + T,s r . k k Therefore our W is the optimal solution of (DRP), and the theorem is proved. Q.E.D. Chapter 2. Fixed Size Weighted Matching 16 R e m a r k : If there are p edges in the current matching then Xq = 0. A l l feasibility and C S . conditions are satisfied, so these p edges constitute an optimum matching of size p. What if the number of edges in the current matching is less than pi We then need to adjust our dual solution ir to ir' such that ir' = ir + 0W where 6 is determined as follows: 9 = Min(6i, 62,63) 61 = a + a,- + aj - cij \fi, j E O 0 6 = 2(a + a; + aj - ) 2 0 Cij VieO,j 6 =r 3 k <£0\JI \/S e $/ k Our definition of 9 ensures the feasibility of ir', we then solve a new (RP) induced by n'. We repeat the same procedure and each time obtain an improved solution. But how do we know that the algorithm will eventually terminate? Let us examine the complexity of our algorithm. T h e o r e m 2.4: The complexity of our algorithm is 0(pn ). 3 P r o o f : Let's call each search for an augumenting path a step, and the sequence of steps between two successive augumentations a stage. Clearly there can be at most p stages. Now let's bound the number of steps in each stage. A step can only be one of the three types, depending on whether 6 = 6 , 0 = 6 , or 0 = 1 2 63. In the first case, two outer vertices of Gj are joined by a new edge, which means that in the next step we shall discover either an augumenting path or a blossom. Since the shrinking of each blossom decreases the number of vertices of the current graph by at least 2, we can have at most n/2 + 1 steps of this case in one stage. If 9 = 62, a new outer vertex is found in the next step, which means that the number of steps of this case is also bounded by n/2. Finally if 9 = 63, we remove from Jf, an Chapter 2. Fixed Size Weighted Matching 17 odd set Sic that corresponds to an inner pseudovertex of Gj, so the number of such steps in a stage is clearly bounded by the number of odd sets in Jb at the conclusion of the previous stage. But this number is bounded by n/2 by assumption (c). Now we see we have a total of 0(pn) steps, and each step can be carried out in 0(n ) 2 time by the cardinality matching algorithm. The determination of 0, I, $ o , and $ / can also be done in 0(n ) 2 time, as well as the construction of Gj, the calculation of 0 and the variable modification. Therefore the total complexity of our algorithm is 0(pn ). 3 2.3 F i x e d Size W e i g h t e d M a t c h i n g In the primal-dual algorithm given in the previous section, each time we obtain a new dual solution x' = tc + $W, we may have one of the following cases before we have to adjust dual variables again. 1. There is no augumenting path found. 2. There is exactly one augumenting path found. 3. More than one augumenting path is found. When the third case appears, we should pay more attention. If we wants an optimum matching of size p and there are r < p edges in the current matching, suppose we fail to find any more augumenting paths and have to adjust to a new dual solution 7T* = n + &W. After doing so, if we suddenly find q augumenting paths simultaneously before we have to adjust dual variables again, and r + q > p, then what should we do? T h e o r e m 2.5: We can pick any p — r among these q augumenting paths and still obtain an optimum matching of size p. Proof: At the beginning we take the initial dual variable on each vertex to be zero, i.e. V i 6 V cti = 0. In any later steps, each time we look for an augumenting path on Chapter 2. Fixed Size Weighted Matching 18 Figure 2.5: Gj we start from an unmatched vertex i with a, = 0; if an augumenting path can be found, the path must terminate at an outer vertex j also with aj = 0. If any one of i and j is a pseudovertex corresponding some maximal blossom Sk, then S contains at k least one vertex r such that a = 0. So all of our augumenting paths both start from T and end at a vertex with zero dual variable. Therefore, if we pick any p — r among these q augumenting paths we still preserve all the feasibility and C S . conditions, i.e., we are still at optimality. Q . E . D . We are going to work out an example which may help in understanding our primal! dual algorithm in Section 2.2 E x a m p l e : Find a maximum weighted matching of size 4 in the graph in Figure 2.5. S o l u t i o n : At each step, a nonzero value of a, will appear on the corresponding vertex, a = 0 throughout the algorithm, and admissible graph Gj is presented at every step. 0 Step 1: a~i — 0 for i ^ 5,9; a, = 1/2 for i = 5,9. Also, 6 = 1 because of edge {2, X 4}; 6 = 2 because of edge {5, 8}; 63 = 00 because of 2 = 0, and 9 = 1. Edge {5,9} is an optimal matching of size 1. Step 2: a, = 0 for i ^ 2,4,5,9; aj = 1/2 for i = 2,4,5,9. Also, S = 5 because of x edge {3, 8}; <5 = 1 because of edge {5, 8}; 63 = 00 because of 2 = 0 and 9 = 1. A n 5 Chapter 2. Fixed Size Weighted Matching 0 19 CD (D © Q CD © CX ( G) £ Q = 14 > (g) Figure 2.6: Step 1 0 « 0 = is ® © C D @: © Figure 2.7: Step 2 optimal matching of size 2 is {{2,4}, {5,9}}. Step 3: 57,- = 0 for i ^ 2,4,5; a~i = 1/2 for i = 2,4; 57 = 1. Also, 5 = 1 because of 5 X edge {8, 9}; d>2 = 1 because of edge {1, 2}; 63 = 00 because of <&/ = 0, and 5 = 1. Step 4: Q; = 0 for i ^ 2; a = 1; r{ 2 5|8i9 } = 1. Also, Si = 2 because of edge {4, 5}; 62 = 00 because of / = 0; S3 = 00 because of = 0, and 9 = 2. Step 5: 57, = 0 for i = 3, 6, 7,10; a,- = 1/2 for the other vertices. Also, Si = 7 because of edge {3, 7}; S = 2 because of edge {1, 3}, {6, 9} and {9, 10}; S = 00 because of 2 3 $/ = 0, and 9 = 2. A n optimal matching of size 3 is {{1,2}, {4,5}, {8,9}}. Figure 2.10: Step 5 Chapter 2. Fixed Size Weighted Matching 21 = 7 = 2 Figure 2.11: Step 6 Step 6: a, = 0 for i = 6,7,10; a, = 1 for i = 5,8,9; c7j = 1/2 for t = 1,2,3,4; F{5,8,9} = —1. Also, Si = 6 because of edge {6, 10}; 82 = 2 because of edge {2, 6}; 63 — 2 because of Sk £ $1, and 9 = 2. We now have a Hungarian tree, so the algorithm stops. A maximum weighted matching of size 4 is {{1, 3},{2, 4},{5, 8},{6, 9}}. 2.4 A Transformation Approach In this section we provide an approach which transforms the fixed size weighted matching problem into a general matching problem. Let G = (V, E,c) be a weighted graph with | V | = n. G = (V,E,c) We create a new graph such that V • V \J{n — 2p new vertices} E : E\J{{s,i} : i 6 V,all new vertices^} c {cij • € E}, where : max{cij : {i, j} € E] + 1, and Co otherwise. Chapter 2. Fixed Size Weighted Matching 22 n-2p new vertices 6 > 6 Figure 2.12: A n example of graph G See Figure 2.12 for an example. Then we can apply any known algorithm to find a full size maximum weighted matching on G. When this optimum matching is restricted to G, it induces an optimum matching of size p on G. Remark: G has n(n — 2p) more edges than G. So G will be become very dense for small p; we can no longer take advantage of the sparsity (if any) of G. This is particularly relevant if the complexity of Theorem 2.4 is more carefullly calculated with respect to the number of edges as well as the number of vertices. Chapter 3 T h e F i x e d Size W e i g h t e d 6-matching P r o b l e m 3.1 T h e W e i g h t e d 6-matching P r o b l e m In this section, we introduce the blossom algorithm for the weighted 6-matching problem, which is due to Pulleyblank [8]. 3.1.1 Introduction and Definitions Let G = (V, E, c) be a weighted graph, and 6 = (6,- : i G V) be a vector of positive integers. The general weighted 6-matching problem can be formulated in the following L P form: (P): Max c x T subject to: (3.1) (3-2) £? = 1 x <6, r : EijeR k X k (3.3) VieV t j H<k s x >0 tj Vi? C V, fc £ t € ^ 6,- = 2s* + 1 V { i , ; } 6 E. Where ct.'s and r^'s are the corresponding dual variables. D e f i n i t i o n 3.1 A feasible solution x = : {i,j} E E) of the above (P) is called a 6-matching. D e f i n i t i o n 3.2 Given a b-matching x, the deficiency o f a vertex i is 6, — £Tj=i ij x which is denoted by def {i). x Vertex i is called a deficient v e r t e x if def (i) > 0. x 23 Chapter 3. The Fixed Size Weighted b-matching Problem Edge j such that Xj > ] 24 Xj > o ^s^y^. Figure 3.13: Sample Blossom Definition 3.3 A walk w = u e u e U2 • • • e fc_it>2ib-i, where e, = 0 1 1 2 menting walk w.r.t. a b-matching x if v %k > 1 is an aug- 2 0 and u fc-i are both deficient vertices and 2 2 if occur twice) if k is an even edge of w. Definition 3.4 The deficiency of a graph G w.r.t. a b-matching x and its corre- sponding dual solution y = (a,r) is £ >odef (i) yi x which is denoted by &(G;x,y). Definition 3.5 A blossom (see Figure 3.13), w.r.t. a b-matching x, is a connected graph B = (V(B), E(B)) containing no even cycles, exactly one odd cycle C and for which the degree constraints satisfy the following conditions. Let v £ V(C). (3.4) T2 (3.5) E? (3.6) (3.7) =lXij X j = 1 > 1 Xj > 1 = bi VieV(B)-{v} = &„ - 1 V ; e E(B) \/j € E(C), E(C) and j is the even edge of a path in C rooted from v By shrinking a blossom B in the graph G, we mean that all the edges of G which have both ends in B are contracted. We call the resulting vertex s a pseudovertex and define b, — 1. Chapter 3. The Fixed Size Weighted b-matching Problem 25 There is an important property of a blossom, which ensures we can do the shrinking in our blossom algorithm. See the following proposition. P r o p o s i t i o n 3.1 Let B be a blossom w.r.t. a 6-matching x. Then for any i € V(B), there exists a new 6-matching x' that can be obtained from x by an alternating walk such that B is also a blossom w.r.t. x' and def >(i) = 1. x During the course of the blossom algorithm we construct forests having special properties. Let T be a tree contained in G , and r € V(T) be the root of T. Then an edge {i, j} € E(T) is even or o d d according as {i,j} is the last edge of the path in T rooted from r to an outer or inner vertex of T. D e f i n i t i o n 3.6 We call T an a l t e r n a t i n g tree w.r.t. a b-matching x (see Figure 3.14) if (3.8) E"=l Xrj < K (3.9) TlU ii (3.10) {i,j} e E(T) Vx (3.11) Xj > 0 V ; is an even edge of T. x = i b Vt'6F(r)-{r} tj > 0 and i or j g V(T) We call a nonempty collection of alternating trees an a l t e r n a t i n g forest. D e f i n i t i o n 3.7 Let k be an edge of a tree T with root r. If we delete k from T then the resulting graph will consist of two trees, one of which, T', will not contain r. We call T' the p o r t i o n of T above k. D e f i n i t i o n 3.8 A H u n g a r i a n Forest is an alternating forest that can not grow any more. 3.1.2 C h a r a c t e r i z a t i o n of the O p t i m a l S o l u t i o n First let's consider the dual problem (D) of the primal 6-matching problem (P). (D): 26 Chapter 3. The Fixed Size Weighted b-matching Problem P : root. Figure 3.14: Alternating Tree Min £ bicti + £ sr k k subject to: (3.12) a, + aj + j e R f c r > fc C i j V{i, j } G £ ( G ) (3.13) a,- > 0 Vi G V (3.14) r > 0 Vfc. fc The blossom algorithm is also a primal dual procedure: We work on an admissible graph Gj (see Chapter 2 for the definitions of Gj, J , J , Jb, etc.) and find a maximum cardie m nality 6-matching x on G . Then we check if A(G; x, y) = 0. If so, we are at optimality; if not, we adjust our dual solution y = (cti,r ) to y and obtain a new Gj on which we can k find an improved maximum cardinality ^-matching x . We continue this cycling process until we terminate with A ( G ; x , r / ) = 0. We state the C S . conditions of our problem as follows: (3.15) xn > 0 = • a + aj + (3.16) a > 0 => £ ? { { (3.17) r > 0 = > £ k i = 1 j € j e R k Xij = k ^ Xij; r = c k tj V{i,j} G E Vi G V = s k V/? fc Chapter 3. The Fixed Size Weighted b-matching Problem 27 The blossom algorithm always preserves all the primal and dual feasibilities, as well as C.S. conditions except (3.16). At each stage of the algorithm, we have a 6-matching x = (xij : {i,j} G E) and a feasible dual solution y = (a,-,rjt : Vi,i2jk). Define G {x) = (V(G), E {x)) where E {x) + + + = {{», j} G E(Gj) : x {j > 0}, and let H be any component of G (x). Then H has the following properties: + (3.18) H contains no even cycles; (3.19) H contains at most one odd cycle; (3.20) if H contains an odd cycle, then H contains no deficient vertices; (3.21) if H contains no cycles, then H has at most one deficient vertex. We also have an alternating forest F contained in Gj such that (3.22) Each i G V such that J2]=i ij < °i x Forest F is partitioned into F° and F : l iS the root of a tree in F. F° consists of all those trees in F such that a = 0 if the root r G V or a, = 0 if the root r C V is a pseudovertex and t E r ; and F 1 r consists of all other trees of F. Then (3.23) A((7; x, y) = £ def (i) = Yl(def (i) : i is the root of a tree of F ) 1 a i > 0 x x It will be seen in the algorithm that as long as there are vertices in F , we are not 1 at optimality, and as soon as V(F ) = 0, namely A ( G ; x , y ) = 0, we implictly have an 1 optimal solution. 3.1.3 The Blossom Algorithm (3.24) Initially we may take rr,^ = 0 G E, a,- = 1/2 max {c : {i,j} tJ G E}, and rfc = 0 Vi?*. F will be the spanning forest of G in which every tree consists of a single outer vertex. Part One: Cardinality Matching Algorithm. Chapter 3. The Fixed Size Weighted b-matching Problem 28 ©: vertex not in forest r Figure 3.15: Forest Growth Step 1: Scan E(Gj) to find an edge j = {vi,V2} joining an outer vertex v t of F x to a vertex v that is not an inner vertex of F . If no such edge exists, then the current 1 2 forest is Hungarian; go to Step 8. Otherwise, go to Step 2. Step 2: Examining Vertex v . 2 If v is in a component of G (x) which is not contained in F, go to Step 3. + 2 If v is an outer vertex of a tree in F which is different from the tree containing Vi 2 then go to Step 4. If v\ and v belong to the same tree of F , go to Step 5. 2 If v is 2 a n inner vertex of a component of F°, go to Step 7. Step 3 (Grow Forest F): Let K be the component of G+(x) containing v . 2 If K contains a cycle, go to Step 3b. Step 3a (see Figure 3.15): If K contains no cycle, we grow the alternating tree T containing v\ by attaching v and K by means of the edge j. Go to Step 1. 2 Step 3b (see Figure 3.16): K contains an odd cycle C. Let Wi be a vertex of C which is an odd distance from v in K and for which this distance is as short as possible. 2 Let w be a vertex of C adjacent to w\ in C which is no closer to v in C than W\. Let 2 2 k be the edge of C joining W\ and w , and K' be the tree obtained from K by removing 2 Chapter 3. The Fixed Size Weighted b-matching Problem 29 Figure 3.17: Two Tree Augmentation the edge k. A d d K' to the forest by using edge j as described in Step 3a. Go to Step 5. Step 4 (see Figure 3.17): Augmentation (Two Trees). Step 4a: Calculation of cr. Let r (r ) be the root of the tree I \ (T ) of F (F) containing (u ). Let cr = min l x 2 2 2 x {xk} where k is an even edge of the path 7Ti in Ti from r to v\; let <r and 7r be analogously t 2 2 defined for T , v and r . By (3.11) c ^ , ^ > 1. Let cr = min {<Ti, <J, def (ri), 2 2 2 By (3.8), cr > 1. Step 4b: Augmentation. 2 x def (r )}. x 2 Chapter 3. The Fixed Size Weighted b-matching Problem 30 Figure 3.18: One Tree Augmentation Define x to be the new 6-matching obtained from x by subtracting cr from x if k is k an even edge of tti or TT and adding cr to x 2 k if k is an odd edge of 7Ti or 7r, or k = j. 2 Then &(Gj;x',y) < A(Gj;x,y) - 1. Step 4c: Computation of new F. If def '(r ) x = 0 (resp. def <(r ) = 0) then remove Tx (resp. T ) from F . If x x even edge of 2 2 is an or 7r for which a:^ = 0 then remove k and the portion of the tree above 2 it from F. Go to Step 1. Step 5 (see Figure 3.18): Augmentation (One Tree). Step 5a: Calculation of cr and Blossom Test. Let r be the root of the tree of F containing v and u . Let tti (7r ) be the path in T 1 x 2 2 from r to v (v ). Let tt be the common position of n\ and 7r . Then E(-k ) \JE(ir ) x 2 s x 2 2 U{j}\ E(ir ) are the edges of an odd cycle C. a Define <7i•= min {x : k is an even edge of ir }, and cr = min {x : k is an even edge k 3 of 71"! or 7r and k ^ E(w )}. 2 s Then <TI,<T <r = min 2 — 2 1- Let {[cr /2},cr ,[def (r)/2]}. 1 2 x k Chapter 3. The Fixed Size Weighted b-matching Problem 31 Where [a] denotes the largest integer no greater than a. If a > 1 then go to Step 5b where we augment; otherwise, go to Step 6 where we shrink a portion of Gj. Step 5b: Augmentation. Define x to be the new 6-matching obtained from x by subtracting (adding) cr from (to) Xk if k is an even (odd) edge of TTI or 7r not belonging to w , and subtracting (adding) 2 3 2cr from (to) x if k is an even (odd) edge of w . Then k 3 A{Gj;x',y) < A(Gj;x,y)-2. Step 5c: Computation of new F. If def '(r) = 0 then remove T from F and go to Step 1. x If def >(r) > 0, but there are / £ E(tt ) 3 x such that x\ = 0, let k be the first such edge in 7T , and T' be the portion of T above k. Remove T' and k from F and go to Step 1. S If def >(r) > 0 and x\ > 0 for all / £ E(tr ), but x' = 0 for some edge & of C , remove x 3 k all such edges k from F and go to Step 1. Finally, if def >(r) > 0 and x\ > 0 for all / £ £(TTI) U £ ( x ) U{i}> then there must be x 2 an even edge k of ir for which x' = 1 or def >(r) = 1. Go to Step 6. 3 k x Step 6: Shrinking Step (see Figure 3.19). We now identify a blossom in Gj. T is the tree of F 1 containing v and u , and tt x 2 3 is the path in T from its root r to the nearest vertex q of C , the odd cycle formed by adding j to T. Let w be the first outer vertex of tt such that the path it' in T from w to s contains no even edge k for which x k < 2. Note 7r' could be empty. Let C' = x (J C; we regard C ' as an odd cycle in the sense that we split each vertex of 7r', except for w, into two vertices and split the edges of x' properly. Then the blossom B consists of C' and any component H of G (x) + such that V(H)f] V(C') ^ 0 except for the even edge of T incident with w if it exists. Note to Step 1. £>eV(B) wj = b — I. Shrink blossom B and go x w Chapter 3. The Fixed Size Weighted b-matching Problem 32 Figure 3.19: Shrinking Step Step 7 (see Figure 3.20): Grow Forest F (pseudo forest growth). 1 Edge j joins an outer vertex v of a tree T\ rooted at r in F to an inner vertex v of 1 x x 2 a tree T rooted at r in F°. Let k be the first edge of the path from t> to r in T , and 0 0 2 0 0 T be the portion of T above k. We adjoin T and the component H of G (x) containing + 0 i>2 to V\ by means of the edge j thereby obtaining a larger tree T[ and a smaller tree T' Q as indicated in Figure 3.20. If r g V(T[), then replace T by T[ and T by T' in F . Go to Step 1. 0 x 0 Q If r 6 V(T ), then remove T from F ° . Let T denote Tj and perform the following 0 X 0 steps. Step 7a: Pseudo Augmentation. Let 7r be the path in T from r to ro- Observe that both ro and r are outer vertices of x x T. Let <7\ = min {xj : j is an even edge of 7r}. Let a = min {a ,def {r )}. x x x Then a > 1. Let x' be the new 6-matching obtained from x by adding (subtracting) a to (from) x^ if k is an odd (even) edge of it. Then Chapter 3. The Fixed Size Weighted b-matching Problem 33 Figure 3.20: Pseudo Forest Growth A(Gj;x',y) < A(Gj;x,y) -1. Step 7b: Computation of new F. If def (ri) x = 0, then remove T from F , reroot T at r , and add T to F°. Go to Step 1 0 1. If def' (r-i) > 0, then we must have x\ = 0 for some even edge of 7r; let k be the first x such edge, and T be the portion of T above k. Remove T and k from T, reroot T at r 0 and add it to F°. Go to Step 1. Part Two: Optimality Test and Dual Variable Change. Step 8: If A(Gj; x,y) = 0, stop: the current 6-matching is optimal. Step 9: Dual Variable Change. Step 9a: Calculation of 9. Let 8i = min {a,- + ctj — c,j} where {i,j} joins an outer vertex of F to a vertex not 1 in F . 1 Let 82 = min 1/2{a; + ctj — c,j} where {i, j } joins two outer vertices of F . 1 Let 63 = min {rjt/2} where Rk is an inner pseudovertex of F . 1 Let 84 = min {a^} where i is an outer vertex of F . 1 Chapter 3. The Fixed Size Weighted b-matching Problem 34 Finally, let 6 = min {<5 6 ,6 ,6 }. l5 2 3 4 Step 9b: Change of Dual Variable. We define new dual solution y = (c^r^) as follows: ai — 9 i is an outer vertex of F . <X = < a,; + 9 i is an inner vertex of F . 1 1 ai otherwise. r + 29 Rk is an outer pseudovertex of F . 1 k r — 29 Rk is an inner pseudovertex of F . 1 k r otherwise. k Then update edge set J by this new dual solution. e S t e p 9c: If 9 G {Si,S }, w e w get new edges in Gj. Go to Step 1. m 2 If 9 = £ 3 , we must properly expand an inner pseudovertex of F for which = 0 and l properly update the new alternating forest F. Then go to Step 1. If 9 = 84, let I = {i : a) = 0} where i is an outer vertex of F . For each i £ I such 1 that i is the root of a tree T,' in F , remove 1 from F 1 and add it to F°. Then go to Step 1. Note that A(Gj;x,y')<A(Gj;x,y)-l. If there is no i £ / such that i is the root of a tree in F , then choose any r G / , and 1 0 let r i be the root of T. Go to Step 7a. 3.1.4 About Complexity A n upper bound on the amount of work required by the blossom algorithm to solve a weighted b- matching problem is of the order A(G;x°,y°).|V|.|F| Chapter 3. The Fixed Size Weighted b-matching Problem 35 where x° and y° are the initial 6-matching and dual solution. The details of the proof are available in Pulley blank [ 8 ] . If we start with an initial 6-matching and its corresponding dual solution as described in ( 3 . 2 4 ) , the blossom algorithm will take 0 ( | 6 | . | V | . | J E | ) operations which is dependent on vector b. So this is not a strongly polynomial algorithm nor indeed a polynomial algorithm in the seting of a multigraph; a strongly polynomial algorithm for weighted 6-matching problem was given by Anstee [ 2 ] ( 1 9 8 3 ) . 3.2 The Fixed Size Wighted 6-matching Let G = (V, E , c) be a weighted graph, V- [j V = be a partition of V , and b = (6,- : i £ V) be a vector of positive integers. Then the fixed size weighted 6-matching problem can be formulated in the following L P form: (P): Max c x T subject to: £t'<j ij x —P Vi g v± £?=! Xij = bi Vi e V= V#* C V, x tj £ bi = 2s + 1 k > 0 Note in the previous section we have taken V~ = 0 for brevity's sake. 3.2.1 A Possible Generalization Conjecture: The fixed size weighted 6-matching problem can be solved by the primal dual algorithm in Section 2 . 2 also. Chapter 3. The Fixed Size Weighted b-matching Problem 36 This conjecture is very likely to be true since there is no essential difference between these two problems. One can exactly follow the same procedure as in Section 2.2: Apply Part One of the blossom algorithm on Gj instead of using the cardinality matching algorithm for the general matching problem, and pay some care to the computation of the dual variable change parameter 9. 3.2.2 A Transformation Approach We explore the same idea used in the previous chapter, namely, we want to transform the fixed size weighted 6-matching problem into a weighted 6-matching problem so that we can solve it by the blossom algorithm in Section 3.1. We create a new graph G = (V, E,c) such that V = V{J{v } 0 E = E\J{{vo,v }:v j j € V±) bo - E i v k - 2p € b=(bi-.iev) c = (cij :{i, j}€ E), where bi={ 6,- Vi e v 6 i= v 0 , and Cij = 0 We create a new problem (P) on (7 as follow: (P): Max c x T subject to: 0,j}e£ 0 otherwise. Chapter 3. The Fixed Size Weighted b-matching Problem 37 No e d g e s f r o m v t o y = Figure 3.21: The construction of (7 E,j ^ x 6 tj <k s Vi? C V s.t. Z fc i e R k bi = 2 ^ + 1 Note we have partitioned V into V~ \J V^, where V~ = 0 (see Figure 3.21). In fact (P) is also a weighted /-factor problem. Theorem 3.2: (P) has a feasible 6-matching iff (P) has one; an optimal 6-matching on (P) induces an optimal 6-matching of (P); conversely, an optimum solution of (P) can be extended to an optimum solution of (P). Proof: 1. Assume x is a feasible matching of (P), and define x as follow: x = (x^ :{i, j} & E) where {i, j}e E Xij bi - E r e v x ir j = v , i E V^. 0 Then £ t < j x^ = bi, Vi € V, so x is a feasible 6-matching of (P); Conversely, if x is a feasible 6-matching in (P), then ( X | G ) is obviously a feasible 6-matching of (P). Chapter 3. The Fixed Size Weighted b-matching Problem 38 2. Let x be a maximum weighted matching of (P), and define x as above. Then x is a maximum weighted matching of (P). If not, assume x* is a maximum weighted matching of (P) such that c x' > c x T T but c x ' = C ^ X ' I G ) > c x , so x is not a maximum weighted matching, a contrar T diction! Conversely if x is a maximum weighted matching of (P), then (x|cr) is a maximum weighted matching of (P). This is also because of c x = c (x| ). T r G Q.E.D. C o m p l e x i t y : Our transformation doesn't increase complexity significantly since we have only added one vertex and at most n edges. R e m a r k : In (P), if we set b = 1 (i.e. 6, = 1 : Vi G V ) , we come to a general fixed size weighted matching problem; when we create the new problem (P), we have b = n — 2p. 0 This transformation is better than the one given the previous chapter if we want to solve this special case weighted fe-matching problem (P) by Pulleyblank's algorithm, since in the previous one, we added n — 2p vertices and n(n — 2p) edges. Chapter 4 Fixed Size (g, /)-Factor Problem 4.1 Preliminaries Let G = (V(G), E(G)) be a multigraph where for each e G E(G), we let u denote the e multiplicity of an edge e in G. We may understand G as a simple graph with a capacity vector u = (u : e G E(G)). e Let g = (g : v G V(G)), v / = (/„ : v G V(G)) be vectors of nonnegative integers satisfying Vv G V(G) : 0 < g < f v < v deg (V), G where dega(v) measures the degree of v in G counting multiplicities. A (g, /)-factor is a subgraph D of G with \/v G V(G) : This might be called a capacitated g < deg {v) < / „ . v D /)-factor since an edge can be used at most u e times. A 6-matching is a /)-factor with g = 0, and an /-factor is a (g, /)-factor with f = g. It is convenient to state the problem in matrix terms. Let G = (V(G), E(G)) have the adjacency matrix u = For the brevity's sake, we do not allow loops in our graph. We wish the row and column sums of an adjacency matrix A to correspond to the degrees of the associated vertices. Then a (g, /)-factor corresponds to a symmetric integral matrix A with zero entries on the diagonal, ith row and column sum is bounded 39 Chapter 4. Fixed Size (g,f)-Factor Problem 40 by (gi,fi) for i = l , 2 , . . . , n and satisfying 0 < A < u. When g = / , a (g,/)-factor reduces to an /-factor for which we require the ith row and column sum to be / , for i = 1,2,..., n. 4.2 A n /-Factor Algorithm A number of algorithms for solving /-factor problems are known. One restriction of the problem is to take the G to be a simple graph with capacity vector u = 1, in which case the /,'s are bounded by n — 1 which is a polynomial in n. However in the general case the / / s are not bounded by a polynomial in n and so this technique will not yield a polynomial algorithm. The algorithm introduced in this section is due to Anstee [1] which solves the problem by either finding an /-factor or showing one does not exist and does this in 0 ( n ) 3 operations. This complexity bound is independent of the size of u or the size of /,'s, and so is strongly polynomial. 4.2.1 Network Flow Formulation Our search for an /-factor is split into two parts. First, network flows is employed to find an integral matrix A with ith row and column sums /,• for i = 1,2,... , n, and satisfying 0 < A < u. We call such a matrix a directed /-factor. If no directed /-factor exists, then clearly no /-factor exists. Second, we are left only with the problem of making A symmetric since our network flows will, because of the lack of loops, automatically give zero entries on the diagonal. We compute an half integral symmetric matrix x = (A + where A T A )/2 T is the transpose of A. Then we eliminate the halves by an alternating walk Chapter 4. Fixed Size (g, /)-Factor Problem 41 algorithm (see Section 4.2.3). If the alternating walk algorithm can not delete all these halves, then we will prove that no /-factor exists by displaying an /-barrier (see Section 4.2.4). A directed /-factor correspond to an integral flow in the following network. There is a source s, a sink t, and nodes i ? R ,..., l5 2 R , Si, S , • • •, S n 2 n There are directed edges from s to Ri and 5, to t both with capacity / , for i = 1,2, . . . , n . There are directed edges from Ri to Sj with capacity Uij for i,j = 1,2,..., n. Assuming there is an integral maximal flow of size /j + f + . . . 4- / 2 n ) form a matrix A = (a,j) from the flow by letting a,j be the flow from Ri to Sj. We deduce that A has ith row and column sum fi and satisfies 0 < A < u and thus is a directed /-factor. Note that our network has \V\ = 2n-f-2 vertices, so a directed /-factor can be obtained in O d ^ l ) = 0 ( n ) operations or OdVH-EI/oglVl) if you wish to take advantage of the 3 3 sparsity of G and hence of our network. 4.2.2 Symmetrizing a Directed /-Factor Let A be a directed f-factor, and form a matrix x = (A + A )/2. T Now x is symmetric, has the the desired row and column sums and satisfies 0 < x < u. Unfortunately, it need not be integral, merely half integral off the diagonal and zero entries on the diagonal. We find that the remaining problem of removing the halves is bounded in that it does not involve the /,'s and only some of the edges of G. One may view the directed /-factor as the bulk of the solution. These are two phases in making A into an /-factor. Define a graph H on the vertices of G with edge {i,j} in H whenever x^ is not integral. Thus we can add or subtract 1/2 from these entries and keep 0 < x < u. Since the row sums of x are integral, we deduce Chapter 4. Fixed Size (g, f)-Factor Problem 42 Figure 4.22: Two cycles in H joined by an alternating walk in G that the degrees of H are even, and so H can be decomposed into closed trails. If H has an even length closed trail, then alternately adding and subtracting 1/2 from the entries of x corresponding to the edges of the closed trail leaves the row and column sums of x unchanged with 0 < x < u. Thus we wish to remove all the even length closed trails from H, which can be done by the following simple algorithm. We call it Eliminating Algorithm One. E l i m i n a t i n g A l g o r i t h m O n e : Start with any path and extend it using the fact that the degrees are even. Eventually some vertex appears twice, yielding a cycle. If the cycle is even, then eliminate it as described; if the the cycle is odd, remove it from the graph but save it. Continue this process, starting over with as much of the original path as was left. If at any point two odd cycles have been found with any vertices in common, then the edges of the cycles can be decomposed into one or more even length closed trails which can be eliminated from H. Thus the algorithm terminates with H consisting of only vertex disjoint odd cycles. The algorithm takes 0 ( | £ | ) operations, since each edge of H can be investigated at most twice. With H consisting of vertex disjoint odd cycles, we start our second phase which is to eliminate the odd cycles from H in pairs as in Figure 4.22. The cycle abode and ghi are in Chapter 4. Fixed Size (g, f)-Factor Problem 43 Figure 4.23: A key example of alternating walk H, but edges {e, / } , {/,<?} are not (they are edges of G). The numbers next to the edges are added to the corresponding entries in x. Row and column sums are preserved, and the operations on the edge {e, / } and {/, g} must be chosen so that after the changes, we still have 0 < x < u. In performing these changes, the two odd cycles of H are removed as described. Note we are always left with even number of odd cycles. Thus we search for walks of edges not in H which always allow us to alternately add and subtract 1 and join two odd cycles of H. Let us define these walks precisely. Consider a walk t>ieii> e u .. .e _iv , 2 2 3 n n where no edges of H are allowed since then we could terminate sooner. The walk will be called an a l t e r n a t i n g w a l k starting at v\ and ending at v if we may perform the following n changes to x and still keep 0 < x < u: add 1 to entry ei, subtract 1 from entry e , add 1 2 to entry e , . . . , or the same series starting with subtraction. We say that the walk ends 3 in addition (resp. subtraction) if we are adding to (resp. subtracting from) entry e _!. n We require our alternating walk to be minimal (not necessarily minimum) subject to these conditions. Thus an edge may be used twice but only if both times we are adding to it or subtracting from it and the second time it appears with its ends in reverse order. See Figure 4.23. Our definition ensures that we can eliminate two odd cycles if they are joined by an alternating walk. Chapter 4. Fixed Size (g, f)-Factor Problem 4.2.3 44 Algorithm for Finding an Alternating Walk Let H consist of vertex disjoint odd cycles C\, C , • •., C . We start at any odd cycle of 2 t H, say C i , and try to find an alternating walk from any vertex of C\ to any vertex of any C for k > 1. This takes 0(n ) 2 k operations and there are at most ra/3 cycles in H, so we need only find n/6 such walks. Thus assuming we are successful in finding the alternating walks, the algorithm will take 0(n ) operations to remove all the odd cycles 3 from H and arrive at the desired f-factor. In the algorithm we form a multigraph G* on the vertices of G with edges in two classes M , M. Because an alternating walk may use an edge at most twice, we will allow up to two edges in each class to join the same pair of vertices. The edges in M correspond to entries for which we may subtract 1 (two edges if we may subtract 2) and edges in M correspond to entries for which we may add 1 (two edges if we add 2) and yet all the while keeping 0 < x < u. We form a directed tree directed out from a base vertex which corresponds to C\. The tree grows vertex by vertex (Step 5). Using the notation p(v) = w to denote that w is the precursor of v in the tree, the directed paths in the tree correspond to alternating walks. The edges of the tree are stored separately from G to keep them from being used again. A vertex is given a label S (resp. T) if there is an alternating walk from a vertex of C\ to the given vertex ending in addition (resp. subtraction). When an edge is added to the tree that creates a cycle it is called a blossom. We shrink the vertices of the blossoms to a single pseudovertex, and there may be nesting of blossoms. A n outermost blossom or pesudovertex in this inductive structure is called exposed. For each blossom, one vertex (possible a pseudovertex) is distinguished as the base vertex, being the vertex of the blossom closest to the base (root) of the tree. If the base Chapter 4. Fixed Size (g, f)-Factor Problem 45 of a blossom is not a pseudovertex then it is called a true base, otherwise the true base is inductively defined as the true base of the base of the blossom. In the shrinking operation, edges joining vertices on the blossom may be deleted as redundant. The edges of the blossom are saved. Further multiple edges may arise in the shrinking process, but for a given pair of vertices only 2 from M and 2 from M could be used, the others could be deleted if desired. We keep track of the original ends of an edge as well as its new ends, which is useful in finding the alternating walk in G from a directed path in the tree. The tree also shrinks but we end up with a tree. We give the pseudovertices labels S,T, and these labels apply to all vertices of G contained in them. Throughout the algorithm, we use the term dual to refer to the replacement of x by e u — x , label S by label T, addition by subtraction, M by M, and vice versa. e e Algorithm for Finding an Alternating Walk • Step 1: Shrink the vertices of C\ in G into a single vertex which forms the base of the tree and gets labels S,T. The vertex is put on the list of unscanned vertices Y. Form a multigraph G* whose edges are divided into two classes M, M. The edges of M consist of Min(x ,2) copies of edge e. We ignore the edges of the odd e cycles of H. The edges of M are given by the dual definitions. • Step 2: If Y is empty, then stop, there is an /-barrier (refer to next section), else, pick a v E Y where u is automatically a vertex of the tree. • Step 3: If v has label 5, do Steps 4 and 5. • Step 4: (searching for blossoms) Search for any edge {v,w} 6 M , where w is in the tree and has label S. If there is such an edge, it forms a blossom in the tree which we shrink to a pseudovertex. The pseudovertex is given labels S,T and is added to Chapter 4. Fixed Size (g, f)-Factor Problem 46 Y. The vertices contained in the pseudovertex are deleted from Y. Return to Step 2. If there is no such edge, continue. • Step 5: (grow tree). For all vertices w not in the tree, do the following. If there is an edge {u, w} £ M, then put w in the tree with p(w) = v, and label T. The chosen edge {v,w} is deleted and w is added to Y. If in addition w 6 C for some k k > 1, then stop. There is an alternating walk from a vertex of C to a vertex of x C. k • Step 6: If v has the label T do the duals of steps 4 and 5. • Step 7: Consider v to be scanned and delete v from Y. Return to Step 2. The algorithm will certainly terminate. The assertions made in Steps 2 and 5 are verified by the following lemmas (for the proofs refer to Anstee [1]). Lemma 4.1: Consider a pseudovertex u with true base b. Then there is an alternating walk in the original G* from b to any vertex of G (not in C ) of the pseudovertex ending x in addition and another ending in subtraction. Both these walks start with addition (resp. subtraction) if the label of p(b) is S (resp. T). If there is no p(u), then we do not care how the walks start since b will corrspond to C\. Lemma 4.2: If a vertex v of G has a label S, then there is an alternating walk from a vertex of C\ to v ending in addition. The dual also holds. Lemma 4.3: If a vertex v is reachable from a vertex of C\ by an alternating walk ending in addition then v will have the label S if the algorithm terminates at Step 2. The dual also holds. Chapter 4. Fixed Size (g, f)-Factor Problem 4.2.4 47 /-Barrier We will only characterize the structure of our /-barrier; for the rigorous proof one should see Anstee [1]. Suppose at any stage we can not find an alternating walk, then we can find an / barrier as follows. Define a vertex y as reachable from a vertex x if there is an alternating walk from x to y. A vertex is considered to reachable from itself by an alternating walk of no edges which can be considered to end in either in addition or subtraction. Assume we were unable to elnminate C\. Define a partition of the vertices of G into sets S, T, U as follow. Let S be the vertices reachable from vertices in C\ only by alternating walks ending in addition, and let T be the vertices reachable from vertices in C\ only by alternating walks ending in subtraction. The remaining vertices U decompose into two sets W, L where W is the set of vertices each one of which is reachable from a vertex of C by an alternating walk ending in addition and from a vertex of Ci by an x alternating walk ending in subtraction. The set L consists of the vertices not reachable from a vertex of C\ and so includes the vertices of C , C 3 , . . . , C . 2 We define an edge {i,j} to be empty (resp. full) if t = 0 (resp. u,j — = 0). Then each edge joining a vertex of S to a vertex of S\J L is empty. Each edge joining a vertex of T to a vertex of T\J L is full. There are no edges in G joining vertices of L to vertices of W. In the subgraph of G induced by the vertices of W, there are components Ui, U2, •. •, Ui. Let Ci C Ui, then every edge joining Ui to S (resp. T) will be empty (resp. full). The same will be true for each Uk (k > 1) with one exceptional edge for each Uk as follows. Either there is an edge {i,j} there is an edge {i,j} with i G Uk, j G S, and x^ = 1 or with i G Uk,j G T, and x,j = 14. A l l these properties plus some network results and computations constitute the proof that no /-factor exists. One can consult Anstee [1] for the details. Therefore, our partition of the vertices of G: S, T, L, Chapter 4. Fixed Size (g, f)-Factor Problem 48 Ui, U21 • • •, Ui is called an / - b a r r i e r . 4.3 F i x e d Size ( y , / ) - F a c t o r Necessary and sufficient condition on the existence of a (g, /)-factor are given by Lovasz [7]. A n 0(n ) algorithm for finding a (#,/)-factor on a multigraph is due to Anstee [3]. 3 This section is mainly my work; I am going to explore the same idea used in the /-factor problem to find a fixed size (g, /)-factor or displaying a fixed size (g, /)-barrier and do this in 0 ( n ) operations. 3 4.3.1 Network Flow Formulation Form a network with a source s , a sink t, and nodes s, Ri, 0 ..., Rn, Si, S ,..., 2 S. n There is a directed edge from So to 5 with upper bound = lower bound = 2p. There are directed edges from s to Ri, and Si to t both with upper bound /,• and lower bound <7, for i = 1 , 2 , 3 , . . . , n. There are directed edges from Ri to Sj with capacity u,j for i,j = 1,2,... , n . (see Figure 4.24). Assume there is a feasible flow of size 2p. Form a matrix A = (a,ij) from the flow by letting a tJ be the flow from Ri to Sj. We deduce that A has ith. row and column sum between 5, and / ; and satisfying 0 < A < u. We call A a directed size 2p (g, /)-factor. If no directed size 2p (#,/)-factor exists, then clearly no size p (g, /)-factor exists. 4.3.2 S y m m e t r i z i n g a D i r e c t e d Size 2p (g, / ) - F a c t o r : Phase O n e Symmetrization is much more involved than that in the /-factor problem, since we will have to preserve the fixed size 2p on the network (i.e., size p on graph G). Let A be a directed size 2p (g, /)-factor. Form a matrix x = (A + A )/2 T Chapter 4. Fixed Size (g, f)-Factor Problem 49 Figure 4.24: Network For Size p (g, /)-Factor Problem so that x is symmetric and half integral. We can view a; as a fractional subgraph of G, with 0 < x < u, and gi < deg (i) < /,• for i = 1,2, ...,n. x We still define H as the subgraph of G whose edges are half integral. This time the row sums of x need not be integral, so some vertices of H may have odd degrees. We need some definitions before going further. Less Than Upper Bound (LTUB) vertex: A vertex v G V is called an L T U B if g = deg (v) < f . v x v Greater Than Lower Bound (GTLB) vertex: A vertex v G V is called a G T L B if g < deg (v) = / „ . v x Strictly in Between (SB) vertex: A vertex v G V is called a SB if g < deg (v) < f . v x v Note V can only have even number of odd degree vertices, and these vertices are all SB's. We can decompose H into 1. Even length closed trails. 2. Vertex disjoint odd cycles. 3. Even length paths between two odd degree vertices. Chapter 4. Fixed Size (g, f)-Factor Problem 50 Figure 4.25: A pair of odd length paths LTUB Figure 4.26: A pair of odd degree cycles 4. Odd length paths between two odd degree vertices. For 1. and 3. we can eliminate them by alternately adding 1/2 and subtracting 1/2 on these edges and we still have a directed size 2p (g, /)-factor. For 4. we can eliminate any pair of such odd length paths by the similiar change (see Figure 4.25). Note vi, v , v , t> all have odd degrees in H, so they are all SB's so that we can on one 2 3 4 path start with addition and on another start with subtraction. Let us call this kind of change a double change. After enough double changes we are left with only one such odd length path or none. For 2. we can also eliminate a pair of odd cycles by a similiar double change if there is an L T U B on one cycle and a G T L B on another. Here a SB can be used either as an L T U B or a G T L B . (see Figure 4.26) We need an algorithm to accomplish the above eliminations. Eliminating Algorithm Two: Chapter 4. Fixed Size (g, f)-Factor Problem 51 • Step 1: If H has odd degree vertices go to Step 2, else, go to Step 4. • Step 2: Start with any path starting with an odd degree vertex and extend it if possible. When some vertex appears twice, a cycle is found. If the cycle is even, then eliminate it as described; if it is odd remove it from the graph but save it. Continue this process, starting over with as much of original path as was left. If at any point, two odd cycles have been found with any vertices in common, then the edges of the cycles can be decomposed into one or more even length closed trails which can be eliminated from H. When we are stuck we must end with an odd degree vertex. If this is same as the initial vertex we get a cycle which can be handled as above, otherwise we are left with a path between two odd degree vertices, then go to Step 3. • Step 3: If the path between two odd degree vertices has even length, eliminate it as described. If odd length, remove it, but save it. Whenever we have two such paths, we eliminate them as a pair by the double change, go to Step 1. • Step 4: A l l vertices have even degree now. Run the Eliminating Algorithm One given in the Section 4.2.2. The above algorithm also takes O d ^ l ) operations which is the same as the Eliminating Algorithm One. When the above algorithm stops we are left with either an even number of vertex disjoint odd cycles or one odd length path plus an odd number of vertex disjoint odd cycles. 4.3.3 S y m m e t r i z i n g a D i r e c t e d Size 2p (g, / ) - F a c t o r : P h a s e T w o A n odd length path can be regarded as an odd cycle by pasting both end vertices into one, we call the resulting cycle a pesudocycle. Later on, one will see that an odd length Chapter 4. Fixed Size (g, f)-Factor Problem 52 pesudocycle < \ Figure 4.27: Type 1 example path plays the same role as an odd cycle: When it appears in Type 1, it can be eliminated with another odd cycle as in Figure 4.27. In Type 2, it can be used as a cycle joined to either a L T U B or a G T L B by an alternating walk of zero length ending in either addition or subtraction; this is because the both end vertices of an odd length path are SB's, and thus the pasted vertex in a pesudocycle is a SB. It is obvious that a pesudocycle can never occur in Type 3. Thus we can simply assume when Eliminating Algorithm Two stops we are left with only vertex disjoint odd cycles C i , C , . . . C^jt- In order to keep the 2 same size we can only eliminate these cycles in pairs if possible. Before going further let's check the vertices of these cycles. Whenever we find a L T U B on one cycle, and a G T L B on another, we can eliminate them as in Figure 4.26 by a double change. Here a SB can still be used as either an L T U B or a G T L B . To eliminate more cycles we have to employ alternating walks again, we first examine how we can eliminate these cycles. • Type 1: Two cycles are joined by an alternating walk, we can perform the following changes as illustrated in Figure 4.27. • Type 2: One cycle is joined to an L T U B by an alternating walk ending in addition Chapter 4. Fixed Size (g, f)-Factor Problem 53 v: GTLB Figure 4.28: Type 2 example -1 -1 +1 Figure 4.29: Type 3 example and another cycle is joined to a G T L B by an alternating walk ending in subtraction, then these two cycles can be eliminated (see Figure 4.28). Note a SB could be used as either an L T U B or a G T L B , u could be on C\ and v also could be on C 2 o Type 3: Each of the cycles is joined to an L T U B (resp. G T L B ) by an alternating walk ending in addition (resp. subtraction) and an odd length alternating walk between two G T L B ' s (resp. LTUB's) or SB's or a G T L B (resp. L T U B ) and a SB (see Figure 4.29). Note: Changes on C\ and C totally increase size by 1 and changes on the walk P decrease 2 Chapter 4. Fixed Size (g, f)-Factor Problem 54 size by 1 (We are actually considering the edge size on G; the size should doubled if on the network). Now we give the the following algorithm to deal with these cycles of Types 1, 2, and 3. Eliminating A l g o r i t h m Three (E.A.T.): • Step 1: Apply the alternating algorithm on each cycle. If at any stage, a cycle is joined by an alternating walk to another cycle, then eliminate them as in Type 1. • Step 2: For each i, grow tree T, with C, as base. Whenever we encounter Type 2 with an L T U B (or a SB) on one tree and a G T L B (or a SB) on the other, then the two cycles can be eliminated as in Type 2. • Step 3: If two T,'s each have at least one L T U B (resp. G T L B ) or SB vertex reachable from base ending in addition (resp. subtraction), then seek an alternating walk joining two G T L B (resp. L T U B ) or SB vertices starting and ending in subtraction (resp. addition). If we succeed, we can eliminate C\ and C as in Type 3. 2 R e m a r k : We apply the alternating walk algorithm at most n times, so the total complexity of steps 1, 2, and 3 is still 0 ( n ) . 3 We will prove in next section if we still have cycles left after using elimination of Types 1, 2, and 3, then there does not exist a size p (g, /)-factor. 4.3.4 F i x e d Size (g, / ) - B a r r i e r First we present an alternate method to solve our fixed size (g, /)-factor problem by transforming it into an /-factor problem. Create a new graph G = ( V , E), such that V = V{J{s}, E = E{J{{s,z}:ieV}, with the multiplicity u defined as: Vi e V : u ai = fi - g ; { Ve € E : u = u , e e Chapter 4. Fixed Size (g, f)-Factor Problem 55 G G Figure 4.30: A n transformation from G to G. and / is denned as: / i = /„ Vi V; 6 and7, = £ / « - 2 P - R e m a r k : Assume each gi of g = (gi : i G V) can only be 0 or /,-. Define V- gi = 0} and V = = {i G V : = {i E V : gi = / , } , then this transformation is exactly same as the one in Figure 2.21. Thus this one is in fact a generalization of the one given for fixed size weighted 6-matching problem. Theorem 4.4: There is a size p (g, /)-factor on G iff there is an /-factor on G; an /-factor on G induces a size p /)-factor on G (this transformation also solves the weighted case fixed size (g, /)-factor problem, see Figure 4.30). P r o o f : Assume a: is a size p (g, /)-factor of G . Define x as follows: x = (xij :{i, }}£ E) where {i, j}e E _ J Xij — < /» ~ HrevXir Then x si < fi - gi Vi e V since £ r 6 j = s,ieV. y x,> > gt; Y,jevx j s = h = 22 f>: - p . The other 2 Chapter 4. 56 Fixed Size (g, f)-Factor Problem Figure 4.31: Figure for Theorem 4.6. vertices of V are clearly all saturated by x, thus x is an /-factor on G Conversely, if x is an /-factor on G, then it easy to see that x\o is a size p (g, /)-factor. Secondly, by using this transformation we will deduce a fixed size (g, /)-barrier on G via an /-barrier on G. Lemma 4.5: If in (7 there is no alternating walk joining any pair of odd cycles, then no /-factor exists in G which implies no size p (g, /)-factor in G . A n /-barrier in G induces a fixed size (g, /)-barrier in G . T h e o r e m 4.6: If Eliminating Algorithm Three fails to eliminate all the odd cycles, then there does not exist a fixed size (g, /)-factor in G . P r o o f (see Figure 4.31): Consider an alternating walk w, which must pass through 5 in view of Step 1 of E . A . T . , from C\ to C% in G Without loss of generality, assume w first reaches s from T\ with subtraction from a vertex p. We deduce by definition of G and the chosen subgraph that p £ L T U B or SB. Now the reversal of w goes from C 2 to C i , and so first reaches s from a vertex q by subtraction with q £ L T U B or SB (if by addition then q £ G T L B or SB, violating Step 2 of E . A . T . ) . But since w is an alternating Chapter 4. Fixed Size (g, f)-Factor Problem 57 walk, there is an alternating walk from s to s starting with addition to a vertex u (which then is a G T L B or SB) and also ending in addition from a vertex v (which must also be a G T L B or SB), and so there is an alternating walk joining u and v starting and ending in subtraction; but now Step 3 of E . A . T . would have been used. So we have a contradiction. Q.E.D.. Now we can conclude there does not exist an /-factor on G. If we define 5, T, L, U\, U2, • • •, U\ for G as in the previous section, our new vertex s will be in L for the first two cases, and in T for last two cases. When we restrict this partition to G, we can call it a fixed size (g, / ) - b a r r i e r . 4.4 Augumenting Walk Theorem Assume G = (V,E) is a simple graph with capacity vector u = 1. This assumption is only for brevity's sake; our result actually holds for multigraphs. Let a subgraph M be a (<7, /)-factor found by any known algorithm. Then an augumenting walk w.r.t. M is defined as below. D e f i n i t i o n : A walk P = t>oeiz;ie2U2 • • • 2 e 2 n + \ 2 n + \ v v n is called an a u g u m e n t i n g walk if we can add 1 on e subtract 1 on e , add 1 on e , . . . , subtract 1 on e , add 1 on e +i l5 2 3 2n 2n and still get a (g, /)-factor. Note if P is an augumenting walk, both v and 0 V 2 + \ n must be either an L T U B or a SB (see Figure 4.32). A n augumenting walk can help get another (g, /)-factor with size increased by 1. By proving an augumenting walk theorem, we ensure that a maximum size (g, /)-factor can always be found. We are going to prove this theorem by developing a walk growing algorithm. Note this algorithm can also be used to find an augumenting walk if one exists. T h e o r e m 4.7: If M is a (g,/)-factor such that no augumenting walks w.r.t. M Chapter 4. Fixed Size (g, f)-Factor Problem 58 Figure 4.32: A n example of augumenting walk exist, then M is a maximum size (g,/)-factor. Proof: Suppose M is a maximum size (g, /)-factor, we only need to show \M\ < \M\. Consider H = MAM For any component D of H if we can show \MD\ = \Mf)D\ < \MQ\ = \Mf)D\, then we can conclude that \M\ < \M\. We show this by the following algorithm. • Step 1: If H is empty: stop; else: pick any component D of H and go to Step 2. • Step 2: If for all v,- £ V(D) : degjj(vi) < degM(vi) then replace H by H \ D (since in this case \MD\ < |M£>|). Else: pick an vertex Vo £ V{D) such that degjj(v ) > degM(v ) and go to Step 3. Q Q • Step 3: Find a vertex v x £ V'(.D), s.t. {v ,V\} Q £ M. Vertex v x cannot be an L T U B or a SB (w.r.t. M ) , otherwise an augumenting walk is found; so there must be a vertex v 2 £ V(D), s.t. {vi,v } 2 £ M. We keep visiting edges of M and of M alternately until we are forced to stop. Finally we obtain an alternating walk P = v eiVie v e v 0 2 2 3 3 . . .e v 2k 2k and go to Step 4. Chapter 4. Fixed Size (g, f)-Factor Problem 59 Figure 4.33: A n example showing terminal vertex Note: P must be of even length and none of Ui, i > 3 , v k - \ could be either an L T U B or a 2 SB, otherwise an augumenting walk will be found. Moreover we must have degjr(v k) < 2 degM( 2k)i otherwise v k can not be the terminal vertex. In Figure 4.33 v is a terminal v 2 4 vertex where a straight line denotes an edge of \M\ and a zigzag line denotes an edge of M. • Step 4: First, do /,• = /,• — 1 for i = 1 to 2k. Second, delete e i , e3,e 2 k -i from M and delete e , e , . . . , e k from M. Namely we replace H by H \ P. Go to Step 1. 2 4 2 Decreasing /,'s by 1 except /o makes each M-matched vertex have the same deficiency as before deleting P from H. Since edges of H decrease montonically, our algorithm only takes 0(n ) operations. When the algorithm stops we can deduce \M\ < \M\ because 3 each time we delete P from H we are deleting edges of M and of M in pairs. Q . E . D . R e m a r k 1: We can define a decreasing walk similarly (see Figure 4.34). A decreasing walk can help get another (g,/)-factor with, size decreased by 1. A theorem can also be proved that if M is a (<?, /)-factor without any decreasing walks, then M is a minimum size (g, /)-factor. R e m a r k 2: The size of all feasible (<?, /)-factors forms an interval, i.e., a (g, /)-factor Chapter 4. Fixed Size (g, f)-Factor Problem 60 \ Figure 4.34: A n example of decreasing walk of any integral size between a and b exists where a is the size of a maximum size (g,f)factor and b is the size of a minimum size (g, /)-factor. If we want a (g, /)-factor of some fixed size p, we could start with any feasible (g, /)-factor M and apply the augumenting (or decreasing) walk algorithm to achieve this size; if we fail we know that no (g, /)-factor of size p exists. Note that we could use this result and binary search on size using the fixed size (<?, /)-factor algorithm as an alternative approach to determine the interval is a specific instance. This approach would often be more efficient. Bibliography R.P. Anstee, A n algorithmic proof of Tutte's /-factor theorem, J . Algorithms 6(1985)112-131 R.P. Anstee, A polynomial algorithm for b-matchings: A n alternative approach, Information Processing Letters 24(1987) 153-157,North-Holland. R.P. Anstee, Simplified existence theorems for (g, /)-factors, Discrete Applied Mathematics 27(1990)29-38, North-Holland. J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, Elsevier, New York, 1976. J. Edmonds and E . L . Johnson, Matching: A well solved class of integer programs, Summary in: Combinatorial Structures and Their Applications (Gordon & Breach, New York, 1970)89-92. E. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, New York, 1976, L. Lovasz, Subgraphs with prescribed valencies, J . Combin. Theory 8(1970)391-416. W.R. Pulleyblank, Faces of matching polyhedra, Ph.D. thesis, Dept. of Combinatorics and Optimization, Univ. of Waterloo, 1973. Christos H . Papadimitriou, Kennneth Steiglitz, Combinatorial Optimization: gorithms and Complexity. Prentice-Hall Inc, Englewood Cliffs, N J 07632, 1984. 61 Al- Bibliography [10] 62 R . L . Urquhart, Degree constrained subgraphs of linear graphs, Ph.D. Thesis, The Univ. of Michigan,1967.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Matchings with a size constraint
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Matchings with a size constraint Zhou, Bo 1990
pdf
Page Metadata
Item Metadata
Title | Matchings with a size constraint |
Creator |
Zhou, Bo |
Publisher | University of British Columbia |
Date Issued | 1990 |
Description | We study the matching problem and some variants such as b-matching and (g, f)-factors. This thesis aims at polynomial algorithms which in addition have other properties. In particular, we develop a polynomial algorithm which can find optimal solutions of each possible size for weighted matching problem, and a strongly polynomial algorithm which can find a (g, f)-factor of fixed size. |
Subject |
Matching theory |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-10-21 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080433 |
URI | http://hdl.handle.net/2429/29413 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1990_A6_7 Z45.pdf [ 3.24MB ]
- Metadata
- JSON: 831-1.0080433.json
- JSON-LD: 831-1.0080433-ld.json
- RDF/XML (Pretty): 831-1.0080433-rdf.xml
- RDF/JSON: 831-1.0080433-rdf.json
- Turtle: 831-1.0080433-turtle.txt
- N-Triples: 831-1.0080433-rdf-ntriples.txt
- Original Record: 831-1.0080433-source.json
- Full Text
- 831-1.0080433-fulltext.txt
- Citation
- 831-1.0080433.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080433/manifest