UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Matching theory: subgraphs with degree constraints and other properties Nam, Yunsun 1994

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1994-893907.pdf [ 2.61MB ]
Metadata
JSON: 831-1.0079982.json
JSON-LD: 831-1.0079982-ld.json
RDF/XML (Pretty): 831-1.0079982-rdf.xml
RDF/JSON: 831-1.0079982-rdf.json
Turtle: 831-1.0079982-turtle.txt
N-Triples: 831-1.0079982-rdf-ntriples.txt
Original Record: 831-1.0079982-source.json
Full Text
831-1.0079982-fulltext.txt
Citation
831-1.0079982.ris

Full Text

CONSTRAINTS MATCHING THEORY: SUBGRAPHS WITH DEGREE AND OTHER PROPERTIES By Yunsun Nam B. Sc. (Mathematics) Ewha University, Korea, 1985 M. Sc. (Mathematics) Ewha University, Korea, 1987  OF A THESIS SUBMITTED IN PARTIAL FULFILLMENT THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY  in THE FACULTY OF GRADUATE STUDIES APPLIED MATHEMATICS) DEPARTMENT OF MATHEMATICS (INSTITUTE OF  We accept this thesis as conforming to the required standard  THE UNIVERSITY OF BRITISH COLUMBIA  April 1994  ©  Yunsun Nam, 1994  ments for an advanced In presenting this thesis in partial fulfilment of the require the Library shall make it degree at the University of British Columbia, I agree that errnission for extensive freely available for reference and study. I further agree that granted by the head of my copying of this thesis for scholarly purposes may be understood that copying or department or by his or her representatives. It is allowed without my written publication of this thesis for financial gain shall not be permission.  ture)  (Signa  Department of  t4 O’tAK  The University of British Columbia Vancouver, Canada Date  DE-E (2188)  Abstract  In this thesis, three generalizations of the matching problem are considered. The first problem is the existence of matrices with given row and column sums. This problem can be interpreted as the f-factor problem of a bipartite graph. The well-known existence theorem follows from maxfiow-mincut theorem, but it contains an exponential number (in the number of rows) of inequalities. We generalize the Gale-Ryser theorem and obtain some conditions under which this exponential number of inequalities can be reduced to a polynomial number of inequalities. The second problem is the general factor problem. Let G An arbitrary subset BL, of {O, 1,2,.  .  .  ,  =  deg(v)} is assigned to each vertex v E V. We  call a B-factor a spanning subgraph F of G such that deg (v) v  e  V. A set B is said to have a gap of length p  that k+ 1,.•.,k+p  (V, E) be a multigraph.  e  B for every vertex  1 if there exists an integer k such  B, and yet k,k+p+ 1 E B. It’s known that the problem  is NP-complete if we allow gaps of length more than one. We extend the algorithm of Cornuéjols for simple graphs and obtain a strongly polynomial algorithm for finding a B-factor when each B doesn’t have a gap of length 2 or more. A new augmenting walk that need not alternate is introduced. The third problem is the square-free two-factor problem. A square-free two-factor is a two-factor in which the cycles don’t have length 4, i.e. are not squares. We obtain an augmenting path theorem like Berge’s augmenting path theorem for a 1-matching. Also we obtain a polynomial algorithm for finding a square-free two-factor when the squares of G are vertex-disjoint.  II  Table of Contents  Abstract iii  Table of Contents  List of Figures  v  Acknowledgement  ix  Introduction  1  1  2  3  1  1.1  Basic Graph Theory Terminology  1.2  Introduction to the Matching Problem  1.3  Three Problems in this Thesis  .  .  2  .  4  Integral Matrices with Given Row and Column Sum Vectors  10  2.1  Introduction  10  2.2  Theorems  12  2.3  The Proof of Theorem 2.4  16  2.4  Further Study  24 25  General Factor Problem 3.1  Introduction  25  3.2  Augmenting Walks  27  3.3  General Factor Problem with Parity Conditions  3.4  Algorithm for General Factors with Parity Conditions  38  3.5  General Factor Problem Allowing Gaps of Length 1  44  3.6  Further Study  .  .  .  .  28  46 111  4  Square-Free Two-Factors  47  4.1  Introduction  47  4.2  A Berge-type Theorem  50  4.3  A Preview of the Blossom Algorithm  67  4.4  The Blossom Algorithm  81  4.5  Some notes for the Recover Algorithm  96  4.6  The Recover Algorithm  101  4.7  The validity of the Recover Algorithm  117  4.8  The structure of .F at the end of the Blossom Algorithm  125  4.9  A Tutte-type Theorem  130  4.10 Efficiency of the Blossom Algorithm  149  4.11 Further Study  162  Bibliography  166  iv  List of Figures  3.1  .  3.2  .  3.3  .  29 30 32  3.4  35  4.1  51  4.2  51  4.3  53  4.4  55  4.5  56  4.6  57  4.7  58  4.8  59  4.9  60  4.10  61  4.11  61  4.12  64  4.13  65  4.14  65  4.15  66  4.16  67  4.17  69  V  4.18 A forest F  .  71  4.19  72  4.20  73  4.21  75  4.22  75  4.23  77  4.24  77  4.25  78  4.26  79  4.27  80  4.28  81  4.29  84  4.30  84  4.31  86  4.32  86  4.33  88  4.34  89  4.35  89  4.36  91  4.37  94  4.38  95  4.39  99  4.40  100  4.41  105  4.42  106  4.43  107 vi  4.44  .  4.45  .  108 109  4.46  110  4.47  111  4.48  113  4.49  114  4.50  116  4.51  117  4.52  120  4.53  123  4.54  124  4.55  125  4.56  128  4.57  130  4.58 A blossom tree  132  4.59  133  4.60  134  4.61  137  4.62  139  4.63  142  4.64  143  4.65  143  4.66  144  4.67  146  4.68  146  4.69  149 vii  4.70  .  4.71  .  153 155  4.72  156  4.73  164  viii  Acknowledgement  My appreciation is due to many people who have substained me in this endeavour. First I would like to thank my supervisor, Prof. Richard Anstee. I cannot express enough my gratitude to him. Without his patient guidance and encouragement, this thesis could not have been completed. I owe much to his insightful questions and suggestions. I want to thank the members of my committee: Prof. Frieda Granot and Prof. David Kirkpatrick. Dr. Kirkpatrick, in particular, spent many hours with me in discussion of my work and ideas. I would like to thank Prof. Kee Lam for his caring support while I have been at UBC. Finally, I would like to thank my dad, Sangjoon, and my mom, Taemin, and all the members of my family for their caring, support and much more.  ix  Chapter 1  Introduction  1.1  Basic Graph Theory Terminology  In this section, some basic terminology and notations in graph theory are given. If the reader is familiar with graph theory, then he/she can skip this section. Whenever we use some terminology or notation which is not used commonly, then we will state them. A graph G  =  (V, E) is a set V of elements called vertices, together with a set E of  unordered pairs of elements of V called edges. If an edge e consists of two vertices v and w, then we denote e  =  (v, w) or (w, v) and say that e joins v and w. Also v and w are  end vertices of e and it is said that e is incident with v. If there is an edge joining two vertices v and w, then it is said that v and w are adjacent. If an edge e joins the same vertex, we call the edge e a loop. A graph G is simple if it has no ioops and no two of its edges join the same pair of vertices. A graph G is a multigraph if it has a loop or more than one edge joining the same pair of vertices. We call the number of copies of edge e the multiplicity of e. In a graph G, a vertex v is said to have degree k (written deg (v)  =  k) if there are exactly k  edges incident with v. A graph F  =  (F(V),F(E)) is a subgraph of G (written F ç G) if F(V) ç V,  F(E) C E and every edge in F(E) joins a pair of vertices in F(V). A spanning subgraph of G is a subgraph F of G with F(V)  =  V. Suppose that V’ is a subset of V. The  subgraph of G whose vertex set is V’ and whose edge set is the set of those edges of G  1  Chapter 1. Introduction  2  that have both end vertices in V’ is called the subgraph of G induced by V’ and is denoted by G[V’]; we say that  G[V’j  is an induced subgraph of G.  A walk in G is a sequence W  =  vertices and edges such that, for 1  2 1 e 0 v  i  the terms of which are alternately  n, e joins two vertices v_ 1 and v. The integer  ,e 1 ,.. , e,-, of a walk W are distinct, W is called a 2 n is the length of W. If the edges e trail. If, in addition, the vertices v ,v 0 ,••• , v, of W are distinct, W is called a path. 1 We use the notation A/.B to denote the symmetric difference between A and B, that is A1B  =  (A  \ B)  U (B  \ A).  We will define here some terminology in complexity theory. An algorithm is pseudopolynomial if it runs in polynomial time in the numbers in the input, not the size of the input. Since the size of a number is its logarithm, a pseudo-polynomial algorithm may not be a polynomial algorithm. We say that an algorithm is strongly polynomial if (i) it runs in a polynomial number of arithmatic operations in the number of numbers in the input (not in the size of the input), and (ii) all numbers generated by the algorithm have a number of bits which is bounded by a polynomial in the size of the input. Hence a strongly polynomial algorithm is a polynomial algorithm.  1.2  Introduction to the Matching Problem  In this section, some problems which are generalizations of the matching problem are introduced. The matching problem asks whether there exists a spanning subgraph F of G of which each vertex has degree one. We call such a subgraph a 1-matching. The problem is well studied. There are a number of polynomial algorithms for finding a 1-matching [16] [20] [28] [41] and there is an existence theorem for a 1-matching, the so called Tutte Theorem [37] [50]. The problem is generalized in many different ways, e.g. the f-factor problem, the (g, f)-factor problem, the general factor problem, the factor  Chapter 1. Introduction  3  problem with side conditions, the b-matching problem, etc. Below, we will introduce the definitions. These generalizations of the matching problem have a nice character, that is, there exists either a solution or concise evidence that there is no solution. Specifically, some algorithms find either a solution or the evidence that there is no solution, and they run in polynomial time. In [37], it’s written “It is fun to consider the matching problem and those problems related to it. They are of an attractive level of difficulty. On the other hand, most of them are solvable problems, but to solve them certainly requires non-trivial methods.” The (g, f)-factor problem is: Given integeral vectors g (f(v) : v  V) such that g(v)  f(v).  f,  (g(v) : v E V) and  f  =  Does there exist a (g, f)-factor, that is, a  spanning subgraph F of G such that g(v) g  =  deg(v) < f(v) for each vertex v  e V? If  then we call F an f-factor. Chapter 2 considers f-factors of bipartite graphs  and cases where the existence theorem is “easy”. There are polynomial algorithms which find a (g, f)-factor or the evidence that there is no (g, f)-factor for a given graph G [4]. The (g, f)-factor problem can be generalized by prescribing an arbitrary subset B of {O, 1, 2,... , deg(v)} for all v  e V, letting B  =  {B I v  that is a spanning subgraph F such that deg(v)  e V}, and looking for a B-factor,  e B for all v e V. This problem is  studied in Chapter 3. Another generalization of the matching problem is the factor problem with side condi tions [14] [32]. The existence problem for two-factors in which the cycles are restricted to having lengths from a prescribed (possibly infinite) set of integers are considered in [32]. In Chapter 4, we study the case when the cycles are restricted to not having length 4, called square-free two-factors. The b-matching problem is generalized in a different way from the above generaliza tion. Each edge e of E is assigned a cost  Ce.  Let b  =  ,b 1 (b ,• , 1 2 by be a vector of )  non-negative integers. A b-matching is an assignment of positive integer weights  Xe  to  Chapter 1. Introduction  4  the edges such that, for each vertex v, the sum of the weights on edges incident with v is no more than b. The b-matching problem then consists of looking for a b-matching of maximum cost where the cost is the weighted sum of the costs on the edges, i.e.  E{cexele E E}. 13  This is studied in [5], [42] and [44].  Three Problems in this Thesis  In this thesis, three generalizations of the matching problem are considered. These appear in Chapters 2-.’4, respectively and each chapter is an independent work from the others. In Chapters 3 and 4, we use the idea of the Blossom Algorithm. If the reader is not familiar with it, then he/she can refer to [16] and [37]. The unifying theme is degree constrained subgraphs and the augmenting walks to obtain them. Our contribution in this thesis are many. We generalize in an attractive way the existence theorem of Gale and Ryser (Theorem 2.2) for (0,1)-matrices of given row and column sums. We generalize further, obtaining a rather nice result that in effect says, in the maxflow-mincut theorem for this problem, that we can restrict ourselves to looking at a polynomial number of cuts. We extend the algorithm of Cornuéjols for the general factor problem [15] to the case of multigraphs and obtain a strongly polynomial algorithm. We introduce an augmenting walk which does not alternate in the usual way but is natural for this problem. Finally we tackle the problem of looking for a subgraph of a graph G that consists of vertex disjoint cycles (including all vertices) but having no cycle of length 4. We only succeed in obtaining a polynomial algorithm for the case where the squares of G are vertex disjoint but even this problem seems to have a rich structure. The algorithm is extremely complicated. The thesis will be of most interest to those with a reasonable knowledge of matching theory who wish to know the latest generalizations. No real-world applications for these results have been found but these results add to the  Chapter 1. Introduction  5  knowledge base for Combinatorial Optimization. In Chapter 2, we study the existence problem of matrices with given row and column sums. This problem is equivalent to the f-factor problem of a bipartite (multi)graph. Let m and n be positive integers, and let R  =  negative integral vectors with r 1 + + rm  = s 1  non-negative integral matrix. Let A  =  (ri,...  ,Tm)  + +  (a) be an  and S  s,.  m x ii  Let  ,s) be non  =  Q  (qjj) be an  =  ni x n  non-negative integral matrix  with row sum vector R and column sum vector S such that  qjj for all i and  j,  Q. Interpreting Q as a bipartite adjacency matrix of a bipartite multigraph G (vertex i of the first part is joined to vertex j of the second part by qjj edges); we  denoted A  see that A corresponds to a subgraph of G with vertex i of the first part having degree r  and vertex  j of the second part having degree  sj.  The well known existence theorem  for a matrix A follows from the maxfiow-mincut theorem. The conditions consist of an exponential number of inequalities, i.e. an exponential number of cuts. D. Gale [29] and H. J. Ryser [45] proved that we can reduce the exponential number of inequalities to a linear number of them, that is only  n  inequalities, in the case qjj  =  1 for all i and  j.  In generalizing the Gale-Ryser theorem, we obtain some more general conditions under which this exponential number of inequalities can be reduced to a polynomial number (in  n)  of inequalities. The augmenting path theorem in network flow theory is used to  get the result. The Gale-Ryser Theorem has been generalized by many people including D. R. Fulkerson [22], R. P. Anstee [2], and most recently W. Chen [13]. Our first result, Theorem 2.3, successfully generalizes the previous results while keeping the statement simple. Perhaps this result will find some application in the way that the Gale-Ryser Theorem has found applications, e.g. to Latin squares. We were surprised to find such a simple generalization of such a well known result. The second result, Theorem 2.4, is much more complicated and hence less likely to find applications. We build a kind of hierarchy: under weaker and weaker conditions, more and more inequalities (still a  Chapter .1. Introduction  6  polynomial in n) are involved in a necessary and sufficient condition for the existence of a matrix A. This is the first result of this type and it was for this reason the result was obtained. In Chapter 3, we study the general factor problem. We have given the definition of the problem in Section 1.2, but we will give here. For each vertex v  e V, let B  be an arbitrary subset of {O, 1,—• , deg(v)}. The problem asks whether there exists a subgraph F such that for each vertex v E V, deg(v) E B,. This problem was introduced by Lovász [36]. A set B is said to have a gap of length p k such that k + 1,” , k + p  B and yet k, k + p + 1  1 if there exists an integer  e B. Cornuéjols has shown  that the problem is NP-complete if we allow gaps of length more than one [15]. Also he gives a polynomial algorithm when G is simple and each B doesn’t have a gap of length 2 or more. He reduces the problem to a sequence of problems in which each B is a parity condition, i.e. all entries in B have the same parity. He reduces the problem with parity conditions to the 1-matching problem. We extend those results by giving an efficient approach for the case of multigraphs (possibly with loops) and preserving the strongly polynomial nature of the algorithm. We introduce a new type of augmenting walk for these matching problems which need not be alternating. A direct application of Cornuéjols’ reduction to a multigraph results in a pseudo-polynomial algorithm. We use his idea to characterize our new augmenting walks, but our algorithm solves the problem directly in a natural way. We operate entirely in the graph G. The method of “sparse substitutes” of Gabow [27] did not seem to be applicable without a lot of work and moreover the method is one level removed from the original graph and hence will incur extra costs. At this stage we know of no practical problems requiring the generality of the gen eral factor problem. We give a made up problem involving warehouses at the end of Section 3.1. Hence it is perhaps hasty to dwell on efficiency. Novertheless our approach  Chapter 1. Introduction  7  provides an efficient algorithm even when the graph is not a multigraph. An extended set of general factor problems are shown to be solvable directly without reduction to a number of parity problems. In Chapter 4, we study the two-factor problem with a condition. A two-factor of G consists of a spanning collection of vertex-disjoint cycles. The problem of finding a two-factor is in P. On the other hand, it is well known that finding a Hamiltonian cycle in a given graph is NP-hard. Many people have studied the complexity of the problem of finding a two-factor in which the cycles are restricted to having lengths from a prescribed (possibly infinite) set of integers. In the case that the cycles are restricted to not having lengths other than 3 and 4, the problem was shown to be NP-hard by P. Hell et al [32]. In the case that they are restricted to not having length 3, this problem is called a triangle-free two-factor, it was shown by D. Hartvigsen [31] that the problem is in P. At this moment, we don’t know if the square-free two-factor problem (no cycles of length 4) or the  { triangle,  square} -free two-factor problem is in P or NP-hard or  otherwise. We focus our attention on the problem of the existence of square-free twofactors. We obtain an augmenting path theorem like Berge’s augmenting path theorem for 1-matching [7]. If we have a square-free (0,2)-factor F of G and H is another squarefree (0, 2)-factor of G with more edges, then there exists an augmenting walk W which is alternating and the symmetric difference between F and any initial subwalk of even length of W is square-free. When we look for an augmenting walk, we need concern ourselves with squares being locally created. An augmenting path having such nice properties does not exist for the case of a L-free two-factor unless L  C {3, 4}. We obtain a  polynomial algorithm for finding such an augmenting walkin a graph where its squares are vertex-disjoint. The algorithm we present is extremely complicated, consisting of two nontrivial components, the Blossom Algorithm (Section 4.4) and the Recover Algorithm (Section 4.6). We apologize to the reader that the result is so complicated but examples  Chapter 1. Introduction  8  given in Figures 4.19 and 4.20 indicate the difficulty of solving the problem by augmenting walks. As in most matching algorithms we have a tree growing phase (the Blossom Algorithm) that gives labels to vertices depending on the type of augmenting walk by which the vertices can be reached from a deficient vertex. Blossoms are collapsed cycles formed in the tree structure by adding edges under certain conditions. Having determined that a desired augmenting walk exists, we then recover that walk from our tree structure by expanding blossoms (the Recover Algorithm).  Unfortunately in various cases we  must alter the walk from the expected walk in order to avoid creating squares. Examples are the paths in Figure 4.45 which are replaced by the paths in Figure 4.48 (in the corresponding diagrams). Please compare the figures to see the changes. In essence, the Blossom Algorithm has avoided dealing with these situations and simply notes that the edges currently examined allow us to give labels as described. Later in the Recover Algorithm, we deal directly with these situations. To actually prove the algorithm works is a large task. We use the conditions for termination of the Blossom Algorithm to prove a Tutte-type Theorem (Section 4.9) giving a necessary and sufficient condition for the existence of a square-free two-factor. This latter result unfortunately turned out to be too complicated for ready application. The Recover Algorithm is proved by a sequence of lemmas in Sections 4.5 and 4.7. The reader may wonder why we did not complete the square-free two-factor problem. The reason is because our initial investigation suggested that the algorithm would be extremely complicated and we wished to finish this thesis in a timely manner. Our results may prove to be a useful foundation for further research. In each of the three problems, a type of augmenting walk appears. Each of them has a different character. In the problem of the existence of matrices with given row and column sums, we use the standard augmenting walk of network flow theory. In the general factor problem, we present a new type of an augmenting walk which need not be alternating. In  Chapter 1. Introduction  9  the square-free two-factor problem, we use an augmenting walk that is alternating, but need some additional restrictions such that the symmetric difference between any initial subwalk of the augmenting walk and the current square-free (0,2)-factor F we have is also square-free.  Chapter 2  Integral Matrices with Given Row and Column Sum Vectors  2.1  Introduction  Degree constrained subgraphs of a bipartite graph are solvable with Network Flow The ory. One case that has been extensively studied using Network Flow Theory is the case of integral matrices with given row and column sums. Let m and n be positive inte gers, and let R 1 +•.. + rm r  =  (ri,...  = Si  ,  rm)  and S  +... + s,. Let  =  Q  =  ,... , s) be non-negative integral vectors with 1 (s (qjj) be an m x n non-negative integral matrix.  Denote by 2L (R, S) the class of all m x n non-negative integral matrices A row sum vector R and column sum vector S such that  =  (a) with  qij for all i and all j, denoted  Q. We use Qt(R, 5) to denote the class of all (0, 1)-matrices of size m by  A  ii  row sum vector R and column sum vector S, which corresponds to Qt (R, 5) when the matrix of l’s. We can, if we wish, interpret a matrix A  (f  =  (R, 5)) of a bipartite graph given by  with  Q is  e 2t(R, 5) as a f-factor  Q.  We can interpret 2tc(R, S) in terms of network flows. The reader may be referred 2 (R, S) can be considered to [23] for the basics of network flow theory. Matrices in Q  as maximum integral flows in the following network. The vertices consist of a source s, a sink t, and R ,• , Rm, Si, 1 r for i =  ,  ..  ,Sn. There is an edge from s to R with capacity  rn. There is an edge from S to t with capacity s, for  Finally there are edges from R to S with capacity qjj for i Consider a maximum integral flow from s to t of size r 1 +  10  =  1,.• , in and +  rm.  Let  j j  =  1,.  =  1,• .. , n.  ..  ,  n.  be the flow  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  from R to Si and let A  =  ). We easily deduce that A 3 (a  11  (R, S). Conversely, from 2 e 2t’  a matrix A in 2t’(R, S) we can construct a maximum integral flow of size r 1++  rm.  Now the maxflow-mincut theorem says that 2t (R, S) is nonempty if and only if no cut has capacity less than r 1 + +  rm.  The number of cuts in the above network is  m+n 2  By Lemma 2.1 in Section 2, the number of inequalities can be reduced to 2 inequalities, but it is still an exponential number. D. Gale [29] and H. J. Ryser [45] independently obtained the result that in the special class 2t(R, S) we can reduce the exponential number of inequalities to a linear number of them, that is only n inequalities. D. R. Fulkerson [22] observed that the result of Gale and Ryser can be generalized to the class of (0, 1)-matrices with given row sums and column sums and zero trace. Also R. P. Anstee [1] obtained the generalization to the class of (0, 1)-matrices with given row sums and column sums and with zeros in a prescribed set of positions consisting of at most one position per column. Recently W. Chen [13] generalized these results to the class 2t(R, S) of integral matrices satisfying a certain condition (see Section 2). In this chapter, we get a generalization of Chen’s result, that is if Q and S satisfy some condition, then we have a necessary and sufficient condition for the existence of a matrix in 2t(R, 5) containing only n inequalities (Theorem 2.3). The results of Gale-Ryser, F’ulkerson, Anstee, and Chen can be regarded as special cases of our result, since they can easily be derived from it. Also we build a kind of hierarchy: under weaker and weaker conditions, more and more inequalities, still a polynomial in n, are involved in a necessary and sufficient condition for the existence of a matrix in 2t(R, S) (Theorem 2.4). Network flow theory is employed to obtain our generalization.  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  2.2  12  Theorems  Throughout this chapter, we will use the following notation: [a,b]  {a,a+1,a+2,•..,b}  =  max {a,O}.  Q (R, S) is nonempty if and only if for c By the maxflow-mincut theorem of networks, 1 allI C [1,m] and J  [1,n], r  qij iEI  iEIjEJ  So we have to check these  m+n inequalities. 2  (2.1)  Si  —  iJ  But the following lemma reduces these  inequalities to 2 inequalities.  S  Lemma 2.1 2t’(R, S) is nonempty if and only if for all J  [1, n],  (rj—>qjj) i=1  Proof.  (==)  m 2  (2.2) jJ  jEJ  Let J be any subset of [1, n]. Let I q)+  —  =  = {i I r,  Ti  —  iEI  jeJ  qii}. Then  iEI jEJ  By (2.1), rj—qjj  s,.  iEI  iJ  iEIjEJ  So we can get inequality (2.2).  (=)  For any I C [1,m] and J C [1,n], ri—qij iEI  iEI i€J  rj—qij) i=1  jEJ  zSi.  iJ  I  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  13  The Gale-Ryser theorem says that there exists a matrix in 2t(R, S) if and oniy if for all J  =  [1,h], (2.2) holds. In the general case of 2I(R,S), we need to check (2.2) for  all subsets J of [1, n], an exponential number of inequalities. For a (0,1)-matrix case, it is enough to check it for only n subsets. We will state the Gale-Ryser theorem formally here in the notation of the above lemma. Theorem 2.2 [Gale-Ryser Theorem] [29] [45] Suppose that s 1  there exists a matrix in 2t(R, S) if and only if for all J  =  2 s  s,,. Then  [1, h],  (r-h) 1=1  (2.3) jJ  The following theorem is a generalization of the Gale-Ryser theorem. We will not give its proof here, because this theorem is a special case of Theorem 2.4. We state it separately from Theorem 2.4 because it has a simpler flavor. Theorem 2.3 Suppose that (qij—qik) <Si—Sk+l  forl<j<k<n.  Then there exists a matrix in 2t(R, S) if and only if for all J rj—qjj) i=1  jEJ  =  (2.4)  [1, h], (2.5)  >s. jJ  Note that any given column order could be used which gives you the flexibility, de pending on  Q,  to even have s  =  11 s  —  1. On the other hand, we cannot always order  columns to make condition (2.4) hold. It may happen that 1 (qjj  —  >  3 s  —  k 5  +1  We can derive from the above theorem not only the Gale-Ryser Theorem, but also Fulkerson’s result [22] on the existence of a matrix in t(R, S) with zero trace and Anstee’s result [1] on the existence of a matrix in 21(R, S) which has zeros in a prescribed set of  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  14  positions consisting of at most one position per column. In [13], Chen gives the same theorem as the above theorem, except that instead of our condition (2.4) he gives the following condition: m—qik  where  for 1  S—S+l  j  < k  n  z is the maximum entry of Q. It is easy to verify that his condition is included  in our condition. The following theorem generalizes Theorem 2.3, and its proof is given in Section 3. The theorem was prompted by an algorithm for finding matrices in 2t (R, S) which appears at the beginning of the proof. We end up imposing regularity condition on  Q  and S (2.6) so that we need only check (2.2) for polynomially many J. Theorem 2.4 Let 1 be an integer such that 0  the following: let the  } 1 ,j,_  j ‘s be such that  C  —  s  qjj + qjj —  j <  [j]. Suppose that .j  <  <  and  ,j21+1}  (q  1  1  —  s +s  n. Then there exist ,j21+2}  {j2,j4,”  qjj +• + qjj 1  —  121+2  s +• + s  —  —  Q and S satisfy such that  qjj) s + 2p  —  1  (2.6)  Then there exists a matrix in 2t’(R, 5) if and only if (rj—qjj) i=1  jeJ  (2.7) jJ  where J  =  [1, h] U [h ,h 1 ] U [h 2 ,h 3 ] U... U [h 4 ,] 1 _ 21 21 h  or ,h 1 [h ] U [h 2 ,h 3 ]U 4  ...  ,] 1 _ 21 21 h U [h  •..h 2 (1hhih n) 21 _jh  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  15  We are able to weaken condition (2.4) at the expense of having to look at many more cut inequalities, namely with G(n ’) inequalities. 2 If 1 >  L!i],  then condition (2.7) holds for all subsets J of [1, n] and it is already  a necessary and sufficient condition for the existence of a matrix in Qt (R, S). It is meaningless to consider this case. The following condition is a special case of the condition (2.6): for some k k_ 2 (qij 1 Since we have (1 + 1) pairs of or equal  ,  i.e.  2k  —  J2k—1  —  qj)+  (j2kl, j2k),  1 _ 2 S  —  j2k 5  + 1.  at least one pair has the difference less than  [-y]. So we obtain the following corollary.  Corollary 2.5 Let 1 be an integer such that 0  1  Suppose that  j,n}. n 1 for 1<j<k<min{j+[ Then there exists a matrix in 2I (R, S) if and only if  >i=1 (r  qjj)  —  jEJ  where J  =  1 + 1,  [1,/i] U 2 ,h U 4 1 [h ] ,h 3 [h ]  ,h 1 _ [h ] U 21  or ,2 1 [h h U [h ] ,h 3 ]U 4  ...  ,] 1 _ 21 21 h U [h  ...h 2 (1hhih n). _ih 21  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  2.3  16  The Proof of Theorem 2.4  Suppose that 2t’(R, S) is nonempty. Then by Lemma 2.1, (2.7) holds. Now we will do the other direction of the proof. Suppose that (2.7) holds. We construct the desired matrix A inductively by columns by rearrangement of the entries in the rows of A*, where A* is defined as follows: A*  (at) is the matrix with row sum vector R in which entries  =  in a row are as far to the left as possible subject to the condition that A*  Q.  So for  each row i of A* there is an index k so that a 1 1*  = qi,  alk+1 =  0,  * a 2  =  *  12 q ,  alk+2 =  .  0,  .  ,  ...,  aJ_ = qik—1,  am  =  *  alk  —  qk,  0  A row rearrangement of row i is the replacement of row i by a new row of the same row sum r . We can envision this operation as corresponding to a sequence of operations of 1 subtracting 1 from one entry a 1 in column j and adding 1 to another entry alk in column k. This corresponds to moving a 1 from column  j  to column k. We always keep A  Note that A* can be obtained from any other matrix A  Q  Q.  with row sum vector R by  row rearrangements moving l’s only to the left. Let’s start with the first column. , q) 1 min(r  si and s  Since t (rm 1 If s  s.  —  qj)+ < 2 s + 3 s +  +  Sn,  , go to the second column. Assume 1 s  =  that s > s . Move entries from the first column to the next columns by row rearrange 1 ments. If the column sum reaches s , then we can start the construction of the second 1 column. Suppose not. Let current matrix A’. Then  and s be the entry of (i, i) and the =  qjj for  j  =  2,••• n whenever a 1 ,  and J={2,...,n}. Then (*)  (rj—>qjj) 1=1  jEJ  rj—qjj) iEI  jEJ  th  column sum of the  0. Let I  =  {i a 1  0}  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  >(rj—qjj) iEI  >  =  17  s’  JEJ  Si  So we have a contradiction to (2.7). Let us suppose that the first k  —  to the construction of column k. If  1 columns have been constructed and let us proceed  S’k = Sk,  go to the next column. Otherwise, two cases  arise. (i) s’ >  Sk  Shift entries from the kth column to the columns k+1,• until we obtain the column sum the column sum reaches  k 5  ,  n by row rearrangements,  Assume that we have to stop shifting before  k 9  Then  I  =  {iIak0}  I’  =  j Vj>k} 2 {iIa=q  I”  =  [1,n]\ (lul’)  =  qjj for  j  k + 1,. , n whenever ak  =  0.  Let  Claim 1 There exist e E I and t < k such that a’et < qt Proof. Assume that no such pair (e,t). Then Let J  =  [1, k  —  qij for all i  =  e  I and all  1] U [k + 1, n]. Then by an argument similar to  j <k.  (*), we get a  contradiction to (2.7). I Claim 2 There exist  f E I” and u <k such that af  Proof. Assume that no such Let J  =  f and u exist. Then  [k +1, nj. Then by an argument similar to  to (2.7). I  =  0. 0 for all i E I” and all j <k.  (*), we arrive at a contradiction  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  Let’s construct a digraph G  { s, t}  (V, D), where V  =  =  {vi,...  ,  Vm}  U  .......  18  ,  W,_i}  U  and D consists of the following arcs:  If i E I”, there exists  j  >  3 v—*w  if  a<q  w,—v  if  aO  v—+t  if  iEI”  s—*v  if  iEI  k such that  < qjj. And ak  0 for all i E I. So if  there exists a directed path from s to t, then we can shift at least 1 from the kth column to one of columns k + 1,••• , n, by following the directed path. Now assume that no such directed path exists. Let 0 J  =  {j  <k  I’  =  {i  I’  12  =  I’\I  a directed path from s to w} a directed path from s to v}  Then 2 Vi1”UI  Vi So for any  j(<  k), either  0 a=0 &VjEJ  e I U I. & Vj =  0 a J  0 for all i E I” U 12 or  =  qjj =  Claim 3 There exist t and u (<k) such that t <u, a’et <  and  0 for some  f  . 1 qij for all i e 1U1  qet  for some e e I U I,  E I” U 12.  Proof. Assume that no such pair (t, u) exists. Let g be the last column before column k that has a nonzero a’fg for some  f  E  I” U ‘2 (by Claim 2 there exists such  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  19  g). Then  Vi e I U Ii  & Vj  g  =  qjj  =O 3 2 &g<Vj<k a ViEI”U1 Also, 2 ViEI”U1 ‘Ii Let J  e  ak=O  I U I & Vj > k a  =  qjj  [1,g]U[k+1, n]. Then by an argument similar to (*), we get a contradiction  =  to (2.7).  •  Claim 4 There exists another pair (t’, u’) of (t, u) different from (t, u) satisfying conditions of Claim 3 where t’ < u’ <t < ‘u.  Proof. Without loss of generality, we can suppose that a and all  j (t <j  u) and a 3  exists u’ < t such that  =  0 for all i E I” U  0 for some i  Vi E I U 12 Vi  e  I U Ii  ‘Ii E I U 12  =  2 t+1, h  =  u, h 3  and all  & h 1  Vj  2 a h  2 <Vj <h & h 3  4 k+1 and h  Vj =  qij for all i E I U I  j (u <j  k). There  I” U 12. Otherwise,  1 & Vj < h  Vi E I U I & h 3 where h 1  e  ‘2  =  4 h  =  0  =  qjj  =  0  =  qij  n. By letting J  =  ,3 1 [h ]U[h h 2 h , }, we 4  can get a contradiction to (2.7). Now assume that there is no such t’. Without loss  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  of generality, we can suppose that  =  e  0 for all i  I” U 1 and all  20  j (u’ <j  t).  Then Vi E I U Ii  2 ViEI”U1 Vi  where h  =  e  h  & Vj  = qij  & h<Vj<hi  I U Ii  1 & h  Vj  a=0  2 h  = qjj  Vi E I U 12  2 <Vj < h 3 a & h  =  0  Vi E I U I  4 a & h 3 <Vj <h  =  qij  u’ and h (i  =  1,... ,4) is the same as above. Let J  =  [1, h] U [h ,h 1 jU 2  ]. By an argument similar to (*), we get a contradiction to (2.7). I 4 ,h 3 {h By repeating an argument similar to Claim 4, we can get more pairs (t, u) satisfying th  conditions of Claim 3. To get the  pair, we would let J  =  [1, h] U [h ,h 1 ] U 2  ,_ h 2 [h , ] or [h 2 ,h 1 ] U•• U [h 2 ,h 1 _ 2 ]. With condition (2.7) we could get 2 U 1 21. Suppose that k < 21. Let J’  l different pairs of (t, u), unless k k  = qij  ,h 1 ] U 2 or [h  ...  ] (hi 2 U [h ,h 21  and we have l pairs <  Also, a 21  <121. =  =  —  1. So we get  J’ U [k + 1, nj. Now we can assume that k > 21  2p1,  0 for all i E I” U  ‘2.  there exists e E I U I’ such that 2 a 1 < So, 21 + 1 a  1 _ 2 q iéIUIi =  2p,  21, p is at most l  , (ji—i,ji) satisfying conditions of Claim 3 with  (jl,j2),  For any  1). Since k  iEIUIi  For any  <  for all i E I U I}. Then J’ is either [1, h] U [h ,h 1 ] U... U [h 2 ,h 1 _ 2 J 2  a contradiction to (2.7) with J  i <12  {j  p_ + 1 2 sj 1  there exists e E I” U 12 such that a’• el2p  2 0. Also, a  =  for all  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  21  . So, 1 iEIUI 2 + a  2 q iEIUIi  Since  = si,...  ak =  and  = Sk1  ,  —  1)  iEI”U12  p—1 2 si  =  Since sç  2 a  (  iEIUIi  j  there exists  s’k > Sk,  >  k such that s <  53.  0 for all i E I” U 12, >  > Sk+l.  iEIUIi  Also, s  qii jElUli  Let  321+1  and  be k and  321+2  and  {jl,j3,” ,j21+1}  (qjj  —  j,  respectively. Then for any  {j,j  (ii  —  ,  } 1 j_  C  ,j21+2},  qii +•• + qjj 1  >D  {j  qii +  —  qjj)  + qjj 1  —  qjj)  iEIUIi  (  q  (sji =  s  —  —  s  q)  —  +“  (  +  iEIUI  iEIUIi  sj + 2) + +  ••  31 + (s  +s  —  —  s  s  —  >  q)  iEIUIi  iEIUIi  + 2)  + 2p  This contradicts (2.6). (ii)  ‘k  <  Sk  Move some entries to the kt column from columns k + 1,•.. ments, until we obtain the column sum before the column sum reaches  Sk.  Sk.  Then  , n  by row rearrange  Assume that we have to stop moving =  0 for  j  =  k + 1,•..  , n  whenever  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  ak <qik.  T  Le  I I’  {ia<qjk} =  =Oforal1j=k+1,—..,n} 3 {iIIa  =  (IuI’)’  By the same arguments as in the case for s’k > that a’et <  22  qet  for some e e I” and a’fU  Construct a digraph G  =  sk,  0 for some  there exist t and u (< k) such  fe  I.  (V, D) in the same way as case (i), except that v—+t  if  iEI  s—*v,  if  iEI”  If there is a directed path from  s  to t, then we are finished. Assume that there is  no such path. Let 0 J  =  {j  <k  a directed path from  s  to  3 w  ‘2  =  {i e I’  a directed path from  s  to  v}  Il  =  I’\12  }  Then 1 ViEIUI  Vi So for any  j(<  e I” U 12  Vj  Jo a  = qi,  1 or a 0 for all i e Jul  =  qij for all i e I” U 12.  Claim 5 There exists t, u and v (< k) such that t <  u  <  e e I” U 12, afU  k), either a  0 a=0 &VjEJ  =  0 for some  f  , and a’gv 1 e 1U1  v, a’et  <qgv for some g  <  qt for some  E I” U 12.  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  Proof. We already note that there exists v such that a’gv Let v be the last column before column k that has Assume that there doesn’t exist u  <qgv  (<qgv)  (< v) such that a’f  23  for some 9 E I U ‘2. for some g  0 for some  f  I” U ‘2. E  I U I.  Then 1 ViEIUI  & Vj<h 1  Vi e I” U 12 & h 1 where h 1  v + 1 and h 2  =  =  k. Let J  =  a=0 2 h  Vj  = qij  2 , 1 [h j h . By an argument similar to  we arrive at a contradiction to (2.7). So there exists u some  (< v) such that a’j  (*),  0 for  f E I U Ii.  Now let u be the last column before column v that has nonzero a’f for some . Assume that there is not (< u) such that a’ 1 6 f E IUI  <qet  for some e E I”U1 . 2  Then  Vi  e  I” U  1 ViIUI  Vi where h  =  ‘u and h (i  e  =  & Vj  ‘2  h  = qjj  1 &h<Vj<h  I” U 12 & h  Vj  h  =0 3 a = qij  1,2) is the same as above. By letting J  =  [1,h] U 2 ,h 1 [h ] ,  we can get a contradiction to (2.7). I Similar to (i), we can get 1 different pairs (t, u) as in Claim 3 and an additional pair (v, k) by letting J unless k  =  [1, h] U [h ,h 1 jU 2  ...  ,] 1 _ 21 21 or [h h ,h 1 U [h ] U 2  ...  , ], 1 _ 21 21 h U [h  21 + 1. With these (1 + 1) pairs, we can get a contradiction to (2.6).  Also when k  21 + 1, we can arrive at a contradiction to (2.7). The proof of  Theorem 2.4 is completed.  Chapter 2. Integral Matrices with Given Row and Column Sum Vectors  2.4  24  Further Study  In Theorem 2.4, if 1 >  L--]  condition (2.7) has to hold for all subsets J of [1, n], yet  condition (2.6) is not trivial. It would be nice to have some condition in the spirit of (2.6) that becomes trivial, i.e. not a restriction, at the same time the number of cuts becomes exponential.  Chapter 3  General Factor Problem  3.1  Introduction  In this chapter we consider the following generalization of the factor problem which was introduced by Lovász [35],. [36]. Let G  =  (17, E) be a graph and, for each vertex v  e V,  let B be an arbitrary subset of {O, 1,... ,deg(v)}, where deg(v) denotes the degree of vertex v in G. We let 13  =  {BIv  e V}. The general factor problem asks whether there  exists a subgraph F such that for each vertex v E V, deg(v) have a gap of length p and k +p+l  1 if there exists an integer k  e Br,. A set B,, is said to  e B,, such that k+ 1,, k+p  B  e B,,. If we allow gaps of length more than one, the problem is NP-complete  [15]. Cornuéjols [15] gives a polynomial algorithm when G is simple and each B, doesn’t have a gap of length more than one. We restrict our attention to Br’s with all their gaps of length 1. We extend the result of Cornuéjols by giving a strongly polynomial algorithm for the case of multigraphs (possibly with loops) which seems likely to be more efficient even for simple graphs. We introduce a new type of augmenting walk for these matching problems which need not be alternating. It may be possible to obtain a strongly polynomial algorithm by using the idea of “sparse substitutes” which Gabow used for the (g, f)-factor problem [27]. Suppose that F is a subgraph of G. We say a vertex v has deficiency i with respect to B (written defF(v)  =  i) if i  =  min{Ik  —  deg(v) 25  k E B}  Chapter 3. General Factor Problem  26  The deficiency of F with respect to 13 is defF= defF(v) vEV  Our problem is seeking a subgraph F of minimum deficiency with respect to B, which we will call B-optimal or just optimal. A 13-factor is a subgraph F of deficiency 0, but we consider the more general problem. Throughout this chapter, let g,, (resp. i.e. B,, C  {g,,,.•  ,  f,,}.  an interval, i.e. B,,  f)  be the lower (resp. upper) bound of B,,,  First consider the relaxation of the problem where B,, consists of  = {gv, g,,  + 1, g, + 2,..  respect to (g, f) (written dei’ (v) i  =  =  f,,}  ,  and we say vertex v has deficiency i with  i) if  max{g,, —deg(v),0,deg(v)  The deficiency of F with respect to (g,  f)  def’F  —  f,,}  is def5’(v)  = vEV  A (g, f)-optimal s’ubgraph is a subgraph which minimizes Of course we wish to consider more general B,,’s. Given that the B’s are parity conditions (i.e. B,,  = {g,,,g,,  + 2,g,, + 4,...  ,  f,,}),  we proceed as follows. First we get a  (g, f)-optimal subgraph, using the strongly polynomial algorithm of Anstee [6] or Gabow [27]. Then decrease the deficiences of vertices whose degrees are in a gap using certain special augmenting walks. These walks are defined in Section 2 and refined by a series of lemmas in Section 3. In Section 4 we present our algorithm. In Section 5 we con sider general 13. We start with (g, f)-optimal subgraph and then use the reduction of Cornuéjols to a number of problems of the previous type. A (g, f)-optimal subgraph is important to our algorithm. If we don’t keep our intermediate subgraphs (g, f)-optimal, we may not get a strongly polynomial algorithm. The reason is given in Sections 3 and 5.  Chapter 3. General Factor Problem  27  Some warehouse problems can be interpreted as a general factor problem. We provide this made up problem to give at least one example where the general factor problem might arise. It does not involve multigraphs. A factory has to supply  n  customers and has  in  different potential locations of warehouses. Each location of a warehouse can serve up to 2 customers and can only serve some specified customers. A factory wants to select as few locations as possible to build warehouses and serve as many customers as possible. Construct a bipartite graph G  =  (A, B) where a vertex in A represents a location of a  warehouse and a vertex in B represents a customer. There is an edge between vertices v  and  w  if customer  constraint B,,  =  w  can be served by location  {O, 2} and each vertex  w  v.  Each vertex  v  in A has a degree  in B has a degree constraint B,,  =  {1}. A  subgraph F of G with the minimum deficiency gives a solution for the factory. 3.2  Augmenting Walks  In this section, we define augmenting walks, which are slightly different from the standard. They are not alternating in the usual sense of edges in F and in E  \ F.  Let A denote the symmetric difference between two sets, i.e. AAB Let F be a subgraph of G. A sequence of vertices and edges P e  =  (i)  , v) 1 (v_  0 v  =  =  (A\B)U(B\A). where  1 e 0 v  is said to be an augmenting walk in G with respect to F if  is a deficient vertex, i.e. deg(vo)  0 B,,  (ii) defFp(vo) <defF(vo) (iii) def (FAP) <def F (iv) there exists no P’  =  1 e 0 v  We say that e has label + if e  ekvk  (k  <  n) such that def (FAP’) <def F  F. Otherwise, e is said to have label  —.  Chapter 3. General Factor Problem  28  Our augmenting walks are different from other augmenting walks, which alternate between + and  —.  Our augmenting walks can have long runs of only + or only  —.  The next theorem shows that for any subgraph F, there exists an optimal solution which can be obtained from F by augmenting walks. Theorem 3.1 Given a non-optimal subgraph F, there exists an optimal F 0 which can be obtained from F by augmenting walks. Proof. Assume not. There exists an optimal F’ and a subgraph F 0 such that F 0 can be obtained from F by augmenting walks and such that FoLF’I is minimum. Since F 0 is not optimal, there exists a vertex v 0 such that defF 0 (vo) > defF’ (vo). There exists an edge e 1 E F /F’ such that } 0 1 { 0 defF (vo) €  <  (vo) is in a gap, then 0 def(vo). (If deg  choose any edge in F LF’ having v 0 0 as an end vertex. If deg 0 (v ) < g, 0 , choose an 0 edge in F’  . 0 \F  , 0 f,  If degF (vo) > 0  vertex of e . If defFo{ei} (vi) 1  choose an edge in F 0  0 (v defp’ ), then P 1  \ F’.)  Let v 1 be the other end  is an augmenting walk and  = v 1v e 0 1  contrary to the choice of F . So }(vl) 0 < defi(vi), (Vi). If 1 0 61 > df’ { 0 defF { 0 defF } (vl) € F”  =  F’/.{ei} is optimal and  IF”AFoI  <  IF’LFoI, a contradiction to the choice of  F’. So defFo{ei}(vl) > def’i(vi). There exists an edge e 2 E (F AF’) 0  \  {ei} such that  }(v1) < defFo{ei}(v1). By a similar argument as above, defFo{ei,e 2 defFo{ej,e }(v2) > 2 defFo{ei}(v ) 2 .  We continue growing a walk in this way.  eventually get a contradiction.  3.3  Since F AF’ is finite, we 0  •  General Factor Problem with Parity Conditions  In this section we study the general factor problem with parity conditions, that is, the elements in B are either all even or all odd. At the end of this section we consider the case that some Br’s are intervals. Let B  = {gv, g  +  ,  f}  where  f  = g,  some integer r. We assume that each B has this form, if no remark is given.  + 2r for  Chapter 3. General Factor Problem  29  We examine the reduction of Cornuéjols [15] of the B-factor problem on G to a 1-matching problem on G’ where G’ can be constructed as follows. Let {ei,... be the set of edges incident with vertex v. W  U  =  V 9 {nt}t1,...,k_  and let L  Let e t)  =  i.e. the graph (W, L) is a complete bipartite graph. t  =  (ni, v) for  =  I  j  1  j  1,••• , k  =  k and 1  Also add edges  t  k  ,  ek}  ,  let 9v},  —  (n2t_1, n t) 2  1,... , r. The graph G’ is the graph obtained from G by replacing each vertex  v  for by  the graph (W, L) as shown in Figure 3.1.  ni 2 fl fl2r-1 r 2 fl  flkg  Figure 3.1: If F’ is a maximum cardinality matching of G’, then F is optimal with respect to B where F is the set of edges subgraph of G and  v  (u, v)  such that  v)  is in F’ for some  j.  Let F be a  be any vertex of G. If deg (v) is in a gap, then we can consider  in G’ as Figure 3.2 (a) or (b), matching as many vertices  v  v  and n as possible. We can  easily change from (a) to (b), and vice versa. So this difference will cause no difficulties in our proofs. Similarly, deg (v) >  f’,.  and deg(v)  e  If deg (v)  v  in G’ can be considered as (c) if degF(v) <  e B,  <f  in F’ like (e) and (f).  and (d) if  all of v are matched like (e), (f) and (g). If deg (v) > g,  B, then at least one of edges  and (g). If deg(v)  g,,  and deg(v)  (n2t_1, n2t)  is in the matching F’ like (e)  e B, then at least one of edges  (n2t_1, n2t)  is not  0)  I’)  <II  -  II  II 0)  CD CD ‘1  a  I CD CD  a CD a  C) :3CD  3  C  CD  II  F\)  II  CD CD ‘1  a  II  CD CD T1  a  II  CD CD 11  a  -  CD  a  CD  II  -I,  CD  a  C.’,  CD CD ‘1  a  II (.11  CD CD ‘1  a  C)  I,  0  Chapter 3 General Factor Problem  31  Let F’ be a matching in G’ such that as many  (ui,  vi) is in F’ if and oniy if (u, v)  e  F and  and n are matched as possible (like Figure 3.2). Then an augmenting walk  in G with respect to F corresponds to an augmenting path for a 1-matching in G’ with respect to F’, and vice versa. So we can characterize an augmenting walk in G using this reduction. Lemma 3.2 Let P be any augmenting walk in G with respect to a subgraph F, say  P = v 1 —•ev. Except for n, the deficiency at v_ e 0 1 decreases and the deficiency at v  with respect to B increases each time e, is added to P, that is  defF{e,,...,ej}(vi_1) <  and defF{ei,...,et}(vi) > defFA{ei,...,e_i}(vi). Additionally defFAP(vo)  <  defF(vo) and defFp(vfl) < defF(vfl).  Proof. We will show this using induction on i. By the definition of an augmenting walk, Now let’s assume that defF{ ,...,€j(v1_1) < 1  defF{ei}(vo)  < defF(vo).  for i  defF{ei,...,e}(vj) > defF{ei,...,e_,}(vj)  k and  We can classify (i)  gVk  If degF{ 1  ...  e  So P,= v 1 e 0  <  k.  in the following cases:  vk  1 < degF{  for i  defFz{ei,...,e_i}(vi_1)  •••  6g  }(Vk) 1  }(VJ) 1  .  .  ekvk  . 1 degF{€ } (vk) ..  <  fvk  is in a gap, then  ...}(vk) E 1 degF{  is an augmenting walk and defF(vk) >  is not in a gap,  defFz{el,...,ek}(vk) >  Adding or subtracting any edge e 1 having  Bvk whatever ek is. defFAp(vk)  = 0. If  defFz{el,...,ek_l}(vk)  = 0.  as an end vertex decreases the  deficiency at vk. Thus defF{eI,...,ek+,}(vk) <defF{e,,...,ek}(vk).  (ii) } . 1 degF{e (vk) ..  <  gVk  If ek has label +, then P = defF(vk).  1 e 0 v  .  ekvk  Otherwise defF{el,...,ek}(vk) >  (the reduction to G’), we can tell that ek+1 defF{el,...,ek}(vk).  is an augmenting walk and defFtp(vk) < defFz{el,...,ek_l}(vk). must have  From Figure 3.3 (a)  label +. So defF{e,,...,ek÷l}(vk)  <  Chapter 3. General Factor Problem  (iii)  ,...,e_ degF{e } 1 (vk)  If  ek  = gVk  <  32  fr,.  has label +, then any edge having an end vertex  Vk  can be  ek+1.  If not,  ek+1  must have label + by Figure 3.3 (b). (iv) degF{ 1  ••k  }(vk) 1  = gVk = fvk  From Figure 3.3 (c) (resp. (d)), ek+1 must have label + (resp. (resp. (v)  —)  if ek has label  —  +).  }(vk) 1 ... 61 degF,{  fvk  Similar to (ii) and (iii).  (a)  (b) ek  e  (c)  (d)  Figure 3.3: The proof of Lemma 3.2 is completed. I By the above lemma, an augmenting walk doesn’t change deficiencies at middle ver tices and the deficiencies at v 1 and v decrease by one each, i.e. defF/p(v) for i  1, n and defFp(v)  defF(v)  —  1 for i  =  =  defF(v)  1 and n. The starting and ending  Chapter 3. General Factor Problem  33  vertices of P must be deficient, i.e. their degrees are in a gap or outside g and  f.  And  the degrees of middle vertices are not in a gap. For convenience sake, we state this fact as a lemma. Lemma 3.3 Let P be an augmenting walk with respect to a subgraph F. Then the degrees  of middle vertices in P are not in a gap and the start and end vertices are deficient with respect to F. The next lemmas contribute to a strongly polynomial algorithm for searching for an augmenting walk by showing that our walks only use vertices whose degrees are between g and  f  and only visit each vertex once (with some exceptions).  Lemma 3.4 Any shortest augmenting walk P with respect to a subgraph F goes at most  once through a vertex v having g,, < degF (v) < Proof. Let P such that  9v  1 e 0 v <deg(v)  f  and deg (v) E B,,.  Assume that P goes more than once through a vertex  <f,,  and degp(v) E B,,, that is  1 = v Vk = v  in P for some k  v  1.  Without loss of generality, we may let k be the first position in P such that v appears and 1 be the last one. Let’s consider the augmenting path F’ in G’ corresponding to P. If we can omit the edges e+ ,... , e from F’ where e is the edge in G’ corresponding to 1 e, then we can omit ek4,” , 1 e from P. Let e’k  = (viz, Ua)  and  1 e+  = (v’, w”).  Let’s consider the following cases: (i) One of ek and e 11 has label  —,  and the other has label + (Say ek has label +, the  other case is similar). Since ek has label +, e’k is not used in the matching F’. The vertex matched since degF(v) E B. So  Va  is matched to some  edges between e’k,+l and e in P’ by the matched edge  nt.  (v’, nt)  Va  must be  We can replace the and the unmatched  edge (nt, vb). Thus the edges ek+1,• ,e 1 could be omitted. See Figure 3.4 (a).  Chapter 3. General Factor Problem  (ii) Both of ej and e 11 have label Since deg(v) >  g,  34  —.  and deg(v) E B,, at least one of edges  matching F’ of G’. Since ek and ei+i have label (Va, n t_l) 2  —,  e’k  t_l, n 2 (n t) is in 2  and e+ 1 are in F’. Thus  t, vb) are not in F’. We can replace the edges between 2 and (n  in P’ by the edges  (Va,  t_l), 2 n  t_l, n 2 (n t), 2  the  t, vb). Thus the edges 2 and (n  4+  and e  ek+1,  ,e  could be omitted in P. See Figure 3.4 (b). (iii) Both of ej and e 11 have label +. Since degF(v) If  (Va,  <fr,  and deg(v) E B, at least one of edges  t_l) and (n 2 n t, vb) 2  between e+ 1 and e  in  are in  F’ (or  (Va, n t) 2  and  t_l, vb)) 2 (n  P’ could be replaced by the edges  t, vb). Assume not. Fortunately we could match 2 (n  tl, 2 2 (n n t ) is not in  (like (c)), the edges  (Va, n t_l), (n 2 t_l, n 2 t) 2  t to 2 n  v’.  Similarly  vb to  j• Also  t_l 2 n  Without causing a problem, we could match vb  n instead of t could be matched to 2  and  Va to 2 n t _l, v” to fl2t without  causing a problem. Since ek and e,+i have label +, e’ and e+ 1 are not in F’. is matched to one of vertices n, and  F’.  is matched to  Va to  4 t 2 n  VC,  a  and  instead of nP.  like (d). We could delete the  edges between e+ 1 could be 1 and e from F’. Hence the edges between ek+1 and e omitted. The proof of Lemma 3.4 is completed. I Lemma 3.5 Any shortest augmenting walk P goes at most once through a vertex v such  that deg(v)  = g,  or  f  edge coming into v is  —  except in the following cases. When deg(v) (resp.  +)  —  (resp.  (resp.  and the edge going out from v is + (resp.  first visit. In the second visit, the edge coming into v is + (resp. out is  = liv  —)  f)  —)  the  in the  and the edge going  +).  Proof. We will only consider  v  having deg (v)  = g,.  It is similar in the case that  Chapter 3. General Factor Problem  35  (b)  (a)  ek  2t fl2t 1 e  Figure 3.4: deg(v)  =  f.  Let P  1 e 0 v  Assume that P goes through  Let k be the first position in P such that If at least one of ek and  1 ej  v  v  more than once.  appears and 1 be the last one.  has label +, then we can omit the edges  ek+1,  ,e 1 from  P by the same argument as Lemma 3.4. Suppose that both of ek and into closed walks C 2 (i ends in  v.  =  ei+i  have label  1,•.• , m) including  v  —.  The edges  ek+1,  ,e 1 can be divided  only once, i.e. each C starts from  v  and  If there exists C 2 such that both starting edge e 8 and ending edge et have  label +, we can delete edges  ek+1,  ,e _ and edges 8  et+1,••  as Lemma 3.4. The new augmenting walk goes through leaves with +, next arrives with + and leaves with  v  ,e 1 by the same argument  twice, first arrives with  —  and  —.  Now, let’s show that such a C, exists. Assume not. Then in each C , at least one of starting edge and ending edge has label  —.  Since ek has label  1 must have label + by Lemma 3.2. So the ending edge of C  —.  —,  ek+1  must have label  Thus the next edge, i.e.  Chapter 3. General Factor Problem  36  the starting edge of C 2 must have label +, etc. So every starting edge of C 2 has label + and every ending edge has label —. But the ending edge e 1 of Cm must have label + since el+l has label  —  by Lemma 3.2. Thus we get a contradiction. I  In the next lemma, we insert the extra hypothesis that F is (g, f)-optimal. Then an augmenting path doesn’t go through certain vertices, and avoids certain unpleasant possibilities such as a pseudopolynomial algorithm when our walks visit a vertex v a number of times comparable to deg (v). Lemma 3.6 If F is (g, f)-optimal, then an augmenting walk P with respect to F doesn’t  go through vertices v such that deg(v) <gv or> Proof.  f.  Assume that P goes through some vertices v such that deg(v) <gv or>  f.  Let  u be the last vertex of this type that P goes through. Say deg(u) <gu (it is similar if deg(u) >  f).  If u is the end vertex of P, then defFp(u) <defF(u), and hence the  degree of u in FAP is bigger than in F. So def(u) < defS’(u). By Lemma 3.2, the deficiencies relative to B at middle vertices don’t change. So the deficiencies with respect to (g,  f)  at those vertices don’t change. Also the deficiencies with respect to B at  the start vertex of P decreases, so the deficiency with respect to (g, Thus the deficiency of FL\P with respect to (g,  f)  doesn’t increase.  is less than of F, a contradiction.  Suppose that u is not the end vertex of P, i.e. P = v 1 e 0 Let F’ = uek+lvk+1  f)  vk_lekuek+lvk+1  By Lemma 3.2, the deficiency with respect to B at u  increases when ek is added to P and the deficiency with respect to B at u decreases when ek+1 is added to P. So ek must have label deficiencies at v relative to (g,  f)  —  and  ek+1  must have label +. For i > k,  don’t increase. Thus the deficiency of FAP’ relative  to (g, f) is less than of F, a contradiction that F is (g, f)-optimal. I By Lemma 3.6, an augmenting walk P with respect to a (g, f)-optimal F starts and ends at vertices whose degrees are in a gap. Suppose F is a (g, f)-optimal. We seek a  Chapter 3. General Factor Problem  walk of vertices  v  37  such that degF(v) E B,, which joins a pair of vertices whose degrees are  in a gap. The walk doesn’t increase deficiencies at middle vertices in the way described in Lemma 3.2. In an augmenting walk P =  (+ or and  ek  —)  <deg(vk) <fvk,  if  has label  —.  deg(vk)  If deg(vk) =  can have label + (resp.  —).  1 e 0 v  =  •  9Vk  ekvI  and  ek  ek+1  can have either label  has label +, or deg(vk) = fvk  (resp. fvk) and ek has label  gVk  —  (resp. +),  ek+1  Our augmenting walks are close to being paths, which go  through each vertex at most once with some exceptions described in Lemma 3.5. We can find an augmenting walk by a blossom algorithm. It can be completed in O(1V1 ) 2 or  O(IIEII)  operations where  hEll  is the number of edges in the simple graph associated  with G. The details of the algorithm is given in the next section. We can extend the above properties of an augmenting walk to the case in which some Be’s are intervals. The difference occurs at an end vertex of the augmenting walk. Let F be a (g, f)-optimal subgraph. An augmenting walk with respect to F starts from a vertex whose degree is in a gap, and goes through vertices following the way described in the above paragraph. But it ends if it reaches either a vertex whose degree is in a gap or a vertex at  v  v  such that B is an interval and the changes do not increase the deficiency  with respect to 23 (i.e. it reaches  an edge labelled  —  and degF(v)  >  by an edge labelled + and deg(v)  v  <  fr,, or by  gv.). If an augmenting walk ends at a vertex v such  that B. is an interval, then it decreases the deficiency with respect to 23 by one, only at the start vertex. It is a remarkable invariant of our algorithm that our subgraph remains (g, f)-optimal after an augmentation, so our subsequent augmenting walks have the same structure. If we don’t have a (g, f)-optimal subgraph, we might have to look for augmenting walks more than polynomially many times in  IVh.  algorithm for finding a 23-optimal factor.  We would not obtain a strongly polynomial  Chapter 3. General Factor Problem  3.4  38  Algorithm for General Factors with Parity Conditions  In this section, we describe an algorithm that finds an optimal solution with respect to B when each B consists of same parity elements. Our algorithm parallels an algorithm of Cornuéjols for simple graphs. First, we get a (g, f)-optimal solution using the strongly polynomial algorithm of Anstee [6], which will  3 + MCF(IVI)) time where MCF(IVI) is the time for a minimum cost flow O(1V1 algorithm on a lvi vertex network. Next look for an augmenting walk connecting two  take  vertices in a gap. Our algorithm for an augmenting walk is a slight variant of Edmonds’ blossom algorithm [16], which finds the maximum 1-matching in a simple graph. The augmenting path in his algorithm is alternating, but our augmenting walk is not. And some edges can be used twice. The following is a rough outline of the algorithm for an augmenting walk with respect to a (g, f)-optimal subgraph F. We form a multigraph G* on vertices of G such that g,  deg(v)  f,  with the edges in two classes E, E. The edges of E consist of one  copy of an edge e = (u, v) in F such that 9u  deg(u)  <f  and g  min{multiplicity of e in F, 2} copies of e such that deg(u) =  f  deg(v)  <fr,  or deg(v) =  and  f.  The  edges of E consist of one copy of an edge e = (u, v) not in F such that g, <deg(u)  <f  and g, < deg(v)  f,,,  and min{multiplicity of e in G  —  multiplicity of e in F, 2}  copies of e such that deg(u) = g or deg(v) = g. As described in Lemma 3.5, those edges e = (u, v) in F (resp. not in F) such that deg(u) = deg(u) =  g  or degF(v) =  g)  f  or deg(v)  f  (resp.  can be used twice in an augmenting walk.  Choose any vertex w whose degree is in a gap. We form a directed tree directed out from w. The tree grows vertex by vertex (Step 5) where we use the notation p(v) =  ‘U  to denote that u is the predecessor of v in the tree. The edges of the tree are stored separately from G* to keep them from being used again. A vertex v is given a label +  Chapter 3. General Factor Problem  39  —) if the edge leaving v can have label + (resp. —). That is, the edge leaving v can label + (resp. —) if 9v deg(v) < f or deg(v) = f (resp. g, < deg(v) f  (resp. have  or degF(v) = gv) and the edge arriving v has label — (resp.  +). Note that this is the  reverse of the usual labelling which identifies the edge which reaches the vertex. If an edge which, when added to the tree, creates a cycle, then the cycle is called a blossom. We shrink the vertices of the blossom to a single pseudovertex. We give the pseudovertex labels +,— and these labels apply to all vertices of G contained in it (Step 4). One of the vertices of the blossom may be a pseudovertex and so there may be nesting of blossoms. An outermost blossom or pseudovertex in this inductive structure is called exposed. For each blossom, one vertex (possibly a pseudovertex) is distinguished as the base vertex being the vertex of the blossom closest to the root of the tree. Another item we introduce here is the true base of a blossom. If the base of a blossom is not a pseudovertex, then it is the true base. Otherwise the true base is inductively defined as the true base of the base of the blossom. We call a starter walk a walk P  1 e 0 v  e,v,, which can be the first part of an augmenting walk, i.e. deg(vo)  is in a gap and the deficiency at v 0 with respect to B decreases, and the deficiencies at v (1  i  n — 1) don’t change.  We use the term dual to refer to the replacement of E by E—, g by  f by gu <deg(v)  f, g,  deg (v) <  f, F by Fc, and vice versa.  Algorithm for Finding Augmenting Walks Step 1. (Initialization) Form a multigraph G* = (V*, E*) possibly with loops where V = {v e V deg (v)  f } and  E* are divided into two classes E, E. The edges of E  one copy of edge e = (u, v) for e  F such that g  deg(u)  <f and Yv  and {the number of e in F, 2} copies of e such that degF(u) =  consist of  deg(v)  f or deg(v)  =  <f  f. The  Chapter 3. General Factor Problem  40  edges of E+ are the dual of E. Choose a vertex w whose degree is in a gap. Put w on the list of unscanned vertices, and w gets labels + and  —.  Step 2. If the list of unscanned vertices is empty, STOP (there is no augmenting walk from w to another vertex whose degree is in a gap). Otherwise select one vertex u from the list. Step 3. If u has label Step  —,  do Step 4, 5, and 6. Otherwise do Step 7.  4. (Search for blossoms)  Search for any edge (u, v) E E  where v is in the tree and has label  —.  If there is  such an edge, it forms a blossom in the tree which we shrink to a pseudovertex. The pseudovertex is given labels + and  —,  and is added to the list of unscanned vertices. The  vertices contained in the pseudovertex are deleted from the list. Return to Step 2. If there is no such edge, go to Step 5. Step 5. (Grow tree) For all vertices v not in the tree, do the following. If there is an edge (u, v) E E, then put v in the tree with p(v)  =  u. v gets label + if deg(v)  = ge,,  otherwise + and  —.  The  chosen edge is deleted. Add v to the list of unscanned vertices. If deg(v) is in a gap, STOP (there is an augmenting walk from w to v). Step 6. Consider u to be scanned and delete u from the list of unscanned vertices. Return to Step 2. Step 7. Do duals of Steps 4, 5, and 6. Since the number of edges in E* is finite, our algorithm will terminate. The following three lemmas verify that our algorithm works correctly. That is, the assertions made in  Chapter 3. General Factor Problem  41  Step 2 and 5 are true when the algorithm stops there, and an augmenting walk in G* which is found by the algorithm corresponds to an augmenting walk in G. Lemma 3.7 Suppose that 0 is a pseudovertex with true base b and b has label + when  b is added to the tree. Then for each vertex v of 0, there exists walks W 1 and W 2 from b to v satisfying: (i) W (i  =  1, 2) starts with an edge of label +.  (ii) for a starter walk P from w to b in which the next edge can be label + and none of vertices in 0 except b is in P, P U W 1 (resp. P U W ) is a starter walk from w to 2 v such that the next edge can be label + (resp.  —).  The similar argument holds for the case that b has label  —  when b is added to the tree.  Proof. Let 0 be a pseudovertex with a base b given in the tree by two dipaths u .. 1 be v 1 be’ joined by the edge e joining u and  Vq.  .  e’v  First, assume that none of the vertices of 0 are  pseudovertices. Let u,. be an arbitrary vertex in 0. Let W 1  =  u 1 be  .  None of u 2  is in P, so the deficiencies of the vertices in P other than b do not change by adding W 1 to P. If b has label + (resp.  —),  then e 1 has label + (resp.  —).  The deficiency of b is  not changed by P U W . None of u has a change in its deficiency by W 1 , except u. So 1 1 is a starter walk. Assume that in PUW PUW 1 the next edge has only one label + or say +. Then deg(u)  = ga,.  an e has label  The edge er+1 has label + (if u,.  =  u,  —, so u,.  er+1 =  —,  must have only label + in the tree.  e). Let W 2  =  v 1 be’  .  e’qvqeupep  •  e1ur.  Then PUW 2 is a starter walk by a similar argument as above. Since er+1 has label +, the next edge in P U W 2 can be label  —  in any case. Now, let’s assume that one of vertices  Chapter 3. General Factor Problem  42  of 0, say u , is a pseudovertex and eu 3 . The edge e 1 8 hits u 3 at its true +i is part of W 8 e 3 base b 8 and e +i hits u at one of vertices of 8  u,  x. Using induction, we can construct  a walk from b 8 to x consisting of nonpseudovertices with the appropriate operations, so that it can replace u . Similarly, each pseudovertex in the walk W 3 2 can be expanded. For label + (resp.  —),  we can get a walk from b to  Ur  consisting of nonpseudovertices  where the union of this walk and P is a starter walk and the next edge can be label + (resp.  —).  I  Lemma 3.8 If a vertex v is in the tree with a label + (resp.  —),  then there is a starter  walk from w to v such that we can extend the walk from v by an edge with label + (resp.  —)  if such an edge exists.  Proof If v belongs to a pseudovertex, then let v, be the pseudovertex containing v. Otherwise let v be v. There exists a dipath v 1 e 0  in the tree where v 0 is w or  the pseudovertex containing w and some v may be pseudovertices. If v = w, then it is trivial. If v 0 = v, i.e. v and w are contained in the same pseudovertex, we can get the desired walk from w to v using Lemma 3.7. Now suppose that vo  v. Then e  hits va_i at a vertex u, where ‘u may be v_ itself or one of vertices of  Vn_  if  is  a pseudovertex. Without loss of generality, we may assume that there is a starter walk P from v 0 to u, and the labels of u and e agree. First, let’s consider the case when v =  —.  v. Say v has label +. Then 9v  degp(v) <  f,  or degF(v) =  f  and e has label  In the both cases, the next edge can have label +. Now consider the case that  v  is  a pseudovertex with its true base b. Then we can construct the desired walk by adding to P the walk from b to v found by the method in Lemma 3.7. I Let’s denote ‘Tn’ the set of descendents of v, i.e. {u inductively we define  pk(u)  = p(p’(u)) for k  2.  I 9(u)  = v for some k  }  where  Chapter 3. General Factor Problem  43  Lemma 3.9 If there is a starter walk from w to a vertex v such that we can extend the  walk from v by an edge with label + (resp.  —),  then v is in the tree with a label + (resp.  -). Proof. Let P  =  1 e 0 v  be the starter walk from w to v (v 0  Let’s assume that the label of v and e+i agree for i  =  0,... , n  =  w and  v).  v  1. If v, has not been  —  is being scanned, e is still in G* and so v,., will be given  in the tree yet, then when label +.  Assume that v, is already in the tree and has label the edge p(Vn)  (p(Vn),  Vj  and v E  has both labels + and  for r  —.  p(Vn_i) = v.  <j  If p(v ) 5  =  Assume that v 8 (r <s < n (s  Vj  —  Vq1,  So  <i  <j  n—i,  1) has only one label, say +. n  —  1) has both labels + and  —  in any case.). So  If p(v ) 81  P(Vs)  by the edge e +i forms a blossom which gives v label 8  There exists q such that p(Vq)  —.  then v 3 has both labels (Since the labels of v 8 and e +i agree, e 8 + has 3  label +. So v. get label v. and  f and  Then there exists r (it may be 1)  n—i. First let’s show that for r  Without loss of generality, we may assume that  —.  =  v, then joining v_ and v,, by the edge e forms a blossom,  so give v label +. Now suppose that yr  Then deg(vfl)  v) has label +. Since the next edge can be +, er-, must be  . If p(Vn.1) 4 v,  such that  —.  joining  Vq  vq+1  and  g  r  and  by the edge  Vq+1  8 gets both labels. So all v (r v Since the label of  and v E T 8 for s  <j  er+1  n  —  eq+1  <j  —.  v,  then joining  Thus P(Vs+i) =  q. Since  p(Vqi)  Vq  forms a blossom which contains  1) have both labels, in particular  Vs.  and  v.  So  yr  by  rl•  agree and v 1 has both labels, joining  the edge e+i forms a blossom, which contains v,. Hence v gets both labels.  and  •  Our algorithm works also when some Bs are intervals, with one exception. In Step 5, it stops also if B is an interval and deg(v) <ft. We can get a (g, f)-optimal subgraph F in  +MCF(IVI)) time. We can decrease 3 O(V  Chapter 3. General Factor Problem  44  lvi, one per vertex. We need grow a tree takes O(ivI ) time. We obtain the following 2  the deficiency with respect to B by at most at most once from each vertex, and this theorem.  Theorem 3.10 A subgraph with minimum deficiency with respect to B, where each B is an interval or a parity condition, can be found in O(1VI 3+ 3.5  MCF(IVI)) time.  General Factor Problem Allowing Gaps of Length 1  In this section, we study the general factor problem where each B is an arbitrary subset of {O, 1,.  .  ,  deg(v)} without gaps of length 2 or more. We can get a B-optimal fac  tor by solving a “few” general factor problems with parity conditions directly following Cornuéjols [15]. If x and y are integers, [x, y} denotes the set of integers {x, x + 1,••. , y} if x {.x, x  —  1,... ,y} otherwise. For a given subgraph F, let  l’  =  min{t  u’  =  max{t  B, all the elements of {t, deg(v)] fl B, have the same parity}  e  B all the elements of [t, deg(v)] fl B, have the same parity}  and pF  — —  hF  v 6 L  ,  Fl j  p  All the elements of B have the same parity, and either l —1 either u’ + 1 E B or u’  =  e  B, or l’  f.  Let i,F  L)  For any w E V such that l F  —  = {LV}VEv,  =  Fi  i  IvV  1 E B, let where L  IB  I  {l—1}  forvV\{w} forv=w  =  gj,. Similarly,  Chapter 3. General Factor Problem  and for any w  45  e V such that u + 1 E B, let F_I j w —  vJvEV,  I (  _j  wiiere  =  BF V  for vEV\{w}  {u’+1}  for  Theorem 3.11 (Cornuéjols [15]) The deficiency of F with respect to B is minimum if and only if there exists no subgraph with smaller deficiency with respect to one of the following families than the deficiency of F with respect to B: (i) B’ (ii) £ for w (iii) U’ for w  e V such that l  1  eB  V such that u + 1  eB  —  Cornuéjols gave an algorithm for finding a B-optimal subgraph which proceeds as follows. First find a (g, f)-optimal subgraph F. We can only decrease the deficiency with respect to B by  VI.  To get an improved solution or find that F is optimal with  respect to B, we use Theorem 3.11 and consider at most  21V1 + 1 general factor problems  with parity conditions. Then we may need to solve O(1V1 ) general factor problems with 2 parity conditions to obtain a B-optimal subgraph. We must consider the complexity of computing £‘, UF, and BF which involves the computation of l’, u. These issues did not arise for Cornéjols for simple graphs. It is sensible to imagine that B is given as a partition B if k  eB 1 and 1 e  and i  <j, then k  =  2U 1 U B, B  U Bq) where  < 1. Also each B, is a parity condition or an  interval and so can be conveniently expressed by its smallest and largest elements. Then the complexity of determining l’ and u is O(logt(v)). We let that the size of the problem is at least  =  maxt(v), and note  .  Theorem 3.12 A subgraph with minimum deficiency with respect to B can be found in  strongly polynomial time  MCF(IVI) 2 5 + IVI O(1V1  + Vlogt).  Chapter 3. General Factor Problem  46  Even though we cannot reduce the complexity of our algorithm theoretically, we can make some heuristic improvements as follows: In £ = {L} vEV, let L = —  3.6  1 instead of setting L = {l  —  including  1}. Similarly for U’.  Further Study  We can consider the following generalization of the general factor problem: For each vertex v  e V, we have costs below(v), above(v) and gap(v) for violating its degree  constraint. Suppose that F is a subgraph of G. The weighted deficiency of v with respect to F is defined by above(v)  .  (g(v)  —  deg(v))  below(v) (deg(v) .  —  f(v))  defF(v) =  if deg(v)  <g(v)  if deg(v) >  f(v)  gap(v)  if deg(v) is in a gap  0  otherwise  The vertex weighted deficiency of F is defined by: defF= defF(v) vEV  One of our future tasks is looking for an efficient algorithm finding a subgraph F of minimum vertex weighted deficiency, perhaps analogous to the results in [6].  Chapter 4  Square-Free Two-Factors  4.1  Introduction  A two-factor of a graph G is a spanning subgraph in which each vertex has degree 2. A two-factor of G consists of disjoint cycles that together cover all vertices of G. If a two-factor consists of only one cycle, then the cycle is a hamiltonian cycle. As is well known, the problem of finding a hamiltonian cycle of a given graph is NP-hard [30]. The problem of finding a two-factor is in P [18]. It is interesting to ask whether or not there is a polynomial algorithm to find a restricted two-factor, especially the following type of a restricted two-factor: a two-factor of G in which the cycles are restricted to having lengths from a prescribed set L of integers, where L  {3, 4,5,.  •}.  Let L—  =  {3, 4,5,.  . .}  —  L.  The problem stated in this form is due to P. Hell, D. Kirkpatrick, J. Kratochvfl, and I. Kfl [32] and they showed that the problem is NP-hard unless L already that a polynomial algorithm exists if L  =  q. In the case  C {3, 4}. We noted =  {3}, we call it  a triangle-free two-factor and it is shown by D. Hartvigsen [31] that it can be solved in polynomial time. The algorithm is very complicated as in the proof, but not nearly so complicated as our algorithm in the proof. We found a few errors which we believed to be fixable but did not spend sufficient time to check carefully the result of Hartvigsen. It is unknown whether the problem is in P or NP-hard or otherwise when L  =  {4} or  { 3, 4}, we refer to them as a square-free two-factor or a {triangle, square}-free two-factor. These two cases are at a kind of frontier between P and NP-hard problems. One might  47  Chapter 4. Square-Free Two-Factors  48  perhaps justify the complexity of our algorithm by the problems proximity to NP-hard problems. It was shown by 0. Vornberger [54] that the edge-weighted version of the {triangle, square}-free two-factor problem is NP-hard. The edge weighted version of the {triangle, square}-free two-factor problem is: For each edge e of G, a weight w(e) is assigned. The weight of a subgraph F of G is the sum of weights over all edges of F. The problem is finding a {triangle, square}-free two-factor which has maximum weight. D. Hartvigsen conjectured that the edge-weighted version of the triangle-free two-factor problem is in P [31]. The case of a two-factor without any restriction can be solved using a b-matching algorithm and it was shown by Pulleyblank that the b-matching problem is in P [44]. In this chapter, the unweighted version of the square-free two-factor problem is stud ied. Unfortunately we still don’t know whether or not it is in P. We think that it’s in P. An augmenting path theorem like Berge’s augmenting theorem for 1-matching [7] has been obtained. The augmenting paths are alternating and we need concern ourselves with squares being created locally. A similar result was obtained in [32] by P. Hell, et al. If a subgraph F of G is not optimal, then there exists an augmenting walk W which is alternating and the symmetric difference between F and any initial subwalk of W is square-free. An augmenting path having such nice properties does not necessarily exist for L-free two-factors if L  {3, 4}. In Section 4.11, we give an example showing that  there is no augmenting path for the case L  {3, 4} having such properties as in the  case L C {3,4}. Our contribution is a polynomial algorithm for finding a square-free two-factor of G when the squares of G are vertex-disjoint. We restricted the problem to this case, because our initial investigation suggested that the algorithm for a general graph was too complicated. However we have not discovered any impediment for the existence of a polynomial algorithm for the general square-free two-factor problem. But even the  Chapter 4. Square-Free Two-Factors  49  restricted case we solve seems highly complicated. We use the idea of Edmond’s blossom algorithm [16] to find an augmenting walk. Our algorithm is more complicated than his algorithm and analogous to the algorithm by D. Hartvigsen [31] for the case of trianglefree. We grow a tree from each deficient vertex until two trees are joined. We get a path joining two deficient vertices in a shrunk graph, which is obtained from G by shrinking a set of vertices into one single vertex. To recover an augmenting walk in G corresponding to the path, we use an algorithm called Recover Algorithm. We obtain a Tutte-type theorem which proves the nonexistence of a square-free two-factor when the algorithm stops without having found one. This theorem gives a necessary and sufficient condition for the existence of a square-free two-factor of G where its squares are vertex-disjoint. It gives a necessary condition for the existence of a square-free two-factor when G is an arbitrary graph, but we don’t know whether it is a sufficient condition also. In Section 2, the Berge-type augmentinhg path theorem is presented and proven in the general case where the squares need not be vertex-disjoint. Our Blossom Algorithm uses the ideas from Section 2 but does not rely on the result. Section 3 consists of two descriptions of the Blossom Algorithm. The second one is more detailed than the first one. A reader will find this sction essential in understanding the Blossom Algorithm presented in Section 4. The Recover Algorithm is presented in Section 6 beginning with a brief description. Section 5 contains some useful results about the Blossom Algorithm that tell us how to handle certain cases in the Recover Algorithm. Section 7 proves the validity of the Recover Algorithm and hence the Blossom Algorithm. In Section 9 the Tutte-type Theorem, Theorem 4.11, is proven. It verifies the termination of the Blossom Algorithm in Step 7 is correct. Some technical lemmas are proven in Section 8 for use in Theorem 4.11. Having completed the proof that the algorithm works correctly, we compute its complexity in Section 10. Our algorithm runs in O(EI  .  ) time. We 5 1V1  conclude with Section 11 a brief consideration of problems for further study.  Chapter 4. Square-Free Two-Factors  4.2  50  A Berge-type Theorem  In this section, we will introduce a Berge-type augmenting walk theorem. We wish to alert the reader that in this section squares of G need not be disjoint; we are able to handle the general case. For an unrestricted two-factor, a minimal augmenting walk with respect to a (0,2)factor F is an alternating trail between edges in F and not in F which joins two deficient vertices. For a square-free two-factor, an augmenting walk is rather complicated. The walk need not be a trail, since some edges can be used twice. In Figure 4.1, F is not a square-free two-factor. Let F’  =  {ei, e ,e 3 ,e 9 , eio}. Then FAP’ is a square-free two8  factor. Note that F’ is not a walk and the reader can easily see that there is no augmenting trail like for the case of simple two-factors. Let P  10 8 7 9 3 0 . 1 e 2 v  =  If  we alternately add and subtract edges along P to F starting from addition, then the resulting one is FLP’. Note that edge e 2 is subtracted first and added later. Let P  be a walk where e,  2 1 e 0 v  =  =  , vi). 1 (v_  Define  FP=FU{e :iodd}\{e, :ieven} Let  Cvwxy  denote a square in G whose vertices in cyclic order are  Pk the initial siibwalk of P of length k, i.e. Ph free (0,2)-factor. A walk P  =  2 1 e 0 v  =  2 1 e 0 v  v,  w, x and y. Denote  ekvk.  Let F be a square  ev is said to be an augmenting walk in G  with respect to F if (i)  0 v  and  v  are deficient, i.e. deg(vo) and  deg(vfl)  <2,  (ii) edge e 2 (resp. e i+i) is in F (resp. not in F) and edge e appears in P only once 2 with a possible exception. The exception is the following: In Figure 4.2 if edge (v,  w) is chosen as +i 21 and any other edge in e  Elvwxy  is not in P , then (w, x) 2  Chapter 4. Square-Free Two-Factors  51  Figure 4.1: must be chosen as  2j+2 8  (by (iii)) and later (w, x) can be chosen  as e2k+1 for some  k > i, (iii) for any i, F  2 doesn’t have any square, and P  (iv) F e P doesn’t have any square.  Figure 4.2: Theorem 4.1 will show that for any square-free (0, 2)-factor, there exists a square-free two-optimal subgraph which can be obtained from F by augmentations. Our augmenting  Chapter 4. Square-Free Two-Factors  52  walk is almost a trail, except that only some edges can be in P twice. Even though it’s not alternating between edges in F and not in F, edges along P are alternately added and subtracted. The spirit of alternation is preserved. Note that if we alternately add and subtract edges along any initial subwalk of even length, then the resulting factor is square-free. The proof of Theorem 4.1 follows the proof idea of Theorem 4 in [32] where the triangle-free case is also considered, though the case arguments here become more com plicated. Theorem 4.1 Suppose that F is a square-free (0,2)-factor of G and non-optimal. Then there is an augmenting walk with respect to F. Proof. We will prove the theorem by contradiction. Assume not, that is there is no augmenting walk with respect to F. Let F 0 be such that  FLFoI  is minimum over  all  square-free subgraphs F 0 of G with def F 0 <def F. Then F 0 is as close to F as possible among less deficient subgraphs. Without loss of generality, we can assume that F 0 is a (0,2)-factor and F 0 has the minimum number of vertices v with deg (v) < deg(v) 0 among the subgraphs described above. Since def F 0 < def F, there is a vertex v 0 such that defF (vo) < 0 degp(vo) (vo,vi)  e  (vo) 0 deg 0 F  \ F.  2 (by Lemma 4.2), degp(vo)  Let P be a maximal walk, P  =  <  defF(vo).  Since  (vo) and there is an edge 0 deg  1 e 0 v  satisfying the  following conditions: (i) All e 21 (resp. e 0 \ F (resp. F \ F ) with some exceptions. The exceptional 0 ) are in F 2 case is the following: In Dvwxy, (w, x) and (y, v)  F fl 0 F (x, y) E F and (v, w) ,  0 F  (Figure 4.3). The edge (w, x) can be chosen as e 2 and later it can be chosen as  e2k+1  (k>i). (ii) It doesn’t have the following eleven forbidden configurations (Figure 4.4):  53  Chapter 4. Square-Free Two-Factors  0 EF  Figure 4.3: (a) There is an edge (w, w’) E F  22 \P  with w  2 \P  with (v ) 0 , w) E (F fl F 21  22 (v v , +i, w) E F 2  0UP ) 2 \ (F  and  ,w’) E F\P 2 (v . 2  (b) There is an edge (w, w’)  F  2 \P  and (v , w’) E 2  UP 0 F\(F J 2 .  (c) There is an edge (w,w’) E F  0UP ) 2 \ (F  with w  22 (v v , ,w’) E 22 +i,w) and (v 2  )\P 0 (FnF . 2  (d) There is an edge (w, w’)  e  F  0U) 21 F \ (F  e  F  0U) 21 F \ (F  with w  22 (v v , , w) E F 1 + 2  21 P \ (Fo U )  and (v , w’) E F 21 0 fl P g. 2 (e) There is an edge (w, w’)  with (v , w’) 21 , w) E F 21 0 fl P 2 and (v  e  ). 2 F\(FoUP  (f) There is an edge (w, w’) E (F fl F ) 0  2 with w \P  i, w) 2 22 (v v ,  e  F  0U) 21 P \ (F  \ F)  U H 21 and  and (v ,w’) E 21 21 \F)UH 0 (F . 21 \P  with (v i,w) € (F 21 0  0 fl P F 21 with w  22 (v2i, w) E F v ,  ) 0 (g) There is an edge (w,w’) E (F fl F ,w’) E F 21 (v  0 UP ), 21 \ (F  (h) There is an edge (w, w’) ,w’) E F\P 21 (v . 22  e  0U) 22 F \ (F  and  Chapter 4. Square-Free Two-Factors  54  0 fl P 2 with eF  (i) There is an edge (w, w’)  i, 2 (v  w)  ) \P 0 , w’) e 2 e (F fl F 2 and (v  UP 0 F\(F ) 2 .  (j)  0 fl P 2 with w eF  There is an edge (w, w’) ,w’) 2 (v  22 v ,  , w) 21 (v  E F  0U) 22 P \ (F  and  . 2 e (Fo\F) UH  0 fl P 2 with (v , w) 21 (k) There is an edge (w, w’) E F  (F \ F) U H 2 and (v , w’) 2 e0  UP 0 F\(F J 2 .  where H 2 is the set of edges (w, x) in a square of the type in Figure 4.3 which are in P , 2 as  e2k  for some k < i (it may be in P 2 as +i). 21 e  , doesn’t contain a square for any i, in Lemma 4.4 2 In Lemma 4.3 we show that F e F we show that the end vertex  v,  in Lemma 4.5 we show that F  of P is deficient with respect to F and n is odd, and P doesn’t have any square. Thus P is an augmenting  walk, which contradicts the assumption we made at the beginning. I Lemma 4.2 Suppose that F is a square-free (0,2)-factor of G which is non-optimal and  0 is as defined in Theorem F  4. 1.  Proof. Assume that there is a vertex an edge (u, v) in F  . 0 \F  deg(v) for every vertex v of G.  Then deg (v) 0 v  such that deg 0 (v) <deg (v). Thus there exists  Two cases are considered depending on whether F 0 U {(u, v)}  has a square or not. Case 1 F 0U  {(u,v)}  doesn’t have a square:  Suppose that there is an edge (u,w) in F 0 Then def F’  def F 0 and  F’FI  <  \  F.  Let F’  =  IF’AFI  =  <  {(u,v)}  \  {(u,w)}.  IFoLFI, and we have a contradiction to the  choice of F . Suppose that there exists no edge (u, w) in F 0 0 Let F’  0 U F  \ F.  Then deg (u) < 2. 0  0 U {(u, v)}. Then F’ is a square-free (0,2)-factor, def F’ < def F F , and 0 . 0 IFoFI. This also contradicts the choice of F  Chapter 4. Square-Free Two-Factors  55  (a)  (b)  (C)  (d)  (e)  (f) w  (g)  (h)  (j)  (k)  (i)  -V  N4WW  6 Figure 4.4:  F-(F U 0 F) F-fl (might be in I) (FflI)(Ii— F)uH 2  Chapter 4. Square-Free Two-Factors  56  Case 2 F 0 U {(u, v)} has a square: A square in F 0 U {(u, v)} must contain edge (u, v) since F 0 is a square-free (0, 2)-factor. Claim 1 F 0 U {(u, v)} has exactly one square. Proof. Assume that there are two squares in F 0 U {(u, v)}. Let LJuvxy and Duvx’y’ be the two squares (Figure 4.5). Then the edges (v, x), (x, y), (y, u), (v, x’), (x’, y’), and . Since deg 0 0 (v) <2, x (y’, u) are in F  =  x’. Since deg 0 (x)  2, y  =  y’. This completes  ru  the proof of Claim 1.  Figure 4.5:  Let Ouvxy be the square in F 0 U {(u, v)}. At least one edge in Duvxy is not in F since F is square-free. Three cases are considered depending on which edge is not in F. Case A. (u,y) is not in F: Let F’  =  0 U {(u,v)} F  \  {(u,y)}. Then def F’  def F 0 and F’LFI < IFoAF, a  contradiction to the choice of F . 0 Case B. (v,x) is not in F: Since deg (v) < deg(v), there is an edge (v,w) in F 0  0 \F  where u  w. Assume that  0 U {(v, w)} has Jvwy’x’. Then we have the configuration shown in Figure 4.6. Since F (v) <2, x 0 deg u  x’. Since deg (x) 0  2, y  =  y’. Similarly u  =  w, a contradiction that  w. We can conclude that 0 F U {(v, w)} doesn’t have any square. By an argument  similar to that of Case 1, we can arrive at a contradiction to the choice of F . 0  Chapter 4. Square-Free Two-Factors  57  Figure 4.6: Case C. (x,y) is not in F: Without loss of generality, we can assume that both (v, x) and (u, y) are in F (otherwise we have Case A or B). Two subcases are considered. (a) degF(y) Let F’  =  =  1:  0 U {(u, v)} \ {(u, y) }. Then F’ is a square-free (0, 2)-factor and def F F 0  and IF’FI  FoFI. Since deg,(v)  =  (v). Since 0 deg degl  (t)  =  degI(y)  (y) 0 deg  —  (v) + 1 0 deg  =  1  =  1,  2, deg/(v)  =  degI(y) =  =  def F’  deg(v) >  =  deg(y) < deg (y). And 0  0 (t) for every vertex t( v, y). So deg  I{t e V : deg,(t)  <  deg(t)}  =  (t) 0 I{t e V : deg  <  deg(t)}  —  1  This contradicts the choice of F . 0 (b) deg(y)  =  2:  There exists an edge (y, z) in F Claim 2 F 0 U {(u, v), (y, z)}  . 0 \F  \ {(u, y)}  doesn’t contain any square.  Proof. Assume that it has one. Then either (u, v) or (y, z)  must  be in the square. By  Claim 1, (y, z) must be in the square (like in Figure 4.7). Either x’ If x’  =  =  x or x’  =  u, then Dyx’wz  of Claim 2.  u. If x’  is not in  =  x, then v  =  w and so it contradicts that deg 0 (v) <2.  0 U {(u, v), (y, z)} F  \ {(u, y)}.  This completes the proof  Chapter 4. Square-Free Two-Factors  58  Figure 4.7: Suppose that there is no edge (z, w) in F 0 \ F. Then deg 0 (z) <2, and F’ is a squarefree (0,2)-factor where F’ and  IF’AFI  <  <  0 U {(u, v), (y, z)} F  \ {(u, y)}.  Also def F’ <def F 0 <def F  . So there is an edge (z,w) 0 AFI, a contradiction to the choice of F 0 IF  in F \F. Let F’ 0  IF’FI  =  =  U{(u,v),(y,z)} \{(u,y),(z,w)}. Then defF’ 0 F  =  def F 0 and  . • 0 IFoFI, a contradiction to the choice of F  Lemma 4.3 Suppose that F is a square-free (0,2)-factor of G which is non-optimal and  P is as defined in Theorem .1 (p. 52). Then F Proof  2 doesn’t have any square. P  Assume that F e P 2 has Uvwxy. Two cases are considered depending on whether  or not there is an edge in LJvwxy which is in P twice. Case 1 There is no edge in flvwxy which is in P twice: Then we must have one of the following cases: (A) (v,w) E 2 flP and (w,x), (x,y) and (y,v) 0 F ,  . 2 e F\P  (B) (v,w) and (w,x)  flP and (x,y) and (y,v) e F\P 0 F , . 2 e2  (C) (v, w) and (x, y)  0 fl P , and (w, x) and (y, v) e F \ F 2 eF :. 2  Chapter 4. Square-Free Two-Factors  (D) (v, w), (w, x) and (x, y)  e  59  0 fl P F , and (y, v) E F 2  g. 2 \P  Case A. flvwxy is type (A): Then one of the forbidden configurations (a), (b) and (c) must exist. Case B. Dvwxy is type (B): Let  j  be such that e 21  =  (v, w) and k be such that  generality, we can assume that  j  e2k+1 =  (w, x). Without loss of  < k. Then one of the following three cases (Figure 4.8)  must occur, using the fact that F 0 has no square.  (i)  (iii)  (ii)  x  X  Figure 4.8:  (i) (x,y) and (y,v) F : 0  If  v2k =  x, then choosing (v2k, v2k+1)  (e). If V2k  =  w and  v2k+1 =  =  (x, w) violates the forbidden configuration  x, then we have to choose  V2k+2 =  y (otherwise we have  the forbidden configuration (d)). (ii) (x,y) E FflF 0 and If v 2  =  (y,v)  E F:  v, then choosing (v ,v 2 ) 1 + 2  (g). If v2j  =  w and v +i 2  =  e  0 and (x,y) FnF  It’s similar to (ii).  e  (v, w) violates the forbidden configuration  v, then we have to choose v j 2  the forbidden configuration (f)). (iii) (y,v)  =  F:  =  y (otherwise we have  Chapter 4. Square-Free Two-Factors  60  Case C. LJvwxy is type (C): Let  j be such that  (x,y) 22 v  e =  (v, w).  Without loss of generality, we can assume that  v. If (w,x)  Fo ((i) in Figure 4.9), then we have to choose  =  82j+1  23 23 and v P  =  x (otherwise we have the forbidden configuration (h)). If (w, x)  Figure 4.9), choosing (v ,) 2 21 v  e  0 fl F ((ii) in F  (v, w) violates the forbidden configuration (i).  =  (ii)  (i)  Figure 4.9: Case D. Dvwxy is type (D): Let  j be such that  23 If v2j P .  (k). If v2j  j+l 2 e  =  v, then choosing (v , v2f+1) 23  =  w and v 241  =  (v, w). Without loss of generality, we can assume that (x, y)  forbidden configuration  =  =  e  (v, w) violates the forbidden configuration  v, then we have to choose v j 2  =  y (otherwise we have the  (j)).  Case 2 There is an edge in LJvwxy which is in P twice: Without loss of generality, we can assume that (v, w) is such an edge.  Then (v, w)  belongs to a square of the type in Figure 4.3. Let rivwst be the square(Figure 4.10). Then (t, v) If for  =  V = V2k  v2k+2).  1 and (v, w) _ 2 e  and w  If w  =  = V2k  =  23 e  = e2k+1  for some  j and  k  (j  < k).  21 then s must be v v , 22 (we don’t have any other choice  and v  =  V2k+1,  then s must be  V2k_1.  So (s,w) must be in  P, and lvwxy cannot be Dvwst. Now we must have one of the following three cases  (Figure 4.11): (i) (w,s)  =  (w,x):  Chapter 4. Square-Free Two-Factors  61  Figure 4.10:  ()=  LI S  W  (ii)  (iii)  -----a Figure 4.11:  Chapter 4. Square-Free Two-Factors  Since y  t, (v, y) must be in F  62  . 0 \F  By a similar argument as above, (v, y) must  be in P. (ii) (v,t)  =  (v,y):  Since x  . 0 \F  s, (x, y) must be in F  Since t  =  23 and (x, y) v 3 v2j_2, x must be _  must be in P. (iii) (w,s)  (w,x) and (v,t)  (v,y):  The argument is similar to (i). The proof of Lemma 4.3 is completed. I Lemma 4.4 Suppose that F is a square-free (0,2)-factor of G which is non-optimal and P is as defined in Theorem 4.1 (p. 52). Then the end vertex v, of P is deficient with respect to F and n is odd. Proof. Assume not. Then either v is not deficient with respect to F or n is even. First suppose that n is odd, but v is not deficient with respect to F. If vertex v is not deficient with respect to F, then deg 0 (v)  =  deg(v)  =  2. The vertex  v  has an equal number  (zero, one, two) of incident edges of F 0 \ F and F \ F . Either edge (v_ 0 , v) is in F 1 0\F or (v_ , v) is in F 1 0 fl F and used for the second time (Figure 4.3). If (v_ , v) is in 1 0 \F, it is clear that there is an edge e F  e  F\ (F 0 UP) which is incident to  is in F 0 fl F and used for the second time, then it is used as next edge e2k+1 is in F 0 incident to  v.  \ F.  e2k  v.  If (v_ , v) 1  for the first time and the  In this case also, there is an edge e  e  F  0 U P) \ (F  which is  So in both cases we arrive at a contradiction to the maximality of P.  Now suppose that n is even, i.e. n (i) there is no edge e E (F 0 (ii) each choice of  =  2i for some i. Then either  \ (F U P)) U  , ) 2 (v 21 v  which is incident to  v,  or  yields one of the forbidden configurations in Figure 4.4  Chapter 4. Square-Free Two-Factors  63  2 once as where H 1 is a set of edges in H 2 which is in P Since deg (vfl) 0 v  of  , 2 (v  v.  but not as  deg(v) by Lemma 4.2, the number of edges in F 0  is greater than that in F  is incident to  e2k,  . 0 \F  So there exists an edge  e  0 E (F  i+i. 2 e  \ F incident to  \ (F U F)) U H  which  Case (i) cannot occur, so it must be case (ii). That is, for each choice  i+ 2 v ) 1 , one of the following situations occurs:  (A) Some edge (w, w’) violates (b), (e), (g), (i) or (k). (B) Some edges (w, w’) and (y, y’) force two different choices by (a), (c), (d), (f), (h) or  22 = v  w and  22 = v  (j).  Claim 1 There is at least one choice of (v ,v 2 +i) which doesn’t lead to situation (A). 2 Proof. Suppose that for a choice We will show that 21 v ,) 1 _ 2 (v  ,v 1 _ (v ) 2  + = v, 2 v  is in F  \  there is an edge (w, w’) which violates (b).  . Assume that 0 F  F  2,  . 0 \F  1 = v. _ 2 v  Since  1 _ 2 v  v’( v)  be a choice of  with  21 v .  , v’) 2 (v  e  0 F  =  cannot be a choice of  Since there are two edges (w’, v ) and 2  is a vertex  F  is in a square of the type in Figure 4.3 and is in F fl F . Let 0  be the square (Figure 4.12 (i)). Since deg(v2) < 2, x w 0 deg  ,v 1 _ (v ) 2  \ F.  ,v 1 _ 2 (v ) 2  The edge  21 2 v , _i,v (v )  in F  , v’) 2 (v  Now we will show that the choice  w’. Similarly y  0 \F  \  . Then 0 F  v 1 _ 2 Dxyv  Since  = w.  must be in  incident to  there  , 2 v  must not be in F, so  1 = v’ j 2 V  can  doesn’t lead to (A).  Assume that it does. Let (y, y’) be the edge which violates (b), (e), (g), (i), or (k) by the choice  21 = v’ v  (Figure 4.12 (ii)). Then  one edge in F \ F is incident to Since (w, w’), (y, y’) and y’yv’ 2 Dv  be in F  , y’ = 2 v  , w’) 2 (v  , 2 (v  y’) must be in F  \  0 U F). Since only (F  w’. In all of the cases, (y, y’) must be in F  are in F  P and incident to  w’(= y’), y = w.  must be in case (b), (e) or (g). In case (b) or (e), (y, y’), (y, v’) and F and incident to  are in F , so 0  v = v’.  w(=  y), and so  v = v’.  (w, v)  In case (g), (y, y’), (y, v’) and  In all of the cases, we arrive at a contradiction that  v  v’.  F. Thus must  (w, v)  Chapter 4. Square-Free Two-Factors  64  (i)  (ii)  Figure 4.12: By a similar argument, we can show that if for some choice of (v ,v 2 ) there is an 1 + 2 edge (w, w’) which violates (e), (g), (i) or (k), then there is another choice of (v ,v 2 ) 1 + 2 which doesn’t lead to (A). This completes the proof of Claim 1. Let v be a vertex which can be a choice of . 21 By Claim 1, we can assume that the v choice v 21  =  v doesn’t lead to (A).  Claim 2 If for the choice v 21  =  v there is some edge (w, w’) which forces v + 2  =  w  by (c) or (d), then situation (B) doesn’t occur (that is, no other vertex is required to be ). + 2 v Proof. Suppose that w is required to be v + by (c). Assume that there is another vertex 2 22 (Figure 4.13). Since (v ,v 1 _ 2 ) 2 y required to be v edges in (F  \ F) U Fo  incident to v . So w’ 2  and a contradiction to the assumption that w  , w’) and (v 2 , v) are only 2 e F, (v  y’. Since (y, y’) must be in F $ F, w  =  y  y.  When w is required to be v 22 by (d), we can show that there is no other vertex required to be v 22 by a similar argument. This completes the proof of Claim 2. Claim 3 If the choice v 21  =  leads to neither (A) nor (B).  v leads to (B), then there is another choice of v 21 which  Chapter 4. Square-Free Two-Factors  65  P  Figure 4.13: Proof. Without loss of generality, we can assume that neither (w, w’) nor (y, y’) forces =  w and v 22  =  y by (c) or (d). Here we will consider only the case that w is  required to be v 22 by (a). By a similar argument, the other cases can be verified. Two cases can be considered depending on whether (v , w’) 2  e  0 or not. F  Casel. (v ,w’)EFflFo: 2 This configuration is shown in Figure 4.14. Since (v , w’) and (v 2 , v) are the only edges 2 in (F  \ F) U Fo  incident to v , 2  =  y’. Since (y, y’) must be in F  e F,  w  =  y.  Figure 4.14: Case 2. (v , w’) 2  If w’  =  e  F  : 0 \F  y’, then we arrives the same conclusion as in Case 1. Suppose that w’  , y’) must be in F 2 (v 0  (f). Then 21 (v y’) ,  g  \ F.  So  y’y 2 Dvv  must be in case (f) or  P (since (v ,) 1 _ 2 21 E F and (v v , w’) 2  that we can choose v 21  =  1 j 2 y’, i.e. the choice v  Assume that we cannot choose v ÷ 2  =  =  y’. Then  (j). Suppose that it’s case F  \ P).  Now we will show  y’ leads to neither (A) nor (B).  u’uy’ be any square in cases (a)’(k) 2 y’. Let Dv  Chapter 4. Square-Free Two-Factors  (Figure 4.15). Since (v _i, v 2 ) 2 in (F  \ F) U Fo  e  66  F fl F, (u , v), (v 2 , w’) and 2 2 (v y’) are the only edges ,  incident to . 21 So u’ is either v or w’. v  Figure 4.15:  (i) u’  =  v ((i) in Figure 4.16):  Since (u, u’) is in F  F, u is either w or y. If ‘u is w, then the choice v 21  doesn’t lead to any square in cases (a)(k). Similarly for the case that u (ii) u’  =  =  =  y.  w’ ((ii) in Figure 4.16):  Since (u, u’) is in F  P, a  =  w. If (u, y’) E F \ F, then y’  Suppose that (u, y’) E F . Then u 0 incident to y’). So w yy’ is in case 2 If Ovv  =  =  =  v and a contradiction.  , y’) and (y, y’) are in F 2 0 and y (since (v  y and we arrive another contradiction.  (j), we will arrive the same conclusion.  This completes the proof of  Claim 3. The proof of Lemma 4.4 is completed. I Lemma 4.5 Suppose that F is a square-free (0, 2)-factor of G which is non-optimal and F is as defined in Theorem 4.1 (p. 52). Then F  P doesn’t contain a square.  Proof It can be proven by a similar argument as in Lemma 4.3. I  Chapter 4. Square-Free Two-Factors  (i)  67  (ii)  u,=  Figure 4.16: 4.3  A Preview of the Blossom Algorithm  Our Blossom Algorithm either finds a square-free two-factor of a given graph G or proves that there is none. In this section and subsequent sections we impose the restriction that the squares of G are vertex disjoint. In this section, we will give a rough outline of the algorithm and discuss the difference between the algorithm and other blossom algorithms [16]. The closest analog is the algorithm of D. Hartvigsen for triangle-free two-factors [31]. Let us first outline the algorithm. We start with any square-free (0, 2)-factor F (Step 0).  Look for an augmenting walk as described in Section 4.2 by tree-growing  (Steps 1 ‘.‘5). We let all deficient vertices be roots and simultaneously grow a tree from each root. They form a forest F. Later we find that it’s different from a forest in other blossom algorithms. In others, trees are vertex-disjoint, but not in ours. We abuse the notation slightly and still call it a forest. If we find an augmenting walk F, then we augment F by alternately adding and subtracting edges along P to F (Step 6). If new F is a square-free two-factor, then stop. Otherwise look for another augmenting walk. This is the same as other algorithms. The difference between our Blossom Algorithm  Chapter 4. Square-Free Two-Factors  68  and others arises in the procedure of finding an augmenting walk, i.e. tree-growing. Our Blossom Algorithm is more complicated than other blossom algorithms. An edge can be used twice and there are four possible labels for a vertex, more labels than in other blossom algorithms. We say that an edge e is matched (resp. unmatched) if e  e F (resp.  eF). Let all deficient vertices be roots and grow a directed tree from each root simultane ously. Start with F  =  {all deficient vertices} and add vertices and edges to F as trees  grow. When a vertex v is added to F, v is given one of the following labels: dummy odd, odd, or even. A vertex v is even if v is added to F with a matched edge. A vertex v is odd if v is added to F with an unmatched edge and either matched edge incident to v can be added to F. A vertex v is dummy odd if v is added to F with an unmatched edge and only one matched edge incident to v can be added to F. If a vertex v is even (resp. dummy odd or odd), then there is an alternating walk in G of even length (resp. odd length) from a deficient vertex to v. All deficient vertices are set to be even at the beginning of the algorithm. A set of some vertices in G is shrunk into one vertex in F, called a pseudovertex. A vertex v in F is either a real vertex or a pseudovertex; if v is a real vertex, then v is dummy odd, odd, or even. Define P, to be the directed path in F from a root to v. During the algorithm, we deal with the current shrunk graph which is obtained from G by shrinking all current pseudovertices. Now we explore the algorithm in more detail. Look for an unmatched edge  (  F)  from an even vertex or a pseudovertex v to a non-odd vertex w (Step 2). If there is no such edge, then stop and there is no square-free two-factor. Of course we must prove this. It is done in Section 4.9. Suppose that there is such an edge. If w  F, let w be odd or  dummy odd depending on whether or not there is a square of G where all its unmatched edges belong to F,, U {(v, w)} but not any of its matched edges. Note that we check this  Chapter 4. Square-Free Two-Factors  69  in the current shrunk graph, not in G. We don’t need to concern ourselves with the edges inside a pseudovertex. This is the power of the blossom approach. If there is no such square of G for P, U {(v, w)} in the shrunk graph, then using the Recover Algorithm we can recover an alternating walk P in G from a deficient vertex to w ending with the edge (v, w) such that P  eF  doesn’t have a square. To recover an alternating walk in G, we  will follow the usual procedure in blossom algorithms with some significant differences. When a square is formed by the walk, we will modify the walk to avoid the square (see Figure 4.45i-.s4.50). If there is no such square, let w be odd and vertices which are joined to w by a matched edge be even. If there is such a square (like Figure 4.17), let w be dummy odd and only the vertex which is joined to w by the matched edge in the square be even (in Figure 4.17 only u is even, not u’).  (i)  (ii)  a pseudovertex Figure 4.17: If w is already dummy odd, let w be odd ((i) on p. 74 explains why w can be odd). Now consider the case that w is even or is a pseudovertex. If v and w are from different trees, i.e. the edge (v, w) joins two trees, we can find an augmenting walk (there are some exceptions where we cannot have an augmenting walk and they are described in Step 4.5). If v and w are in the same tree, then adding the edge (v, w) to .T forms a cycle in F and we shrink the set of vertices in the cycle into one vertex, i.e. a pseudovertex,  Chapter 4. Square-Free Two-Factors  70  (there are some exceptions where the set of vertices cannot be shrunk and they are  in  described in Step 4.5). Some vertices in the cycle might be pseudovertices. There may be some special vertices in a pseudovertex as follows: If there is a square of G where all its unmatched edges belong to P but not any of its matched edges where P is the directed path in F from a root to v ending with an unmatched edge, then call such a vertex v a dummy vertex. After forming a pseudovertex, let an end vertex of a matched edge, which is incident to any nondummy vertex in the pseudovertex, be even (Step 5e). If any matched edge joins any nondummy vertex in the pseudovertex to an odd vertex or a nondummy vertex in a pseudovertex, form another pseudovertex containing the pseudovertex (Step 5e). Figure 4.18 is one example of forests generated by our algorithm. The following two examples show why our Blossom Algorithm is so complicated. In Figure 4.19, we start growing a tree from vertex r. If the vertices v and w are even with predecessors u and t respectively, then we cannot form a pseudovertex using the edge e. This is one of the cases in which a pseudovertex cannot be formed using an edge joining two vertices which are even or pseudovertices. Later a pseudovertex o is formed using one of the edges e (i  =  1, 2, 3) and contains all of the vertices inside the marked  circle. Now we can breakthrough along the edge  f  and find an augmenting walk (from  the Recover Algorithm). Note that we have to use the edge e’ twice to breakthrough along  f.  Moreover any augmenting walk must use the edge e’ twice. This indicates why  any algorithm for the problem must handle this possibility. In Figure 4.20, we start growing a tree from vertex r. First the pseudovertex which is marked by the smaller circle is formed. The vertex v is dummy. (Let P be the path starting from r to v through vi’s. The reader can see that F the edge  f  P contains Dv vv.) So 3 v 2  cannot be added to F. Later another pseudovertex, which is marked by the  bigger circle, is formed containing the previous pseudovertex and v becomes no longer  Chapter 4. Square-Free Two-Factors  71  o • root  root  : even  :dummy odd • dummy in • apseudoveex a pseudovertex  Figure 4.18: A forest .T  Chapter 4. Square-Free Two-Factors  Figure 4.19:  72  Chapter 4. Square-Free Two-Factors  73  S  •0  Figure 4.20:  Chapter 4. Square-Free Two-Factors  74  dummy. This yields a breakthrough along the edge  f  and the augmenting walk shown.  Although a different order for tree growing may find the augmenting walk without using blossoms, it seems unlikely that you could specify that order in the algorithm. We hope these two examples help to explain the complexity of our algorithm. We believe the complexity is a unavoidable outcome of the blossom approach. Above, we have given a rough description of our Blossom Algorithm and examples showing why the algorithm is so complicated. Note that if G has no square, then our algorithm is the standard blossom algorithm. Now we will describe the difference between our Blossom Algorithm and others and some terminology which may help a reader to understand the algorithm in the next section. (i) A dummy odd vertex v may be later reached by another edge in a tree-growing. If it is a matched edge, then v becomes even. If it is an unmatched edge, then there is no square of G containing the edge since we deal here with a graph whose squares are vertex-disjoint. So v becomes odd and the vertex (u’ in Figure 4.17) prevented from being even now becomes even. (ii) A dummy vertex v in a pseudovertex may be reached by an unmatched edge later in a tree-growing. We form a pseudovertex containing the pseudovertex which contains v, and v is no longer dummy. In some other cases, v becomes no longer dummy. They are described in Step 5 and see Theorem 4.6. (iii) An edge e can be used twice in  if e belongs to a square of the type in Figure 4.21.  Once e is added to .F, we store it in set E* for the second use. First e is used to give x an even label with P = even with P, =  v, w, x). Second for either y or x’. If w becomes even, then y is w, v, y). If y becomes odd, then x’ is even with P’ = (Pa, v, w, x’).  Later when we recover an augmenting walk P in G, e might appear twice in P. By a small change in F, we can avoid using e twice in P (the details are in Step 4 of the Recover Algorithm).  Chapter 4. Square-Free Two-Factors  75  Figure 4.21 (iv) Trees in .T are stored using the notation p(v)  =  w to denote that w is a predecessor  of v in a tree. A vertex v may have two predecessors. In this case, either one is chosen to be p(v). Suppose that v has two predecessors w and w’ and w is chosen to be p(v). If vertex x has v as its predecessor and w is not in P, i.e. w’ is in P, then P is recorded instead of p(x)  =  =  (P’,v,x)  v. For example, suppose that in Figure 4.22 first v becomes  dummy odd (v has predecessor w’) and x becomes even, and later v becomes odd (w is another predecessor of v) and x’ becomes even. Then we store them in the following way: p(v)  =  w, p(x’)  =  v, and P  =  (P,v,x).  Figure 4.22: For a vertex v, P, can be defined as given (such as P,  =  =  (P(), v) in a recursive way, if no remark is  (Pa, x, v)). In the algorithm, we use the notation root(v) to denote  the root of the tree in which v lies.  Chapter 4. Square-Free Two-Factors  76  Here we want to make a short note about choosing one predecessor as p(v) when v has two predecessors. Suppose that v has two predecessors w and w’. Then v is in a square of G (see Steps 4.1 and 4.3) and one predecessor is in P for only one successor x of v which is in the square. Say that w’ has this property. Then w is chosen to be p(v). (v) If a vertex v is added to F as a dummy odd for the first time and later it becomes odd or even, then v has two predecessors in F. These two predecessors might be from different trees. In F trees are not vertex-disjoint ((i) in Figure 4.23). In (iii), it was noted that some edge can be used twice in F. An edge might be in two different trees, so in F trees are not edge-disjoint either. If two predecessors of a vertex are in the same tree or an edge is used twice in the same tree, the tree doesn’t fit the usual concept of a tree. But we call still it a tree. If we split a vertex which has two predecessors or an edge used twice in F into two, then F has a usual forest structure, i.e. trees are vertex-disjoint and edge-disjoint and each tree fits the usual definition of a tree ((ii) in Figure 4.23). We don’t split vertices or edges explicitly in the algorithm (there are some complications for edges which are not in F, and this makes this approach unworkable). (vi) Earlier this section, it was stated that if there is any unmatched edge e joining two vertices v and w which are even or a pseudovertex and both are in the same tree, then adding (v, w) to F forms a cycle in F. In fact, it may not be a cycle. In Figure 4.24, vertex x or the edge (x, y) is in P, as well as Pu,. If we split vertex x or the edge (x, y) into two, then by some extension it can be considered as a cycle. In the algorithm, the base b of a pseudovertex is defined as the first vertex such that (b,p(b)) and (p(b),p (b)) are common edges on P, and P from v (resp. w) to its root. 2 In a usual blossom algorithm, the base b is defined as the first common vertex on the paths P, and  We say that edge (p(b), b) is the stem of a pseudovertex.  (vii) Suppose that a vertex v is added to F twice. Then there are two directed paths P and P’ in F from roots to v (Figure 4.25 (i)). If some part of P including v is shrunk  Chapter 4. Square-Free Two-Factors  77  (ii)  (i)  b  root  root  root  Figure 4.23:  (ii)  (iii) I  (  p / %  I  Figure 4.24:  Chapter 4. Square-Free Two-Factors  78  into a pseudovertex o, then in P the portion which is in o is replaced by o. But keep F’ as it is now; that is don’t replace v by o in F’. Later some part of P’ including v may be shrunk into a pseudovertex, like Figure 4.25 (ii). Two pseudovertices are said to be attached to each other at vertex v. If two pseudovertices are attached to each other, form another pseudovertex including the two pseudovertices.  (ii)  (I)  S -  -  I  I  /  I  I F /  / —  S.  root  a  I!  0  root  root  O root  Figure 4.25: (viii) Suppose that an edge e is used twice in F. Then there are two directed paths P and F’ from roots to the end vertices of e (Figure 4.26). If some part of P including e is shrunk into a pseudovertex o, then in P the portion which is in o is replaced by o. But keep F’ as it is now. This is similar to (vii). Later some part of F’ including e may be shrunk into a pseudovertex, asin Figure 4.27. Then the matched edge  f joins two  pseudovertices, so another pseudovertex containing  Chapter 4. Square-Free Two-Factors  (i)  79  (ii)  4’  ‘  root  a  root  root  -P  root Figure 4.26:  j  tpns a o X1A UpJOp  W0Ij  ‘qdii junnjs  ijt ou  ooi usop ‘j jj °xaoAoptIosd j  ‘ainbs  i  prs  aLvnbs v svai  spa ppwun s! jp aiaq  jp o  T ci  ‘ll  psut opo  u.io  St t uq ‘sp  Ut3U1J U’L St )J)I{ U)1{J  ue  aq UUfl  ppw  ptp o pou uop  12 ‘ ’J  U0tWOU Ot{ OSfl OM OS SflJ Ut  P-T  “!°“-‘°S JfRO fltM  M  W 05 o  ut  o uopq  tjed popatp  pa UO UeTf JOffl U0tOU T{ OSU  ‘J  2utsn  poipe  uuoj  e st j j (x)  ia  ou st  uq ‘x x1AopnSd  x x1Aopnsd  St  ‘i Vt AeM  Ue UtSfl OU  iO  jouop  xaoAopnsd e  °M fip 9yvf  X pue 0 sM1aAopUaSd o oj uiutoC op  X pue 0 UIUTThUO xaaaopnsd ioue s) 0 O  ‘jdurex  M  pou s  s jo Au ou nq  jo 91nbs u st aiai pue  uiq O  111103 OM  iiUtIteUIt U TpflS  aETf ‘se StT{ UI  31 (g dj  pp o ‘punoj S 0 xioAopnosd ioje paepues  Ut ou xoJoAopnosd e 111103 o ‘uiijuOe oq untp sm  :IJ  SUOtIUA y (xt)  t!T 100.1  100.1  I  I  S  —  I  paULIOj Ie S  08  1 sJoPeci-0MJ  tJaAopnsd o aqj  arci-arvnbS  i  81  Chapter 4. Square-Free Two-Factors  doesn’t have a square. At various times in the algorithm we call some square a blocking square if some P, creates a square, i.e. the augmentation along path P,, is blocked by the square. Note that for an even vertex v, P doesn’t create a square. (xi) Some edges are currently useless, that is they do not assist us in our tree growing at this time. But it may become useful later. For example in Figure 4.28, the edge (v,w) is useless since adding (v, w) to F gives only x an even label but x is already even with p(x)  =  y. Later it becomes useful if a pseudovertex containing the edge (y, v) is formed.  (ii)  (i)  /  Figure 4.28: If we pick up an edge which is currently useless, store the edge in the set CUE(currently useless edges) to prevent picking it up repeatedly in Step 2. Whenever any change is made in F, empty the set CUE and edges in this set become available again.  4.4  The Blossom Algorithm  In this section, we will present our Blossom Algorithm. We wish to remind the reader that set E* consists of edges which can be used twice ((iii) on p. 74) and set CUE consists of currently useless edges ((xi) on p. 81).  Chapter 4. Square-Free Two-Factors  82  Blossom Algorithm Step 0. (Initialization of F) Let F be any square-free (0, 2)-factor of G. For example, we could take F  =  Step 1. (Initialization) If there is no deficient vertex, then we have a square-free two-factor and STOP. Otherwise, let E  =  E  \ F,  E  F, E*  =  =  ,  and CUE  =  q!. Let all deficient vertices be even.  They will be roots of F. Step 2. (Select an unmatched edge to change F) Search for the following type of edges  ( CUE) from an even vertex or a pseudovertex v  to a non-odd vertex w: e  =  e  =  (v,w)  e  E+,  (v, w)  e  E*  where w is even.  If there is no such edge e, then there is no square-free two-factor (this is shown in Theorem 4.11) and go to Step 7. If e is in E, go to Step 3. If e is in E*, go to Step 4.6.  Step 3. When e E E, w must be one of the following: (i)  F  (ii) dummy odd  (iii) even  (iv) a pseudovertex. If w  F, go to Step 3.1. If w is dummy odd, go to Step 4.3. If w is even or a  pseudovertex, go to Step 3.2. Step 3.1 (w  F)  Check whether a square S of G exists where all its unmatched edges belong to P U {e} but not any of its matched edges. If such a S exists, go to Step 4.2. Otherwise go to  Chapter 4. Square-Free Two-Factors  83  Step 4.1. Step 3.2 (w is even or a pseudovertex) Check whether a square S of G exists where all its unmatched edges belong to P, U {e} (resp. P, U {e, (w,p(w))}, P U {e}, or P, U {e, (v,p(v))}) but not any of its matched edges. If no such a S exists, go to Step 4.4. Otherwise, i.e. the augmentation along P U {e} (resp. P U {e, (w,p(w))}, P U {e}, or P U {e, (v,p(v))}) is blocked, check whether (w,p(w)) (resp. (p(w),p (w)), (v,p(v)), or (p(v),p 2 (v))) is a matched edge and 2 belongs to S. If so, go to Step 4.4. Otherwise go to Step 4.5. Step  4. (Tree Growing)  Various cases are chosen in Step 2 or 3. Step 4.1 (w  .F and there is no square.)  Let w be odd, E  =  E  —  {(v,w)} and p(w)  v. Let u 1 and 2 u be the ends of two  matched edges incident with w (ui and u 2 must not be odd). For i even nor a pseudovertex, then let it be even, p(u)  =  w, and E  =  1,2, if u, is neither  =  —  {(w, u)}.  If w belongs to a blocking square wuxz (see Figure 4.29) such that: (i) Dw’uxz contains three matched edges (w, u), (w, z), and (x, z) and one unmatched edge (u,x), (ii) (u,x)  e  E*, and  (iii) xis dummy odd with P then let x be odd with P Let E  =  E  —  =  =  (Pq,’u,x),  (Pr, w, ‘U, x), and no longer call Dwuxz a blocking square.  {(w, u)} and E*  =  —  {(u, x)}.  Note that y is neither odd nor  nondummy in a pseudovertex. If y is neither even nor dummy in a pseudovertex (i.e. y is  F or dummy odd), then let y be even, p(y)  =  x and E  =  E  —  {(x, y)}.  Chapter 4. Square-Free Two-Factors  84  Figure 4.29: Reset CUE Step  =  and go to Step 2.  4. (w g F and there is a square S.)  The square S is one of the following (Figure 4.30):  (i)  (ii)  (iii)  Figure 4.30: In case (i), if’u is even, then the predecessor of u is x. Let w be odd, P =  E  —  {(x,v)}, and E  =  E  —  =  {(v,w)}. If u’, which is the end vertex of the  other matched edge incident with w, is not even, then let u’ be even, p(u’) E  =  E  —  {(w,u’)}. Reset CUE  =  =  E  —  =  w, and  =  v, and  and go to Step 2.  In cases (i) and (ii), if u is not even, then let w be dummy odd, p(w) E  (P,v,w),  {(v,w)}. Let u be even, P  =  (P,w,’u), and E  =  E  —  {(w,u)}. Call  Chapter 4. Square-Free Two-Factors  Dvwux a blocking square. Additionally in case (i), let E* = E* U {(v, w)}. CUE =  85  Reset  and go to Step 2.  In case (iii) and the case that in (ii) u is even, let CUE = CUEu {(v,w)} and go to Step 2. Step 4.3 (w is dummy odd) Let u and u’ be the end vertices of matched edges incident with w. Suppose that (w, u) is in a blocking square. Since w was dummy odd, e is not in a square. Reset w to be odd, p(w) = v, and E+ = E+ and E Step  = E  —  —  {(v, w)}. If u’ is not even, then let u’ be even, p(u’) =  {(u’,w)}. Reset CUE = q and go to Step 2.  4.4 (w is even or a pseudovertex, and there is no square.)  Consider P to be edge e. Go to one of the following two cases depending on whether or not root(v) = root(w). Case 1. root(v)  root(w)  Check whether a square S of G exists where all its unmatched edges belong to P, U {e, (w,p(w)),. , 1 (p’ ( w),p’(w))} but not any of its matched edges (root(w) = p(w)). If no such a S exists, go to Step 6. Otherwise, it must be the case in Figure 4.31. Reset P = (P,, y, q, z). Let b = y and go to Step 5 (there is a square of type (ii) in Figure 4.36). Case 2. root(v) = root(w) Let b be the first vertex such that (b, p(b)) and (p (b) , p 2 (b)) are common edges on the paths P, and P from v (resp. w) to its root. If there is no such b, let b = root(v) = root(w). (a) Suppose that b = root(v) = root(w) (b = p(v)) and b is a real vertex incident with no matched edge. Check whether a square S of G exists where all its unmatched edges belong to P, U {e, (w,p(w)),... , 1 (p’ ( w),p’(w))} but not any of its matched edges. If  Chapter 4. Square-Free Two-Factors  86  I  (x,y) €F (z,q)eF, I I  I I  66 root (w)  root (v)  Figure 4.31: such a S exists, go to Step 5 (there is a square of type (iv) or (viii) in Figure 4.36). Otherwise go to Step 6. (b) Suppose that b  =  root(v)  =  root(w), b belongs to a blocking square of the type in  Figure 4.32 where another vertex y is deficient and P,, paths P, or P, yet not both of them. Reset P  =  =  (b, x, y, z) is part of one of the  (y,x,b,z). So root(v)  root(w). Go  to Case 1.  Figure 432: (c) Suppose that root(v)  =  root(w) and the assumptions of cases (a) and (b) do not hold.  Chapter 4. Square-Free Two-Factors  87  Then go to Step 5. Step 4.5 (w is even or a pseudovertex, and there is a square S.) The square S must be one of the cases in Figure 4.33. In cases (i) and (ii), let P, = (y,w,v) and let b = y. Go to Step 5. In case (iii), if both x and y are even or pseudovertices, then it is one of the cases in Figure 4.34. Let CUE = CUE U {(v, w)} and go to Step 2. If only one of x or y is even and the other is its predecessor (say x is even and p(x) = y), then go to Step 4.4 with = (v, w, y). Now suppose that the two assumptions above do not hold. If x is not even, then let x be even, P = (P,v,x), E+ = E+  —  {(v,w)}, and E = E  —  {(x,v)}.  If y is not even, then let y be even and do similar as when x is even. Call Dyxvw a blocking square, reset CUE =  çi  and go to Step 2.  In case (iv), go to Step 5. In case (v), if x is odd, then go to Step 4.4 with P = (v,w,x). If x is not in .F, then let x be even, P = (P,w,x), E = E Uvwxy a blocking square. Reset CUE =  —  {(v,w)}, and E = E—  —  {(x,v)}. Call  and go to Step 2. Otherwise, i.e. x is even  or a pseudovertex, let CUE = CUE U {(v, w)} and go to Step 2. In cases (vi) and (vii), let CUE = CUE U {(v, w)} and go to Step 2. Step 4.6 (e  e E* and w is even)  Let Dyxvw be a square containing v and w (Figure 4.35). Then either x or y is even. Without loss of generality, we can assume that x is even and P = (Pm, v, x). If y is even or a pseudovertex, then let E* = E*  —  {(v, w)} and go to Step 2. If y is odd, then  go to Step 4.4 with P = (v, w, y). Now suppose that y is not in F. Let y be even, = (P,w,y), E* = E* to Step 2.  —  {(v,w)} and E  = E-  —  {(w,y)}. Reset CUE = qS and go  Chapter 4. Square-Free Two-Factors  88  (ii)  (i)  (iii) —  /  /  ‘I  I  I  J I  o  o  I  (x,y) F  / I  p(v)x p(w)y  (x,y)F  (vi)  (v)  _  S  ,  ‘  ,  .5.  ——  p(y)x p(w)x (v,y)€ II:? (vi)  p(y)4x  p(w)*x  (vii) I  S  I  —  (v,w) is any unmatched edge Figure 4.33:  Chapter 4. Square-Free Two-Factors  89  (1)  rJY p(y)=v p(x)=w Figure 4.34:  U Figure 4.35:  p(y)=v p(x)=y  Chapter 4. Square-Free Two-Factors  90  Step 5. (Shrinking) We divide this Step into 5 small steps for convenience’s sake. Step 5a. (Check whether there is a blocking square) Let m, n be such that pm(v)  =  p”(w)  =  b. For k  =  0, 1,. , n, check whether a square S of  G exists where all its unmatched edges belong to P, U {e, (w, p(w)),... but not any of its matched edges 1 (p (w)  =  ,  (pk_l  (w) ,k (w)) }  v). Interchange the roles of v and w, and do  it again. If any square is found, then it is one of the squares xyzq shown in Figure 4.36.  (I)  S S  (ii)  — — — —. —  I I I I  I  S I  91  Chapter 4. Square-Free Two-Factors  (iv)  (iii) I  ,  I  S  I  S  I  S  I  S  I I  S S S  I I  I  I  I  I I  I  I  I  S  S  (v)  (vi)  (viii)  (ix)  Figure 4.36:  (vii)  S  Chapter 4. Square-Free Two-Factors  92  Step 5b. (Let some of the squares found in Step 5a be blocking squares and turn some of them into squares which are not blocking) In case (v), if x is not a pseudovertex, then let CUE  CUE U {(v, w)} (one of (x, y),  =  (y, z) or (z, q) is (v, w)) and go to Step 2. If x is a pseudovertex, continue this step (all of x, y, z and q will be shrunk to one vertex). In case (vi), if E:Jxyzq is a blocking square, no longer call it a blocking square. Suppose that y is even and p(y) {(v, p(z)  z.  Then (v,w) is either (q,x) or (x,y). Let CUE  w)} and go to Step 2. Suppose that y is even and p(y) =  CUE p(z)  =  y. Reset p(z)  =  =  q, E  E U {(y,z)}  =  \ {(z,q)},  CUE U  Then (v, w) is (z, q) and  and E  =  E U {(x,y)}. Let  q and go to Step 2. Suppose that y is dummy odd. Then (v,w) is (z,q) and  y. Reset p(z)  and p(y)  =  z.  =  =  =  q, E  z. Reset CUE  =  E  \ {(z,q)},  and E  =  E U {(x,y)}. Let y be even  and go to Step 2. If y is odd or a pseudovertex, then  continue this step (all of x, y, z and q will be shrunk into one vertex). In case (vii), if flxyzq is a blocking square, no longer call it a blocking square. Suppose that x is even and p(x)  =  y. Then (v,w) is (q,x). Let CUE  to Step 2. Suppose that x is even and p(x) p(z)  =  q and p(y)  Reset CUE  =  =  z  if not. Let E  =  CUE U {(v,w)} and go  y. Then (v, w) is either (y, z) or (z, q). Let  E U {(x, y)}\{(v, w)} and E  =  E U {(q, x)}.  çb and go to Step 2. Suppose that x is dummy odd. Then (v, w) is  either (y, z) or (z, q). Let p(z) E  =  =  =  q and p(y)  E U {(q, x)}. Let x be even and p(z)  =  =  z  if not. Let E  y. Reset CUE  =  =  E  \  {(v, w)}  and  and go to Step 2. If y  is odd or a pseudovertex, then continue this step (all of x, y, z and q will be shrunk into one vertex). If a square of type (viii) is present, then choose one appearing for the smallest k, and reset P,  =  (Pq, x, y). Go to the beginning of Step 5 with b  In cases (i)  =  q.  (iv), if x is not a pseudovertex, then let x be dummy, z the mate of x,  and Llxyzq a blocking square. If there exists a blocking square of type (i) or (iii) where  Chapter 4. Square-Free Two-Factors  93  (q, x) and (x, y) belong to either P or P, then let x be dummy and z the mate of x. Here P and P are the portions of P, and Pt,., from b to In cases (ix) and (x), x is not dummy and  v  and from b to  w,  respectively.  is not a blocking square. We can  Dxyzq  reach x through (Ps, q, x) in (vii) (resp. (Pr, z, q, x) in (viii)). If there exists a blocking square of type (vii) and (viii), then no longer is it a blocking square and x dummy. If x is deficient, go to Step 6. Step  5c. (Store a new pseudovertex o)  Let 0 be the set consisting of vertices which are real or inside a pseudovertex on the path P or P. Shrink all the vertices of 0 to a pseudovertex  o.  Let b be the base of o.  Store the structure of 0 in Q(0) (for an augmentation). If b is a deficient vertex, then let o be a root. Otherwise, let P 0  =  F,, and reset CUE  =  Step 5d. (Some dummy vertices become nondummy) If the ends of both matched edges incident with a dummy vertex x in 0 (x can be a vertex in a pseudovertex in 0) belongs to 0, then both ends are even. No longer call x a dummy vertex and the square containing x a blocking square. If there exists an edge (t, x)  E  E+ from a vertex t in 0 to a dummy vertex x in 0 (x  can be a vertex in a pseudovertex in 0) and (t, x)  .F, then we can reach x by (Pt, x).  No longer call x a dummy vertex and the square containing x a blocking square. If x is deficient, go to Step 6. If any edge in  P or P, i.e.  (pc_l(v),pc(v))  or  (pv_l(w),p(w)),  is incident to a  dummy vertex x or its mate in another pseudovertex(it can be a pseudovertex in 0), then no longer call x a dummy vertex and the square containing x a blocking square. It’s shown in Theorem 4.6 why x is not longer dummy. If x is deficient, go to Step 6. If the edge (x,  z)  in squares in Figure 4.37 is on P or Ps,, no longer call  blocking square. If q is dummy odd, let q be odd and E  =  E*  —  {(z,q)}  Dyxzq  a  in (i). Let  Chapter 4. Square-Free Two-Factors  94  u(r/ y) be the end of the matched edge which is incident with q. If u is not even, then , q, u). If q is even, then go to Step 4.4 with Pm,, = (z, q). 0 let u be even with P = (P  (ii)  (i)  ,  Figure 4.37: Step 5e. (Change F by some edges which have one end in o) If there is any matched edge from a nondummy vertex t in 0 to an odd vertex or a nondummy vertex in another pseudovertex x where (t, x)  P, and (t, x)  , then, if 0 P  not in the special case below, go to Step 4.4 with Prn,, = (x, o). The special case is that 0 = (Ps, y, o) are in a blocking square as in Figure 4.38. Suppose P = (Pu, z, x) and P that y and z are pseudovertices. Then (y, z) is neither the stem of y nor of z. Let p(o) = y, p(x) = z and E = E U {(y, z)}. Go to Step 4.4 with F,,,,, = (x, o). If either y or z, say y, is a pseudovertex, then no longer call Dxzyt a blocking square, and let p(o)  y, p(x) = o, E = E U {(y, z)} and E = E— U {(x, z)}  z are real vertices, then let p(x) = o and E = E U {(x,z)}  \ {(t, x)}.  If both y and  \ {(t,x)}  If there is any unmatched edge in F from a vertex t in 0 to an even vertex or another pseudovertex x where (t,x) w = x.  g  ,, and (t,x) 3 P  g  , then go to Step 3.2 with v = o and 0 F  Chapter 4. Square-Free Two-Factors  95  I  Figure 4.38: If there is any pseudovertex x attached to 0, i.e. a vertex in x is on P or Ps,, then go to Step 4.4 with  =  (x,o).  For a vertex z which is either dummy odd or not in .F, and joined to a nondummy vertex in o by a matched edge, let x be even and p(x) = o. For a vertex x of,T such that p(x)  e  but P  0, let p(x) = o. Note that p(x)  \ {(x, y)}  0 in the following case: p(x) = y and y  0,  is different from 6 P U P (refer to (vii) and (viii) on p. 76).  Go to Step 2. Step 6. (Augmentation) Using the Recover Algorithm, we can find an augmenting walk. If the step previous to this one is Step 4, then go to Step 2 in the Recover Algorithm with F = P U {e, (w,p(w)), (p(w) ,p 2 (w)),... , (p’(w),p(w))} where p(w) = root(w) and look for an alternating walk ending at root(w) with an unmatched edge. If the previous step is Step 5, then some deficient vertex x which was dummy previously became nondummy and so we go to Step 2 in the Recover Algorithm with P = P 0 and look for an alternating walk ending at x with an unmatched edge. At the end of the Recover Algorithm we get an alternating walk F, and we reset F = F and go to Step 1.  P  Chapter 4. Square-Free Two-Factors  96  Step 7. (No square-free two-factor) This step is for the proof of Theorem 4.11. If CUE e  =  =  ,  then STOP. Otherwise, for each  (v, w) E CUE do the following: If either v or w (say v) is  .1, then there exists  a square S of G where all of its unmatched edges belong to F,, U {e} but not any of its matched edges; let S be a blocking square, i.e. each of  v  and  w  w  (v,p(v))})  =  v.  Otherwise,  is even or is a pseudovertex and then there exists a square S of G  where all its unmatched edges belong to F,, U F,,, U {e,  be dummy odd and p(w)  {e}  (resp. P, U {e, (w,p(w))}, P,,, U {e}, or  but not any of its matched edges. Let S be a blocking square. Now  STOP.  4.5  Some notes for the Recover Algorithm  In Step 5 in the Blossom Algorithm, we stated that if any edge in P or P is incident to a dummy vertex x or its mate  z  in another pseudovertex, then x is no longer a dummy  vertex. In this section, we will prove the statement and make some notes which are useful for the next two sections. Theorem 4.6 In Step 5, if any edge f in P,,b or Ps,,  pk(w)), i.e. (pk_l(v), pk(v)) or (p 1 (w),  is incident to a dummy vertex x or its mate z in another pseudovertex, then x is no longer a dummy vertex. Proof. Since x is dummy, it belongs to a blocking square  xyzq  of type (i)  Figure 4.36 on p. 91. Without loss of generality, we can suppose that t be the end of  f  f  (iv) in  is in P,,b. Let  which is neither x nor z, and x’ be the pseudovertex containing  x.  Let u be the end of the matched edge incident to x which doesn’t belong to x’. We will distinguish cases where  LJxyzq  is of type (i), (ii), (iii) or (iv). In each case we will  distinguish between the cases where understand the following.  f  is incident to x or  z.  Figure 4.39 may help to  Chapter 4. Square-Free Two-Factors  Case A Dxyzq is type (i) and If  97  f is incident to x:  f is unmatched, then u is even by P = (Pt, x, u). Suppose that f is matched. Since x  is dummy, x’ is not in P,. Then there exists an unmatched edge in P which is incident to x. Case B Dxyzq is type (i) and  f is incident to z:  There exists an unmatched edge in P which is incident to z. Without loss of generality, we can assume that  f is such an edge. The vertex u is even by P = (Pt, z, y, x, u).  Case C Dxyzq is type (ii) and  f is incident to x:  It’s similar to case A. Case D Dxyzq is type (ii) and  f is incident to z:  If x’ is not in P, then there exists an unmatched edge in P which is incident to z and not (z, q). Without loss of generality, we can assume that  f is such an edge. Then u is  even by P = (P,z,y,x,u). See (d)-(1) in Figure 4.39. Now suppose that x’ is in P. Then (z,q) is in P. Let g = to (z, q) in P. Then either i or (P,q,x,y,...  (i,j) be the edge next  3 = j belongs to x’, say i. If (x, y) is in P (i.e. P  ,i,j)), then ‘u is even by (P,v,p(v),p (v),... ,j,j,... ,y,x,u). Otherwise, 2  u is even by (P,v,p(v), p (v),... ,j,(P)’,z,y,x,u). See (d)-(2) in Figure 4.39. 2  Case E Dxyzq is type (iii) and  f is incident to x:  It’s similar to case A. Case F LJxyzq is type (iii) and  f is incident to z:  It’s similar to case D. Case G Ixyzq is type (iv) and  f is incident to x:  Suppose that there exists an unmatched edge in P incident to x.  Without loss of  Chapter 4. Square-Free Two-Factors  generality, we can assume that  f  98  is such an edge. Then u is even by P = (Pr, x, it).  Now suppose that there is no unmatched edge in P which is incident to x.  Then  (x,p(x)) and x’ are in P,. Let g = (i,j) be the edge next to (z,q) in Pt,. Then either i or j belongs to a?, say i. If P, = (Ps, q,•• , i,j) (resp. (Ps, y,  •.  ,  i,j)), then u is even by  (P,v,p(v),..,j,i,”.,q,x,u) (resp. (P,v,p(v),.”,j,i,”.,y,x,u)).  Case H Dxyzq is type (iv) and  f  is incident to z:  There exists an unmatched edge in P which is incident to z. Let  f be such an edge.  Note  that both (q, z) and (z, y) cannot belong to P, (otherwise, z belongs to a pseudovertex and x is not dummy). Without loss of generality, we can assume that (z, y) it  is even by P = (Pt,z,y,.x,u). The proof of Theorem 4.6 is completed. I  (b)  (a) x  (h)  g P,.  Then  Chapter 4. Square-Free Two-Factors  99  (d)(i)  (e)  (g)  (2)  x,  Figure 4.39:  Chapter 4. Square-Free Two-Factors  100  In the Blossom Algorithm, ancestors of some vertex are sometimes changed. It hap pens in the following cases (Figure 4.40)  (a)  (c)  (b) F-  I  I  ‘  I F  cL—i’ a  a  a  (d)  (e)  a (f)  Figure 4.40:  (a) Case 1 in Step 4.4, (1) in Step 4.5 and (viii) in Figure 4.36.  (b) (ii) in Step 4.5. (c) (b) in Case 2 in Step 4.4. (d) (vi) in Figure 4.36 (Step 5).  Chapter 4. Square-Free Two-Factors  101  (e) (vii) in Figure 4.36 (Step 5). (f) Figure 4.38 (step 5). In cases (a) and (b), P, is changed from (Pm, v) to (Pu, w, v). In case (c), P is changed from (w,x,y,v) to (y,x,w,v). In case (d), P is changed from (P,w,x,y) to (P,y). In case (e), P (resp. P) is changed from (P,w,x) to (P,y,x) (resp. (P,w,x,y) to (Pr, y)). In case (f), if w is a real vertex, then P is changed from (Pr, w, x) to (Ps, x). In case (c), if v is a pseudovertex, then the stem of v is changed. In case (d) (resp. (e)), the stem of y (resp. x and y) is changed. In case (f), the stem of x is changed. In cases (a) and (b), (v, w) remains as the stem of v. We use these comments in Theorem 4.8. 4.6  The Recover Algorithm  In this section, we give an algorithm to recover an alternating walk in G corresponding to a directed path in ..F. If v is even (resp. (dummy)odd), then the algorithm will produce an alternating walk P from root(v) to v ending with a matched edge (resp. an unmatched edge). If v is in a pseudovertex, then the algorithm can recover alternating walks ending with both a matched edge and an unmatched edge. The subgraph F  P doesn’t have  any square, except when either v is dummy odd or v is a dummy vertex in a pseudovertex and P ends with an unmatched edge. If it is in the latter cases, then there is only one square in F  P and the square contains v.  Our Recover Algorithm follows the usual procedure in blossom algorithms with some differences. First find the directed path P, in the current J from v to its root (Step 1) and expand pseudovertices in P, (Steps 2.2 and 3). At the beginning of the algorithm, let P be Pt,. Whenever there is a change in P (e.g. a pseudovertex in P gets expanded), then we update P. From time to time, there is a square of G which is created by P and then we make a small change in P to get rid of the square (Steps 5 and 6). In  Chapter 4. Square-Free Two-Factors  102  Step 4, we make a change in P if the same edge appears in P twice. In the usual blossom algorithm, the order of expanding pseudovertices is not important, but it is important in our algorithm. We order our choice of a pseudovertex to be expanded according to the rule which is stated at the beginning of Step 3. Otherwise, we might get a square which we may avoid and to get rid of that square we might have to make a big change in F, e.g. shrinking previously expanded pseudovertices in an uncontrolled way. This may lead to our algorithm running in exponential time. During the algorithm, we will deal with the graph obtained from G by shrinking pseudovertices in the current P. As the algorithm progresses, pseudovertices in P are expanded. When we expand a pseudovertex o, the pseudovertices in o but not in P will be opened, i.e. each of those pseudovertices will be replaced by the subgraph of G induced by the set of vertices in the pseudovertex. During the Recover Algorithm, we will use the term ‘an ancestor’ to mean an ancestor in F, not in P. Recover Algorithm (Find a desired alternating walk from a root to v.) Step 1. Let v’ be v itself or a pseudovertex containing v if v belongs to a pseudovertex. Find F,,’ in the current F. If v’ is even (resp. (dummy)odd), then P,,’ ends with a matched edge (resp. an unmatched edge). Let P = Pu,. From now on we denote  (*) and continue to use this notation after we make changes to F. Go to Step 2. Step  .  (Expanding pseudovertices so that v becomes the last vertex of P)  If v is dummy odd, then go to Step 2.1. If v,, is a pseudovertex, then go to Step 2.2.  Chapter 4. Square-Free Two-Factors  103  Otherwise go to Step 3. Step 2.1 (v is dummy odd) There exists a vertex w such that (va, w) is matched and P U {(v, w)} does not create a square (see Step 4.2 in Blossom algorithm). Add (va, w) and w to the end of  ]3  Step 2.2 (v is a pseudovertex) Recall the structure Q(v) from the Blossom Algorithm. Suppose that v. is formed by the following two dipaths and edge e (e might be more than one edge or a fake edge, i.e. an edge between two pseudovertices which are attached to each other): u 1 bf  .  .  .  u f 1 n,  bgiwi...wm_igmwm where some ui’s and wi’s might be pseudovertices. The vertex v is u, w, or belongs to one of u or w . Say that v is n or belongs to u. 3 If v had been dummy previously and became nondummy when v was formed and we look for a walk ending at v with an unmatched edge, then Theorem 4.6 tells how to handle this case. We will not repeat it here. If u is a real vertex (i.e. u  =  v) and dummy and we are looking for a walk ending  at v with an unmatched edge, do the following: In cases (i)(iv) in Figure 4.36, there exists w in v such that (v, w) is matched. Either unmatched. If P (resp. P  =  ft  =  or f+i is (v, w) and the other is  (resp. f+i) is (v, w), let  1 e 0 v  voe1v1  f  .  .  .  w 1 v_iebg  n 1 v_jebf  .  .  .  wm_igmwmeuifiui_i  u_ifuf+iuj+i  ).  .  .  .  1 f+iufu-  In case (v) in Figure 4.36, there  is no such w. From now on look for an alternating walk ending at q or y with a matched edge. At the end of the algorithm, add (q, x) or (y, x) respectively to P to obtain the  Chapter 4. Square-Free Two-Factors  104  desired walk. Without loss of generality, we can choose q and assume that q is ‘a 1 or in u. Let P  1 e 0 v  •  ebgiw v_ 1  •  •  wm_igmwmeuifiui_i  ..  .  f’a2f’a1  If u is a real vertex which is not dummy and we look for a walk ending at v with a matched edge, then choose P  f or =  f2+i  which is matched, say  1 e 0 v  u 1 v_iebf  f. Let  u_f u 2 .  Similarly for the case that ‘u is a real vertex and we look for a walk ending at v with an unmatched edge. If u is a pseudovertex, then let P  =  1 e 0 v  and rewrite P using the notation of  u 1 v_iebf  •  .  (*). Do Steps 4’-6 and go to the beginning of  Step 2.2. Otherwise, rewrite P using the notation of  (*). Do Steps 4—6 and go to Step 3.  Step 3. (Expanding the remaining pseudovertices of F) If there is no pseudovertex in F, then go to Step 8. Otherwise search from vertex v to 1 for a pseudovertex satisfying the following: v (i) it’s not an ancestor of another pseudovertex in F, and (ii) if it contains edge (x, y) in a square of the type in Figure 4.41 where neither (x, q) nor (y, z) is in P and there is another pseudovertex o in P containing (z, q), then o is one of its ancestors. In Lemma 4.7, it’s shown that there is a pseudovertex satisfying conditions (i) and (ii). Let vk be the first such pseudovertex found satisfying (i) and (ii).  Chapter 4. Square-Free Two-Factors  105  ii Figure 4.41:  Recall the structure  from the Blossom Algorithm and suppose that  Q(vk)  Vk  is formed  by the following two dipaths and edge e: u 1 bf bgiwi If neither ek+l  hits  ek vk  nor  ek+l is  f _ 1 u  •  .  wm_igmwm  .  the stem of ‘Uk, then do Step 7. Say that  at u. Similarly for the case that ek+l is the stem of  ek  is the stem of Vk and  Vk.  If u is a real vertex and ek+l is matched (resp. unmatched), then choose which is unmatched (resp. matched). If P  = v 1 e 0  f,  u 1 vk_lekb f  (resp.  •  f,  or f+i  f+i) is chosen, let  u1_1fuek+1vk+l  (respectively, P  =  1 e 0 v  •  vk_lekbglwl  .  wm_lgmwm  eulf1u1_l...u+lf+1uek+lvk...vfl_levfl).  Let’s consider the case when ek+l is a fake edge and u is a real vertex. If one of or f+i,  say  f,  f,  is unmatched and belongs to a square of G (i.e. case (i) in Figure 4.42),  then let P  =  1 e 0 v  vk_lekbglwl  . 1 euifiui_  .  .  Wml9mWm  u1+1f+luek+1vk  v_iev.  Chapter 4. Square-Free Two-Factors  106  Otherwise (case (ii) in Figure 4.42), choose  f  or f+i which is unmatched and let P be  chosen in the same way as above.  (I)  (ii)  I  Vk  — — —  ‘.  I  I  S  _c?/  I  Vk  ,I  . -.  ——  o  Figure 4.42: If u is a pseudovertex,  ek+1  is matched, and  ek+1  hits u at a vertex x which had  been dummy previously and became nondummy when pseudovertex vk was formed, then Theorem 4.6 tells how to handle this case. If u• is a pseudovertex and F’ creates a square of G containing ek+1 (Figure 4.43) where F’  =  1 e 0 v  vk_lekbflul  .  . .  then let P  =  1 e 0 v  vk_lekbglwl  _ 1 eu,fiu  wm_igmwm  u1+1f+1uek+1vk  .  v_iev,,.  Note that P doesn’t create a square containing ek+1. If it’s not any of the above cases already considered in Step 3, then let P  = v 1 e 0  vk_lekbflul  u1_1fuek+1vk+1  v_iev.  Chapter 4. Square-Free Two-Factors  107  (I)  (ii) _____  -‘‘S  .  1 f+  k÷1  “  Figure 4.43: Rewrite P using the notation of (*). Do Steps 4—’6 and go to the beginning of Step 3.  Step 4. If an edge e appears twice in P changing either from unmatched to matched or from matched to unmatched, one of the cases in Figure 4.44 must occur. In case (i), let In case (ii), let  ek = ek =  (q,z), (y,z),  Vk = z, Vk = z,  and and  ek+1 = ek+1 =  (z,y) in P. (z,q) in P.  Go to Step 5. Step 5. If an unmatched edge of  (z,  (z,  q) in P belongs to a square of the type in Figure 4.41 and none  y), (q, x) and (x, y) is in P, then the square is one of the cases in Figure 4.45. Here  we assume that (x, y) is not in P if (x, y) is in a pseudovertex in P which has not been expanded yet.  Chapter 4. Square-Free Two-Factors  108  (ii)  (i)  Figure 4.44: All of x, y, z and q belong to a pseudovertex o, and x and y belong to a pseudovertex in o. Neither (y, z) nor (q, x) is the stem of the pseudovertex containing x and y, except case (iv). In case (iv), (q, x) is the stem of the pseudovertex. Assume that o is formed by the following two dipaths and edge e: u 1 bf  .  .  .  f _ 1 u  bgiwi..wm_igw and x and y belong to u. The vertices z and q might be in b, or some uj or w. In cases (i)’(iv), o or a pseudovertex in o containing z and q was expanded in either Step 2.2 or 3 before we started the current steps 4’-..’6. In cases (v) and (vi), a pseudovertex in o containing z and q is expanded in either Step 2.2 or 3. In case (i), divide it into two cases depending on whether z and q are not in b or some h  (1  uh  (1 h  h  i) or otherwise. First suppose that z and q are in neither b nor any  i). Note that b has not been expanded yet if b is a pseudovertex. Let k be  Chapter 4. Square-Free Two-Factors  109  / /  (v)  (iv)  (vi) /  V  /  /  /  UI  Figure 4.45:  >p  Chapter 4. Square-Free Two-Factors  such that  k = 13  j(>  b and  P where  e’ =  110  k) be such that e 3 1 e 0 v  =  =  (z,q) in P. Set fue’qev.  ekvkflul..  (x, q). See (i) in Figure 4.48. If  •  2 ev  and q are in b or some  z  h  (1  h < i), one  of the cases in Figure 4.46 must occur (we subdivide it into two subcases depending on whether or not there is some after  (z,q)  vd  in P which is the end vertex in  11 ‘ h  of fh+1 and  vd  appears  in P):  (a)  ,,----  -  -  /  /  Figure 4.46: In the both cases, for some k, fh  =  Let  ek.  P where e’  =  uh  =  or a pseudovertex in  j(>  k) be such that  1 e 0 v  e = (z,  ekuhfh+luh+1.  (y, z). In (b), there is some  Vd  is expanded in either Step 2.2 or 3 and  u  .  q). In (a), set  fue’zejvi  .  .  which is the end vertex in  uh  pseudovertex containing it. Let P where e’  =  (y,z).  =  1 e 0 v  ekuhe’u1fu_1f1  See Figure 4.47  .  .  .  fh+lvded+lvd+1  eV  of  fh+1  or a  Chapter 4. Square-Free Two-Factors  111  /  Figure 4,47: In case (ii), if b is a pseudovertex then b has not yet been expanded. Let k be such that  vk =  b and  j(>  k) be such that e 3 P  where  e’ = (y,z).  = v 1 e 0  Note that  z  = (z,  q). Set fue’zev  ekvkflul  and q cannot be in any  after a pseudovertex containing x and y is formed, so  Uh  (1  (z, q)  h < i) (edge  is not in  (z,q)  is in .T  See Figure 4.48  (ii). Case (iii) is similar to (ii). See Figure 4.48 (iii). In case (iv), x and y belong to P where e’  = (z,  of having  1 u  and let  j  be such that  e = (z,  q). Set  = v 1 e 0  y). See Figure 4.48 (iv). When u is expanded, we will handle the difficulty  3 = (z, e  q) appear twice in Step 4.  In case (v), b appears twice in P. Without loss of generality, we can assume that appears in P before (t, b). Then k (d < k). Let  j  vd = Uk =  be such that e 3  = (z,  b,  ed+1 =  q). Then  (b, r), and  v = z  ek =  (r,  b)  (t, b) for some d and  or a pseudovertex containing  z,  Chapter 4. Square-Free Two-Factors  and  1 = v_  P where e’  q or a pseudovertex containing q. Set  = v 1 e 0  =  112  (y,  z)  edvdflul  and e”  =  vd+3ed+3vd+2e tekvk  (s,t). See Figure 4.48 (v).  Case (vi) is similar to (v). See Figure 4.48 (vi). Note that in the above new P, no  uh  has been expanded (this is proved in Lemma 4.13).  Go to Step 6 Step 6. Note that we have completed Step 5 before this step. If there is a square of G where all its unmatched edges belong to P but not any of its matched edges, then it’s one of the cases illustrated in Figure 4.49. The proof of Theorem 4.8 helps a reader understand how we deduce these cases. In all of the cases, all of the four vertices q, x, y and  z  belong to a pseudovertex o,  and x and y belong to a pseudovertex in o. Assume that o is formed by the following two dipaths and edge e: bfiui...ui_ifjuj w 1 bg  ..  Wm_l9mWm  and x and y belong to u. In cases (ii) and (iii), q some  =  b. Possibly  z  and q might be in  or w in case (i), but not in cases (ii) and (iii). In case (i), if  some u, then  j  >  i. In either Step 2.2 or 3,  ‘u  z  and q are in  or a pseudovertex in u containing x and  y has been expanded. Let u be the pseudovertex expanded in either Step 2.2 or 3 and be such that e 3  = (z,q).  In case (a) in (i), let h be such that eh is the stem of u. Set P  = v 1 e 0  v_1eveuehvh•  ev  j  Chapter 4. Square-Free Two-Factors  113  (iii) S S  (v)  (iv)  —  (vi)  —  /  Figure 4,48:  ‘I  Chapter 4. Square-Free Two-Factors  114  \ /  Figure 4.49:  Chapter 4. Square-Free Two-Factors  where e’  115  (z, y). In (b), similar to (a). See (i) in Figure 4.50.  In case (ii), let k be such that  Vk  is q or a pseudovertex containing q. Then ek  =  (x, q).  Set P where e’  =  =  1 e 0 v  _ieve 3 v  •  Vk  ev  is q or a pseudovertex containing q. Then  or a pseudovertex in u containing y, and P =  •  (z,y). See (ii) in Figure 4.50.  In case (iii), let k be such that  where e’  uekvk  =  1 e 0 v  Vk_1  Vk_2  is y  is a pseudovertex in u containing x. Set  evevk_2ek_1vk_1ekvk••  ev  (z, y). See (iii) in Figure 4.50.  Note that u is reshrunk again in this step. pseudovertex can be expanded at most  In Lemma 4.14, we show that each  O(IVI) times. Return to where Steps 4r’.,6 were  called in either Step 2.2 or 3. Step 7. If a pseudovertex o is in P, then the stem of o is added to P except Figure 4.43 in Step 3. Since neither ek nor  ek+1  is the stem of  Vk,  one of the cases in Figure 4.51 must occur.  Without loss of generality we can assume that e the real vertex where edge e and P  =  =  ek  and  f  f are incident. Let  1 e 0 v  vk_lekuek+lvk+1  ev  and go to the beginning of Step 3. In (b), assume that e is the stem of pseudovertex  Vk,  In (a), let u be  Vk  and expand  i.e. return to where Step 7 was called in Step 3.  Step 8. If  v  is dummy or dummy odd, then eliminate the last vertex w and edge (v, w). Now we  have the alternating walk which we were looking for.  Chapter 4. Square-Free Two-Factors  116  (i)  (a)_—  (b)  ——  —  ,__ — — —  ,  \ /  (ii)  (iii) I  I  I  I  I  I  I  I  I  \  Figure 4.50:  Chapter 4. Square-Free Two-Factors  117  (ii)  (I)  /  /  \  I /  \  /  stem stem 0 Figure 4.51: 4.7  The validity of the Recover Algorithm  In Step 3 in the Recover Algorithm, we stated that there is a pseudovertex in P satisfying conditions (i) and (ii) if there is a pseudovertex in P. In this section, we will prove the statement and the validity of the Recover Algorithm. Lemma 4.7 At the beginning of Step 3, if there is a pseudovertex in F, then there exists a pseudovertex in F satisfying conditions (i) and (ii). Proof. Assume that there is no such pseudovertex,  Clearly there is a pseudovertex  satisfying condition (i). Let w ,w 1 ,•• , wk be pseudovertices satisfying condition (i). 2 For each i, there exist Dxyzq of the type in Figure 4.41 and a pseudovertex o which prevent the pseudovertex w from being expanded by condition (ii). The pseudovertex o is not an ancestor of w. The pseudovertex o is either wj or an ancestor of wj for some  {  i  j =  i. Construct a digraph G’ 1,2,•  ,  =  (W, D) in the following way: The set W is  k} and the set D consists of arcs w  —+  3 where o is either wj or an w  Chapter 4. Square-Free Two-Factors  118  ancestor of w . Then each vertex w in G’ is the tail of some arc. Since G’ has a finite 3 number of vertices, then there is a dicycle. Let C  =  2 1 w  1 be the dicycle. Then o w  is either w+i or its ancestor (here we consider 1 as 1 + 1). Without loss of generality, we can assume that among (z , qj) (zi, q) is the last added to F. When edge (z 1 , qj) is added, 1 the pseudovertex w 1 has been formed already. After edge (z , qi) is added, a pseudovertex 1 is formed containing w and o. Since w1 is either o or its descendent, w 1 is in the new pseudovertex or its descendent. After all of (z , qj) (i 1 for  j  =  1•.• , 1  —  1) are added to F,  2 and o or its descendent. When > i, w is either in a pseudovertex containing w  (zi, q) is added to F, the pseudovertex w 1 has been formed already and is either in a pseudovertex containing w 1 or its descendent. Since 1 and o w 1 are in a pseudovertex or  Wi  01  is either w 1 or its ancestor, either  is a descendent of Oj when (zi, q) is added. If Wi and  01  are in a pseudovertex, then the edge (zi, qi) must not be added. So w 1 is a descendent  of  Oi,  contrary to the assumption. I  Now, we will show that at the end of the Recover Algorithm we get an alternating walk which we look for. Theorem 4.8 A walk P which we get at the end of the Recover Algorithm is an alter  nating walk from root(v) to v and P  F doesn’t contain any square, except when v is  dummy or dummy odd and there exists a square containing v. Proof Clearly P obtained at the end of the algorithm is alternating. Now we have to verify that P  F doesn’t contain any square except that when v is dummy or dummy  odd there exists a square containing v. Without loss of generality, we can assume that v is neither dummy nor dummy odd. We will prove by induction on the running of the Recover Algorithm that P  eF  doesn’t contain any square of G in the shrunk graph,  that is the graph obtained from G by shrinking pseudovertices in the current P. The inductive step is that when a pseudovertex is expanded and we get new P at the end  Chapter 4. Square-Free Two-Factors  119  of Step 6 there is no square of G where all its unmatched edges belong to P but not any matched edges. Clearly there is no such square of G for the initial P, i.e. P in Step 1. Assume that there is a P having such a square. Let  *  be the P and Dvwxy  be the square. Without loss of generality, we can assume that there is no such square for previous P’s. Let P’ be the previous P and o be the pseudovertex in P’ which is expanded. Since Elvwxy appears after o is expanded, at least two vertices in flvwxy are in pseudovertex o. Claim 1 A pair of vertices in LJvwxy cannot belong to any pse’udovertex in o. Proof. Suppose that a pair of vertices in Dvwxy belongs to a pseudovertex u in o. First consider the case that a pair of vertices which are adjacent in Dvwxy are in u. Without loss of generality, we can assume that v and w are in u. The edge (v, w) must be matched (otherwise, u is in  *  and u has not been expanded yet, so Dvwxy must not appear yet).  The edge (w, x) must be matched (otherwise,  it  is in P*).  Similarly (v, y) must be  matched. At least one edge in Dvwxy must be unmatched. By the above argument, (x, y) is the only edge which can be unmatched. Neither x nor y is in u (otherwise u is in P*). It must be one of the cases in Step 5. Now suppose that a pair of vertices which are  not adjacent in Elvwxy are in  it,  say v and x are in  it.  Without loss of generality, assume  that neither w nor y is in u (otherwise, it’s the previous case that two adjacent vertices in Livwxy are in  it).  There is at least one unmatched edge in Ovwxy. Suppose that  (v, w) is unmatched. Then  it  is in P’ and Dvwxy must not appear yet. This completes  the proof of Claim 1. From now on we can assume by Claim 1 that any pair of vertices in Dvwxy doesn’t belong to a pseudovertex in o. All of the four vertices v, w, x and y cannot be in o. (If all v, w, x  and y are in o, then Evwxy is a square of type (ix) or (x) in Figure 4.36. Without  creating a square, we can reach each vertex with a matched edge and an unmatched  Chapter 4. Square-Free Two-Factors  120  edge.) So either two or three vertices are in o. There exists an edge in  Dvwxy  joining a  vertex in o and a vertex not in o. Claim 2 At most one edge of Dvwxy joining a vertex in o and a vertex not in o is unmatched. If there is such an edge, then it’s the stem of o. Proof. Let F’  =  1 e 0 v  and vk be pseudovertex o. Let e be an unmatched edge  •  in Dvwxg joining a vertex in o and a vertex not in o. Then either e is  or ek+1, or a  ek  vertex in o is added to F twice (it must be one of the cases in Figure 4.52). Either ej or ek+1 is the stem of o, say ek. In Step 3, P is chosen such that P doesn’t create a square containing ek+1. Thus e cannot be ek+1. Suppose that e situated as in one of the cases in  Figure 4.52. In case (i), there is no square containing e. In case (ii),  flvwxy must have  already appeared when we formed F’. This completes the proof of Claim 2.  (ii)  (i) II,  0  ,‘ S  I I  I  I  0  () \__  I  S  S I  I  I  Figure 4.52: As mentioned above, we have two possibilities: (A) Three vertices in (B) Two vertices in  Dvwxy  Case A Three vertices in  Dvwxy  are in o.  are in o.  Dvwxy  are in o:  Without loss of generality, we can assume that y is not in o. When pseudovertex o was  Chapter 4. Square-Free Two-Factors  121  formed, one of (v, y) or (x, y) satisfies one of the following three cases: (i) matched and belonged to P , (ii) unmatched and didn’t belong to P 0 0 (it might not have been in F), or (iii) belonged to a pseudovertex. (Note that P 0 is the path from o to its root in F.) Otherwise Dvwxy must appear when pseudovertex o was formed. It must be one of type (i)(iv) in Figure 4.36. We keep it as a blocking square with one of its vertices as being dummy, until we encounter one of the cases in Step Sd in the Blossom Algorithm. Say that (v,y) is such an edge, i.e. (v,y) was as in case (i), (ii), or (iii). If (v,y) was matched and belonged to F , (v, y) was the stem of o and stays as the stem of o until the end of the 0 Blossom Algorithm (it’s not any case on p. 100). Since it’s not any case in Figure 4.51, (v, y) is in P’. If (v, y) is unmatched, then by Claim 2 (v, y) must be the stem of o and  was the stem of o when pseudovertex o was formed (it’s not any case on p. 100). We cannot have case (i) or (ii). Now suppose that (v, y) belonged to a pseudovertex u. Since v belongs to both u and o, either u is inside o or u and o are attached to each other. If u is  inside o, then y belongs to o, a contradiction. It’s not possible that u and o are attached to each other at vertex v. If two pseudovertices are attached to each other at a vertex, then both edges in a square which is incident to the vertex belong to one pseudovertex (see Figure 4.25). In this case, w is the only possible vertex at which two pseudovertices are attached to each other, not v. Case B Two vertices Dvwxy are in  0:  Suppose that a pair of vertices which are not adjacent in Dvwxy are in o. Say that v and x are in o. At least one edge in Dvwxy is unmatched. Say that (v, w) is unmatched. By Claim 2, the other three edges must be matched and (v, w) must be the stem of o. Since (v, w) is the stem of o and v is the true base of o, the two matched edges incident to v  must be in o, a contradiction that matched edge (v, y) is not in o. So the two vertices which are in o must be adjacent in Dvwxy. Without loss of generality, we can assume  Chapter 4. Square-Free Two-Factors  122  that x and y are not in o. When pseudovertex o was formed, one of (w, x), (x, y) or (v, y) satisfies one of the following three cases: (i) matched and belonged to P , (ii) unmatched 0 and didn’t belong to P 0 (it might not have been in .F), or (iii) belonged to a pseudovertex. The edges (w, x) and (v, y) can not be such an edge for the similar reasons as in Case A. So (x, y) is such an edge. We will distinguish the cases for (x, y) as (i), (ii), or (iii). In each case, we will distinguish between the cases where both (w, x) and (v, y) are matched or not. (i) (x, y) E P 0 and is matched: (a) One (w, x) or (v, y) is unmatched: Say that (v, y) is unmatched. Then (v, y) is the stem of o by Claim 2. So p(y) = where x’ is x itself or a pseudovertex containing x if x belongs to a pseudovertex. The vertex w is even with p(w) = x’ before v is odd with p(v) = y. So w continues to have p(w) =  or forms a pseudovertex either with x’ or an ancestor of x’. But  eventually w and v are in the same pseudovertex and then the pseudovertex must contains x and y, a contradiction that o contains only v and w, not x and y. (b) Both (w, x) and (v, y) are matched: Without loss of generality, we can assume that y was the predecessor of x when (x, y) was added to .F. So y is (dummy)odd or a vertex in a pseudovertex. Let (t, y) be an unmatched edge in F which is incident to y. Since our graph has only vertex-disjoint squares, there is no square containing edge (t, y). The vertex y must be odd or nondummy in a pseudovertex and v must be even with p(v) = y. The vertex y stays as an ancestor of v until pseudovertex o is formed, and the edge (v, y) becomes the stem of o. Since we are not in any case shown in Figure 4.51, (v,y) p*  Chapter 4. Square-Free Two-Factors  (ii) (x, y)  123  0 and is unmatched: P  (a) One of (w, x) or (v, y) is unmatched: Say that (v, y) is unmatched. Then (v, y) is the stem of o and (w, x) is matched by Claim 2. Then one of the following cases must occur (Figure 4.53):  (ii)  (I)  I  I  /  /  /  O  / -2  Figure 4.53: In Step 6, we modify P to avoid Dvwxy. (b) Both (w, x) and (v, y) are matched: Here we assume that (x, y)  e  F before pseudovertex o was formed. We will arrive at  a similar conclusion if we assume that pseudovertex o was formed while (x, y)  F.  Without loss of generality, we can assume that y is the predecessor of x when (x, y) is added to F. Assume that F here is the one existing when pseudovertex o was formed. Let x’ be x itself or a pseudovertex containing x if x belongs to a pseudovertex. Since (x, y) is unmatched and y is the predecessor of x when (x, y) is added to F, x’ is (dummy)odd or a pseudovertex. We noted already that (w, x) could not be  Chapter 4. Square-Free Two-Factors  . So (w, x) 0 matched and E P  124  gP . If (w, x) g Ps,, then another pseudovertex is 0  formed, which contains o, x and y (see (i) in Figure 4.54). In Steps 5 and 6, we modify P to avoid Evwxy. Suppose that (w, x) E Pr’. Since (w, x) is in a square containing (x, y), x’ does not have both w and y as predecessors in SP. The vertex y must be in x’ and (w, x) is the stem of x’ (see (ii) in Figure 4.54). If (x, y) is in (i.e. x’ is in p*), then (w,x) is in PK also (it’s not any case in Figure 4.51).  (ii)  (i)  I  S  I  S  X  -,  \ F  0 /  Figure 4,54:  (iii) (x, y) belonged to a pseudovertex u: (a) One of (w, x) or (v, y) is unmatched: Say that (v, y) is unmatched. Then (v, y) is the stem of o by Claim 2 and p(o) The pseudovertex  it  =  has not been expanded, and Dvwxy must not appear yet at  this stage in the expansion of P. (b) Both (w, x) and (v, y) are matched: Assume that .F here is the one existing when pseudovertex o was formed. Since u  Chapter 4. Square-Free Two-Factors  125  has been expanded already, p(o)  u and neither (w, x) nor (v, y) is in P . If either 0  (w,x) or (v,y) is in P, say (v,y), then (w,x) is not in P. Another pseudovertex must be formed, which contains a and o ((i) in Figure 4.55). The edge (x, y) must be matched (if (x,y) is in  then (v,y) is in .P*). If neither (w,x) nor (v,y) is  *,  in P, then another pseudovertex must be formed, which contains u and o ((ii) in Figure 4.55). In Steps 5 and 6, we modify P to avoid Dvwxy.  (ii)  (I)  ,/  / /  \\  ol  IL_i:  1  \  \\  ,ll,!  \ \  —  —  Figure 4.55:  The proof of Theorem 4.8 is completed. I  4.8  The structure of F at the end of the Blossom Algorithm  In this section, we will describe the structure of F when the Blossom Algorithm ter minates. This will be useful in Section 4.9, If no remark is given, F is the square-free (0,2)-factor at the end of the algorithm. Recall that a vertex v is deficient if deg(v) <2 for the current F. When the algorithm terminates, each vertex v is one of the following: (dummy)odd,  Chapter 4. Square-Free Two-Factors  even, a vertex in a pseudovertex (either dummy or nondummy), or v  126  F. The vertex  has the following properties: (i) If a vertex v is odd, then there are two matched edges incident to v. The other ends of both matched edges are even or in a pseudovertex, (ii) If v is dummy odd, then there are two matched edges incident to v, one of which is in a blocking square and the other has an end which is dummy odd, even, a dummy vertex in a pseudovertex or not in F, (iii) If v is dummy odd, then there is only one unmatched edge to v from an even vertex or a vertex in a pseudovertex, which is in a blocking square, (iv) If a vertex v is not in F, there are two matched edges incident with v, of which the other ends are dummy odd, even, dummy vertices in a pseudovertex, or not in F. The ends cannot be odd or a nondummy vertex in a pseudovertex, (v) There is no unmatched edge from an even vertex or a vertex in a pseudovertex to a vertex not in F, (vi) There is no unmatched edge where its ends are even vertices or vertices in a pseu dovertex, with the exception of a stem of a pseudovertex or an edge in a blocking square, (vii) There is no matched edge between two pseudovertices, except for the following three cases: (a) the stem of one pseudovertex, (b) an edge with one end dummy, or (c) an edge in the case shown in Figure 4.38, (viii) In a pseudovertex, either its true base is deficient or the stem of a pseudovertex is the following: it’s a matched edge from an (dummy)odd or a nondummy vertex in  Chapter 4. Square-Free Two-Factors  127  another pseudovertex, or an unmatched edge from an even vertex or a vertex in another pseudovertex. It may be in a blocking square, and (ix) In a pseudovertex, its true base or dummy vertices can be deficient, but no other vertices can be deficient. If there is a deficient vertex v which is neither the true base of the pseudovertex nor a dummy vertex, then there is an augmenting walk from a root to v and so we can decrease the deficiency of F. A blocking square is created in Step 4.1 ((i) and (ii) in Figure 4.29), Step 4.5 ((iii) and (v) in Figure 4.33), Step 5 ((i)—(iv) in Figure 4.36), or Step 7. Labels of some vertices in a blocking square might have been changed after it was created. At the end of the algorithm, blocking squares are the types shown in Figure 4.56. In a blocking square of type (i).-.’(iv), all of four vertices cannot be pseudovertices. In a blocking square of type (v)(viii), the mate of a dummy vertex must not be in a pseudovertex. Let o be any pseudovertex. Let E(o) be the set of edges where it’s not in a blocking square, and its one end is a nondummy vertex in o and the other end is even or in another pseudovertex. Let BS(o) be the set of edges in blocking squares of which at least one vertex is in o. Let H(o)  =  G[O] U E(o) U BS(o) where 0 is the set of vertices in o.  A vertex v in o except its true base and dummy vertices is matched by two edges, the other ends of which are in o, even, or in another pseudovertex. Both of the matched edges are in H(o). If v is a dummy vertex and the blocking square containing v is not type (viii), then there is one matched edge in G[0] incident to v. Property (viii) says that either the true base b of o is deficient, or its stem is a matched edge from a (dummy)odd or a nondummy vertex in another pseudovertex or an unmatched edge from an even vertex or a vertex in another pseudovertex. If the stem is an unmatched edge from an even vertex or a vertex in another pseudovertex, then there  Chapter 4. Square-Free Two-Factors  (I)  (H)  128  (iii)  (v)  (vi)  (vH)  (viii)  Figure 4.56:  (iv)  c)  Chapter 4. Square-Free Two-Factors  129  are two matched edges incident to b, both of which are in G{OJ. Suppose that b is not dummy in o and the stem is a matched edge from a (dummy)odd vertex or a nondummy vertex in another pseudovertex. Then there is another matched edge incident to b, of which the other end is even or a vertex in a pseudovertex. So the matched edge is in H(o). If the stem is from an odd vertex, then it’s not in H(o) and there is only one matched edge in H(o) incident to b. Otherwise (i.e. the stem is from a dummy odd vertex or a nondummy vertex in another pseudovertex) it is in H(o). In this case, there are two matched edges in H(o) incident to b. Suppose that b is deficient and nondummy in o. Then there is a matched edge e incident to b (if there is no matched edge, then an augmentation is made since b is not dummy). The end of e which is not b is either even or a vertex in a pseudovertex, so e is in H(o). Suppose that b is dummy in o. Then b belongs to a blocking square of type (viii) in Figure 4.56. There is no matched edge in G[O] U BS(o) which is incident to b. By the definition of E(o), there is no matched edge in E(o) incident to b. We want to summarize the above and state it explicitly as two lemmas. Lemma 4.9 If a vertex v in o is neither the true base of o nor dummy, then there are  two matched edges in H(o) incident to v. If v is a dummy vertex in o and the blocking square containing v is not type (viii) in Figure 4.56, then there is one matched edge in H(o) incident to v. Lemma 4.10 There are two matched edges in H(o) incident to the true base b, except  when b is deficient or a dummy vertex, or the stem is a matched edge from an odd vertex. If b is deficient or the stem is a matched edge from an odd vertex, then there is only one matched edge in H(o) incident to b. If b is a dummy vertex, then b belongs to a blocking square of type (viii) in Figure 4.56 and there is no matched edge in H(o) incident to b.  Chapter 4. Square-Free Two-Factors  4.9  130  A Tutte-type Theorem  In this section, we will derive a Tutte-type theorem for a square-free two-factor when G is a graph whose squares are vertex-disjoint. Also the theorem gives a necessary condition for the existence of a square-free two-factor of G when G is an arbitrary graph. At this moment we don’t know whether it is also sufficient in a general graph. The theorem proves that if the Blossom Algorithm terminates without a square-free two-factor then there is no square-free two-factor in G. A similar, though incorrectly worded, theorem for triangle-free two-factors is in [31], which uses the idea of vertex splitting. Given G = (V, E). Let S  e  V and A  follows: For  v  ,v 1 v ,••• 2  and edge (u, v) with  ,  Vk  A, if  (i) every vertex  v  (ii) every vertex  v  deg[\] (v)  (V  \ S).  Construct the graph GA[V  \ 5]  as  = 0, do nothing. Otherwise, replace v with vertices  (‘u, v)  such that  has degree 1 or 2 after splitting, and of degree 2 is in a square or a diamond where a diamond is the  following type of a graph (Figure 4.57).  Figure 4.57: Let B C V U, in GA[V  \ (S U A)  \ S]  have the following long list of properties: If  which is a square or a diamond with vertices  (i) none of w, x and y belongs to B, (ii) the degree of  v  in GA[V  \ S]  is greater than 2,  v, w,  v E  B, there exists  x and y such that  Chapter 4. Square-Free Two-Factors  131  (iii) at least one of w, x and y is in A, (iv) if U, is diamond, then v is one of the vertices which has degree 3 in U, and (v) any pair of w, x and y is not joined in GA[V  \ S]  by other than edges in squares.  Split v E B into two vertices so that one of its split vertices is in a square. Call the other part (i.e. the part not in a square) a degenerate petal. If there exists a diamond in the resulting graph, then split all the vertices of A in the diamond into vertices of degree one. Let T = A U B and GT[V \ S] be the resulting graph. A component of GT[V \ S] can be (i) an isolated vertex, (ii) an isolated edge, (iii) an isolated square, or (iv) subgraphs in G[V \ (S UT)] are joined by an edge in a square, and some edges, squares and degenerate  petals are attached to one of subgraphs (Figure 4.58). Call a component in GT[V  \ S]  a  blossom tree.  Define a center in the following way: Form a graph G from GT [V edges in a square which has a split vertex from G[V  \ (S U T)}.  \ S]  by deleting  If a square has only one  split vertex and two vertices which are in one component of the resulting graph G, then put back in the graph G the edges in the square (Figure 4.59). Call a component in the resulting graph a center. Call the following types of Dvwxy a square petal (Figure 4.60): (p’) One vertex of Dvwxy has degree more than two in GT [V \ 8] and the vertex which is not adjacent to the vertex in Dvwxy is a split vertex of a vertex in B. The other two vertices are split vertices of vertices in A. (p) At least three vertices in Dvwxy are split vertices which is not type (p’). (q) One pair of vertices which are not adjacent in Dvwxy belong to one center and the other two vertices are split vertices.  Chapter 4.. Square-Free Two-Factors  132  a degenerate petal  a component in G[V-(S UT)] Figure 4.58: A blossom tree  Chapter 4. Square-Free Two-Factors  133  one center  I I I  )  I /  1 /  a component in G Figure 4.59: (r) One pair of vertices which are adjacent in Dvwxy are split vertices and the other two vertices belong to different centers. (s) One pair of vertices which are not adjacent in flvwxy are split vertices and the other two vertices belong to different centers. (t)  One vertex is a split vertex and the other three vertices belong to different centers.  We call an edge an edge petal if at least one of its ends is a split vertex of a vertex in A and has degree 1 in GT[V  \ Sj.  Call a split vertex in a petal a tip of the petal.  Note that an edge is both an edge petal and in a degenerate petal if one end is a split vertex of a vertex in A and the other end is a split vertex of a vertex in B. Denote by an odd blossom any blossom tree where each center has an odd number of petals and has neither a degenerate petal nor a square petal of type (p’). The reason we define an odd blossom as one having neither a degenerate petal nor a square petal arises on  Chapter 4. Square-Free Two-Factors  134  (q)  (p,)  (r)  (s)  0  (t)  a center Figure 4.60:  Chapter 4. Square-Free Two-Factors  135  p. 148(a component of type (v) is not an odd blossom). Call a blossom tree which is not an odd blossom an even blossom. An isolated vertex and an isolated edge are considered to be even blossoms. An isolated square is considered to be an odd blossom with one center and one square petal of type (p). A blossom tree with no center, i.e. no vertex in V  \ (S U T),  is considered to be an even blossom except when it is an isolated square.  Let =  the number of centers in odd blossoms,  p’  =  the number of square petals of type (p’),  p°  =  the number of square petals of type (p) in odd blossoms,  0 q  =  the number of square petals of type (q) in odd blossoms,  =  the number of square petals of type (r) in odd blossoms,  0 s  =  the number of square petals of type (s) in odd blossoms, and  0 t  =  the number of square petals of type  (t)  in odd blossoms.  Let C(S, T)  =  21T1  ](v) 5 degG[V\  —  —  3BI, and  yEA  D(S, T)  =  0+p c 0+q 0  —  0 + 2p’. t  Theorem 4.11 G has a square-free two-factor if and only if for all S and T with an associated splitting as described earlier in this section,  21S1 Proof.  (=)  C(S,T)+D(S,T)  Let F be a square-free two-factor of G. Choose S and T be any pair of  disjoint subsets of V and split vertices of T as described in earlier this section. Divide T  Chapter 4. Square-Free Two-Factors  136  into two sets A and B satisfying the description earlier. Let F’  2V \ S  21S1  \ SI  —  F fl G[V  \ S].  Clearly,  21F’I C(S,T)  =  21V  =  21V\ (SUT)I +  —  =  —  21F’I + C(S,T)  deg[V\s](v)  +31B1 —2IF’ +C(S,T).  yeA  It’s enough to show that  21V \ (S U T)I +  degG[V\S](v)  +  31B1  —  21F’I  D(S, T)  (4.8)  yEA  Let A’ be the set of split vertices of vertices in A, B’ be the set of split vertices of vertices in B which are tips of square petals, B” be the set of split vertices of vertices in B which are tips of degenerate petals. Equation (4.8) holds if for each component C in the graph GT[V  \ 5], deg(v)  2I(V\(SUT)) nC+  +IB”flCI —21F’flCI  vEA’UB’  J  (  cc+p+qc—tc ifCisanoddblossom 2p  otherwise  ()  where cc is the number of centers in C and similarly for Pc, qc, t and p. An odd blossom doesn’t have a square petal of type (p’). If C is an odd blossom, then p’c  =  0.  Let 2 ifv is in V\ (SUT) (i.e. in acenter) 2 if v is in A’ and a tip of a square petal b(v) =  1 if v is in A’ and a tip of an edge petal  (4.10)  2 ifvisinB’ 1 if v is in B” (i.e a tip of a degenerate petal) Let C be any component of GT[V \ 5]. If deg,fl(v)  =  b(v)  for every vertex v in C, then  LHS of (4.9) is 0. Except for a tip of a degenerate petal, a vertex v cannot have degree  Chapter 4. Square-Free Two-Factors  137  more than b(v) in F’ fl C. A vertex  v  is said to be short if  F’ fl C. The shortage of a subgraph  Q  of C is  VEQ[b(v)  —  v  has degree less than b(v) in  deg,flØ(v)]. We have to show  that the shortage of C is greater than RHS of (4.9). Case A C is an odd blossom: If C is an isolated square, then LHS of (4.9) is  2 and RHS is 2 (since an isolated square  is an odd blossom with one center and one square petal of type (p)). Suppose that C is not an isolated square. Tips of square petals are least short when they are matched in the following way (Figure 4.61):  (i)  (ii)  (iv)  (v)  (iii)  (vi)  Figure 4.61: A square petal of type (p), (q) or (s) has at least one short tip. Claim 1 If F’ is as in Figure 4.61 and every edge petal is matched, then each center in C has at least shortage one except one center in a square petal of type (s) and (t).  Chapter 4. Square-Free Two-Factors  Proof. Let  Q be any center in  138  C. Suppose that there is no square petal of type (s) and  (t) where both edges having an end in  Q are either matched or unmatched. Then in a  square petal except type (q), there is only one matched edge having one end in square petal of type (q), there are three matched edges having one end in  Q. In a  Q. Let 1 be  the number of edge petals of Q, p be the number of square petals of type (p). Similarly for qq, rQ,  and tQ. Then  Sq  deg,(v)  =  21F’ fl QI  + 1 +PQ + 3qQ + rQ +  Sq  + tq.  vEQ  and deg,(v) vEQ  Since  b(v)  =  2IQ.  vEQ  Q has an odd number of petals,  1 + Pq + 3 qQ + rQ +  deglfl(v)  Sq  + tq is odd. So  2Q—1  vEQ  Then there is at least shortage one for the center  Q. This completes the proof of Claim 1.  Suppose that F’ is as in the hypothesis of Claim 1. CC  —  SC  —  Then there are more than  t centers which have at least shortage one, so the shortage of C is more than  c + PC + q  —  tC  (=  cc  —  sc  —  t + PC + q +  Sc’).  If some center not in the exceptional  cases described in the above claim doesn’t have shortage at least one, then there exist an edge petal which is not matched or a square petal where its edges are not matched in the way in Figure 4.61 so that there are more shortage on its tips than we have assumed. We are done with the case that C is an odd blossom. Case B C is an even blossom: We want to show that a square petal of type (p’) has at least two units of shortage at its tips and a tip of a degenerate petal has degree one in F’ fl C. If not, then there is a vertex which has more shortage than we have assumed and we can borrow some shortage from it. Suppose that there exists a square petal U of type (p’) which has less than two  Chapter 4. Square-Free Two-Factors  139  units of shortage at its tips. Clearly, U has at least one unit of shortage at its tips and we have to look for another unit of shortage from another place. To have only shortage one, the vertex b’ in B’ must have degree two in F’ fl C. The tip of the degenerate petal which is split from the same vertex as b’ must have degree 0 in F’ fl C, so we can borrow one unit of shortage from here to use in our sums. Suppose that there exists a degenerate petal of which tip has degree two in F’ fl C. Let b” be the tip and b’ be the vertex split from the same vertex as b”. We want to show that shortage one can be obtained from the square petal U containing b’. Note that b’ must have degree 0 in F’ fl C. The following five cases will be considered depending on what type of a square petal U is (Figure 4.62):  (i)_  (ii  Figure 4.62: In case (i), the tips which is adjacent to b’ have at least shortage one, so U has at least four units of shortage at its tips. Since an isolated square is an odd blossom with one center and a square petal of type (p), this is two more units of shortage than we have  Chapter 4. Square-Free Two-Factors  140  assumed. In case (ii), U has at least four units of shortage at its tips similar to case (i). If U is in an even blossom, then this is two more units of shortage than we have assumed. Suppose that U is in an odd blossom. Then this is three more units of shortage than we have assumed. Even if the one unit of shortage in the center we have assumed is “transferred” to a tip of U, we have still two extra units of shortage. In case (iii), U has at least three units of shortage at its tips. By an argument similar to case (ii), there is at least one extra unit of shortage. In case (iv), U has at least three units of shortage at its tips. This is three more units of shortage than we have assumed. Even if U is in an odd blossom and the two units of shortage in the two centers we have assumed are “transferred” to tips of U, we have still one extra unit of shortage. In case (v), U has at least two units of shortage at b’. If U is in an even blossom, then this is two more units of shortage than we have assumed. Now suppose that U is in an odd blossom. If U has only two units of shortage at its tips, then the other tip of U has degree two in F’ fl C. So the shortage in the center cannot be “transferred” to a tip of U, and we still have one extra unit of shortage. If U has more than two units of shortage at its tips, we have enough extra units of shortage (similar to cases (ii)(iv)).  (==)  Assume that G  =  (V, E) does not have a square-free two-factor. Apply the  Blossom Algorithm to G. At termination, let F be the square-free (0, 2)-factor which we have and S be the set of odd vertices, and let T  =  A U B where A is the set of even  vertices and dummy vertices in pseudovertices and B is the set of dummy odd vertices. Vertices not in S U T are either nondummy vertices in pseudovertices or not in F. Split a vertex v in A into vertices of degree 1 or 2. If there is a blocking square containing v, keep it as a square in GA[V  \ S].  Now split vertices in B as described on p. 131. Note  that every square petal is a blocking square, but not every blocking square is necessarily  Chapter 4. Square-Free Two-Factors  141  a square petal (see Figure 4.65). For every odd vertex v, there exist two matched edges which are incident to v. The matched edges are incident to either an even vertex or a vertex in a pseudovertex. So  21S1  =  Fl  —  IF’I  where F’ is the same as described before. Since there exists a vertex  which is matched by less than two edges,  (41S1  =  21F1  —  21F’I <21V1  —  21V1  >  2F and 21S1 < 2V  \S  —  21F’I  2IF’I). Now it’s enough to show that  21V\ S  —  21F’I  =  C(S,T) + D(S,T).  That is, 21V  \ (S U T)I + >  ](v) 8 deg[V\  +  31B1  —  21F’I  =  D(S,T).  yEA  This is equivalent to show that the equality holds in (4.9) for each component in GT[V\S]. Let C be any component in GT{V  \ 5].  Component C is one of the following: (i) an  isolated vertex, (ii) an isolated edge, (iii) an isolated square, (iv) a number of pseudover tices joined by edges, or (v) a center consisting of vertices not in F. Possibly some component consists of only split vertices. If it’s not case (i), (ii) or (iii), we include this case in case (v). Case A C is type (i): If v is an isolated vertex, v is adjacent to only odd vertices and it is even.(If there is no matched edge which is incident to v, then v is a root at the beginning of the algorithm and so has an even label. If there is one, then its other end w is odd and v gets an even label when w gets an odd label.) The vertex v is in A. So both LHS and RHS of (4.9) are 0 and the equality holds. Case B C is type (ii): If e is an isolated edge, then its ends are in T. (Obviously, an end of e is not nondummy in a pseudovertex. Suppose that a vertex v is not in F. Then there are two matched  Chapter 4. Square-Free Two-Factors  edges incident to  v  and no end of the two matched edges is odd. So  contradicting degGT[V\S] (v) If an end of  e  142  =  degGT[V\s](v)  2,  1. An end of an isolated edge cannot be a vertex not in F.)  is a split vertex of a vertex in B, then e is a degenerate petal and must be  a matched edge by Property (ii) on p. 126. If both ends of e are split vertices of vertices in A, then e must be matched (otherwise e joins two even vertices and a pseudovertex which contains both ends of e must be formed). In any case, e must be matched. So both LHS and RHS of (4.9) are 0. Case C C is type (iii): Without loss of generality, we can assume that no component of G is an isolated square. In this case, it’s trivial that there is no square-free two-factor. In GT[V  \ Sj, only isolated  square are blocking squares and only type (i) in Figure 4.56 will be isolated (others joined at pseudovertices). By the algorithm they are one of the following (Figure 4.63):  (i)  (ii) :dummy odd  Q  :  even  Figure 4.63: In both cases, both LHS and RHS of (4.9) are 2 and the equality holds. Case D C is type (iv): If a pair of pseiidovertices is joined by an edge in GT[V  \ S]  which is not in a blocking  square, they, excluding dummy vertices they contain, belong to one center and the edge must be the stem of one of them. Note that if two vertices in a blocking square belong to one center and another vertex is in a pseudovertex, then we consider the pseudovertex containing the third vertex to be in the center containing the other two vertices. In  143  Chapter 4. Square-Free Two-Factors  Figure 4.64, pseudovertices x, y and z belong to one center.  (‘;  apseudovertex Figure 4.64:  Some blocking squares are not square petals. That is, a blocking square of which two or three vertices are in pseudovertices in one center (Figure 4.65).  one center  a pseudovertex Figure 4.65:  Claim 2 Component C has neither a degenerate petal nor a square petal of type (p’).  Chapter 4. Square-Free Two-Factors  144  Proof. By Property (ii) or (iii) in p.126, an end of an edge in a degenerate petal cannot be nondummy in a pseudovertex. So C could not have any degenerate petal. A square petal of type (p’) must be a blocking square of type (i) in Figure 4.56. In Figure 4.66, for vertex q to be in a pseudovertex, either (q, x) or (z, q) must be the stem of the pseudovertex containing q. So either x or z must be in a pseudovertex. Thus C cannot have a square petal of type (p’). This completes the proof of Claim 2.  Figure 4.66:  Claim 3 Component C is an odd blossom. Proof. By Claim 2, it suffices to show that a center petals. The center  Q  Q  in C has an odd number of  consists of one or more pseudovertices excluding their dummy  vertices if any. Since two pseudovertices are joined by an edge which is the stem of one of them, every pseudovertex in  Q,  except one pseudovertex, has its predecessor in  exceptional pseudovertex is an ancestor of all pseudovertices in the base of  Q.  Q.  Q.  The  Call this pseudovertex  By Property (viii) in p. 126 either the true base of the base of  Q  is one  of the roots, or its stem is a matched edge from an odd vertex, an unmatched edge from an even vertex which might be in a square petal, or an edge from another center or a dummy odd vertex which is in a square petal. By Property (vi) on p. 126, an edge petal is matched, except when it’s the stem of the base of  Q  and an unmatched edge from an even vertex. A square petal which is not  type (q) has two edges incident to a vertex in  Q;  and one of the edges is matched and the  Chapter 4. Square-Free Two-Factors  145  other is unmatched. However, if one of the edges is the stem of the base of Q, both of the edges must be either matched or unmatched. In a square petal of type (q), all four edges are incident to vertices in  Q  and three of them are matched (e.g. (v) in Figure 4.56),  except when one is the stem of the base of  Q  (e.g. (vi) and (vii) in Figure 4.56) or the  square petal is type (viii) in Figure 4.56. In the exceptional cases, two of the edges are matched. A blocking square which is not a square petal has two matched edges incident to a vertex in  Q  (Figure 4.65).  For every pseudovertex o in C, H(o) is a subgraph of C (H(o) is defined in Section 4.8). By Lemma 4.9 and 4.10, every vertex in  Q  except the true base of the base of  Q  has  two incident matched edges in C. The true base has two incident matched edges in C with some exceptions. Exceptional cases are the following: (1) The true base is deficient, (2) The true base is a dummy vertex in a blocking square of type (viii) in Figure 4.56, and (3) The stem of the base is a matched edge from an odd vertex. Let 1 be the number of edge petals of  Q,  1 in  be the number of square petals of  which are not type (q), m 2 be the number of square petals of ii  be the number of blocking squares attached to  21Q1  21F’  ‘  QI  Q  Q  Q  which are type (q), and  which are not square petals. Then  1 + 3m 2 + 2n ± 1. +1+m  By Equation (4.11), 1 + ïni + m , the number of petals of 2  Q,  (4.11)  is odd. This completes the  proof of Claim 3. If vertex v has degree greater than 2 in C and is in a square petal which is not type (q), one edge incident to v is matched, and the other is unmatched, split v into two vertices so that the square petal is separated from the center containing v (Figure 4.67). Let the resulting graph be C’. Let D’ (resp. D”) be the set of vertices in C’ which are split now and in a square petal (resp. not in a square petal, i.e. in a center). Each component in C’ is either one center with only edge petals and square petals of type (q)  146  Chapter 4. Square-Free Two-Factors  r Figure 4.67:  (i)  (ii)  (iii) (iv)  (vi)  (vii)  0  a center  Figure 4.68:  Chapter 4. Square-Free Two-Factors  147  or one of the cases in Figure 4.68. Each case in Figure 4.68 has a square petal of type different from (q) and may have more than one center which are joined by edges in the square petal. Let U be the square petal. Note that each center might have edge petals and square petals of type (q) as well. A vertex v is said to be short if v has degree less than b(v) in (4.10) in F’flC’. Suppose that a component R in C’ consists of one center with only edge petals and square petals of type (q). Then R has one unit of shortage at its base or at the tip of the edge petal which is the stem of the base, one unit of shortage per square petal of type (q) (the same reason as given in the proof of Claim 3), and one unit of shortage per vertex in D”. Now suppose that a component in C’ is one of types in Figure 4.68. For each center, one of the edges in U is the stem of its base. It has two units of shortage at the tips of U, one per square petal of type (q), and one per vertex in D”. So the total shortage in C’ is m + 2n + c + 1 where m is the number of components in C’ with only edge petals and square petals of type (q), n is the number of components in C’ which is one of types in Figure 4.68 and 1 is the number of vertices in D” (also the number of vertices in D’). If we put vertices in D’ and D” back together to recover C, then the shortage at vertices in D’ and D” disappear. So LHS of (4.9) is  in  + 2n + qc  —  1.  Let 1 n  =  the number of components which are type (i),  =  the number of components which are type (ii) and (iv),  3 n  =  the number of components which are type (iii), (v) and (vi), and  4 n  =  the number of components which are type (vii).  Then n  =  1 n 2 + 3 , 4 n and  Chapter 4. Square-Free Two-Factors  c  =  148  4 2 n 3 + m. 2n 3n  Let p° (resp. p’) be the number of square petals of type (p) in which no (resp. one) vertex is split. Similarly for r2 (i  =  0,1,2),  (i  =  0, 1,2), and t (i  =  0, 1,2,3). Then  2+s 1 + 2r 1 + 2s 2+t 1 + 2t 2 + 3t , 3 1+r P 1 n  =  3 + p’+r + 2 , s t  =  2 + p°+r + 1 , s t  3 n  =  r°+s°+t’, and  4 n  =  . 0 t  So LHS of (4.9) is m+2n+q—l  cc+pc+qc—t.  Case E C is type (v): By Claim 4, C is an even blossom and so we have to show that LHS of (4.9) is 2p. Since a vertex in a center is not in F, a square petal of C must be a blocking square of type (i) in Figure 4.56. A square petal of C must be of type (p’) and the edges in the square petal must be matched as in Figure 4.69. There is shortage two at its tips. Each edge petal is matched by Property (v) on p. 126 and a tip of each degenerate petal has degree one in F’ fl C. Since a vertex in a center is not in F, it has degree two in F’ fl C by property (iv) on p. 126. LHS of (4.9) is 2 p and the equality holds. Claim 4 Component C is an even blossom. Proof. We noted already that a square petal of C is type (p’). If C has either a square petal or a degenerate petal, then C is an even blossom. Suppose that C doesn’t have either a square petal or a degenerate petal. Then C has only edge petals. Since a vertex in a center is not in F, it’s matched by two edges both of which are in C by property  Chapter 4. Square-Free Two-Factors  149  p(y)=x X,Z  y  :even  :dummy odd  Figure 4.69: (iv) on p. 126. Each edge petal is matched by Property (v) in p. 126. So each center must have an even number of edge petals. This completes the proof of Claim 4. The proof of Theorem 4.11 is completed. I  Efficiency of the Blossom Algorithm  4.10  In this section, we derive an upper bound on the amount of work done by the Blossom Algorithm in solving the square-free two-factor problem. that the Recover Algorithm runs in  ) 4 O(1V1  In Theorem 4.15 we show  time. Using this theorem it’s shown in  Theorem 4.16 that the amount of work to perform the Blossom Algorithm is bounded by  O(EI  .  ) 5 1V1  time. In the algorithms, we omit some technical details. In this section we  will give rough outlines of each of them so that we can verify our complexity estimates of each. We will describe how to store a pseudovertex when a new pseudovertex is formed. At various times during the Recover Algorithm and the Blossom Algorithm, we have to check whether or not there exists a square which blocks augmentation along some path, e.g. in Step 3 in the Blossom Algorithm. We will give a description of our way to check it.  Chapter 4. Square-Free Two-Factors  150  We assume that we store a pseudovertex in the following way: Make a list of vertices in a new pseudovertex o and keep the cycle and base structure of the pseudovertex o in  Q (0)  (as mentioned in Step 5c in the Blossom Algorithm). Each vertex keeps a list of  pseudovertices containing it. For each vertex in the pseudovertex o, add o to the list of pseudovertices containing it. Here we will describe how to check the existence of a square which blocks augmen tation along some path. At the beginning of the Blossom Algorithm, we find all of the squares in G using the algorithm which is designed by B. Monien [40]. His algorithm takes O(1V1 ) time to find a square in G. If we find a square in G, then delete the four 2 vertices in the square from G and look for another square (in our graph the squares are vertex-disjoint and there is no other square of G containing any of vertices in the square). Repeating this procedure we get all of the squares of G. Since the squares of our graph are vertex-disjoint, there are at most 11 squares. So after O(VI) iterations we get all of the squares of G. It takes  ) 3 O(1V1  time to find all of the squares of G. The following  lemma shows how to check the existence of a square which blocks augmentation along a path and how much work is needed. Lemma 4.12 For a path P appearing during the algorithms, it takes O(1V1 ) time to 2  check whether there is a square S where all its unmatched edges belong to P but none of its matched edges belongs to P. Proof For each unmatched edge e in P, check whether there is a square containing edge  e. This takes 0(IVI) time since the list of all of the squares of G contains at most 0(V) squares. If there is a square containing e, then check whether or not the other three edges in the square are in P. This takes  0(IVI) time since P contains at most 0(IVI) edges (a  path P appearing during the algorithms pass through each vertex at most twice).  Chapter 4. Square-Free Two-Factors  Since there are at most procedure at most  151  O(IVI) unmatched edges in F, we go through the above  O(IVI) times. The total amount of work is bounded by O(IV ). I 2  The following lemmas are needed for proving that the Recover Algorithm runs in polynomial time. Lemma 4.13 The statement made at the end of Step 5 in the Recover Algorithm is true, namely any of the  Uh  ‘s in the new P has not previously been expanded.  Proof. Assume not, i.e. assume that one of the  Uh’S  in the new P which we have now  has been expanded before. Without loss of generality, we can assume that in previous times when we went through Step 5 and modified P, none of  Uh’s  in the new P had  been expanded before. In this proof, pseudovertices except o will be denoted by capital characters. Claim 1 Since pseudovertex o was expanded, edge (z, q) or a pseudovertex in o contain ing (z,q) has been in P. Proof. Assume that neither edge (z, q) nor a pseudovertex in o containing (z, q) had been in P and later (z, q) itself or a pseudovertex containing (z, q) was added to P. That is one of case (i) or (iv)’-.’(vi) in Figure 4.45 occurred, and (z, q) or a pseudovertex containing (z, q) was added to P. Let Uabcd be the square and B be the pseudovertex containing a, b, c and d. Let U be the smallest pseudovertex in o such that U contains the edge (z, q) and the intersection of U and P is nonempty where P is the P before modifying P by Dabcd. Since both U and B contain the edge (z, q), one of the following cases must occur: (A) U and B are the same pseudovertex, (B) B is inside U, (C) U is inside B. (A) U and B are the same pseudovertex: Suppose that edge (a, b) was added to F before (z, q). When the edge (a, b) was  Chapter 4. Square-Free Two-Factors  added to  ,  152  the edge (c, d) must be in a pseudovertex (otherwise Dabcd was a  blocking square during the Blossom Algorithm). When (a, b) was added to  ‘,  a  pseudovertex containing a, b, c and d was formed, but not containing the edge (z, q). This contradicts the assumption that B and U are the same pseudovertex.  Similarly we arrive at a contradiction when edge (z, q) was added to .T before (a, b). (B) B is inside U: Any pseudovertex or any vertex in B was not in P when the modification of P by flabcd was made (since U is the smallest pseudovertex such that U contains the edge (z, q) and the intersection of U and P is nonempty when the modification of P by Dabcd was made). So one of case (i) or (iv)(vi) in Figure 4.45 cannot occur by Elabcd.  (C) U is inside B: Then one of the following cases must occur: (1) B and o are the same pseudovertex, (2) B is inside o, (3) o is inside B. If B and o are the same pseudovertex or B is inside o, then we arrive a contradiction by an argument similar to case (A). Suppose that o is inside B. Then one of the cases in Figure 4.70 must occur. If it’s case (i), then we arrive at a contradiction by an argument similar to case (A). Suppose that it’s case (ii). By the assumption we made at the beginning of this proof, the modification of P by Dabcd was made before o was expanded. So we arrive at a contradiction that the modification is made after o was expanded. This completes the proof of Claim 1. Claim 2 The current modification of P (i.e. by Dxyzq) cannot occur as in case (ii) or (iii) in Figure 445.  Chapter 4. Square-Free Two-Factors  153  (ii)  (I)  S  I  I  I  /  I  I  ,  I  I  I  B  I  /  I  B /  /  u  /  u /  /  / —  S /  I I  I  / I  —  — —  Figure 4.70: Proof. Since uh (1  d  was  expanded before (z, q) appeared in P, either (z, q) is in one  h) or u was not in P. First suppose that (z, q) is in one  d  (1  d 1 ‘ 1  d < h). Since  the edge (z, q) was added to 1 after a pseudovertex containing x and y was formed, (z, q) is not in P. So the edge (z, q) cannot be an ancestor of u. When we expanded  ud,  (z, q) cannot appear in P, so this contradicts Claim 1. Now suppose that u was not in P. Since u was added to P later, one of case (i) or (iv)(vi) made the change in P. Let EJabcd be the square and U be the pseudovertex containing a, b, c and d. Then U must contain u. We can classify it into the following cases: (A) U and o are the same pseudovertex, (B) U is inside o, (C) o is inside U. (A) U and o are the same pseudovertex: By an argument similar to case (A) in Claim 1, we arrive at a contradiction. (B) U is inside  0:  Chapter 4. Square-Free Two-Factors  154  Since U contains u, U must be u . The pseudovertex U was not in F, hence Dabcd 2 could not add u to P. (C) o is inside U: It’s one of the cases in Figure 4.70 except that B is replaced by U and edge (z, q) may not be in a pseudovertex in o. So we arrive at a contradiction. This completes the proof of Claim 2. By Claim 2, the current modification of P must be one of case (i) or (iv)-1(vi). Then Uh  was in P before and later it was removed from P. So one of situations in Figure 4.45  and 4.49 occurred and uh was removed from P. Let Iabcd be the square which made the change in P and B be the pseudovertex containing a, b, c and d. Then Since  uh  is in B and o, one of the following cases must occur: (A) B and  o  ‘uh  is in B.  are the same  pseudovertex, (B) B is inside o, (C) o is inside B. Case A B and o are the same pseudovertex: We classify it into the following two cases (Figure 4.71): (a) It’s case (a) in Figure 4.71: If edge (a, b) was added to .F before containing a, b, c and d, but not edge  (z, (z,  q), then we must form a pseudovertex  q), hence contradicting that B and o are  the same pseudovertex. Similarly we arrive at a contradiction when edge  (z,  q) was  added to S before (a, b). (b) It’s case (b) in Figure 4.71: If the pseudovertex U was formed before  (z,  q) was added to F, then a pseudovertex  was formed containing a, b, c and d, but not edge  (z,  q). If  (z,  q) was added to  F before the pseudovertex U was formed, then the pseudovertex U must not be inside o.  Chapter 4. Square-Free Two-Factors  155  (a)  (b)  S..  S S  /  S  /  —  /  /  U  \  /  /  / /  -7  S  Figure 4.71: Case B B is inside  0:  The pseudovertex B is of P which is in  uh  ‘uh  or inside  ‘uh.  So Dabcd affected only part of uh and the portion  must not be removed from P.  Case C o is inside B: Suppose that no edges of Dabcd are in o. Then the portion of P which is in o either was removed from P or remained in P when a change in P is made by Oabcd. So it’s not possible that (z, q) is in P and  Uh  is removed from P. So at least one of edges of Ilabcd  is in o. We will classify it into the following cases (Figure 4.72): (a) It’s case (a) in Figure 4.72: By the assumption we made at the beginning of this proof, o must not have been expanded before edge (a, b) appears in P. So uh has not been expanded either.  Chapter 4. Square-Free Two-Factors  (a)  156  (c)  (b)  B /  /  0 I’  \  0  —  -ç  \ I  I I  I I  I  (e)  (d) _•_%  ___—  I I  B  I  B /  / /0  0  /  \  / —  I  I I  I  I I I /  —  //  /  Figure 4.72:  ‘-0-’  Chapter 4. Square-Free Two-Factors  157  (b) It’s case (b) in Figure 4.72: If edge (z, q) was added to F before (a, b), then there is a pseudovertex containing x, y, z and q, but not edge (a, b), a contradiction. Similarly we arrive at a contradiction when edge (a, b) was added to F before (z, q). (c) It’s case (c) in Figure 4.72: A change in P was made by Flabcd before any pseudovertex in o was expanded (since (a, d) is not in a pseudovertex in o). (d) It’s case (d) or (e) in Figure 4.72: By an argument similar to Claim 2, we arrive at a contradiction. The proof of Lemma 4.13 is completed. I Lemma 4.14 During the Recover Algorithm, a pseudovertex can be expanded at most  O(IVI) times. Proof. Suppose that a pseudovertex u has been expanded more than once during the Re cover Algorithm. The possible places during the Recover algorithm where a pseudovertex is reshrunk are in Steps 5 and 6. In Lemma 4.13 it is shown that in Step 5 pseudovertices uhs  have not been expanded before. Hence Step 6 is the only place where a pseudovertex  is reshrunk. If u is reshrunk in Step 6, u is the last pseudovertex which was expanded and will be the next pseudovertex to be expanded. The pseudovertex u will be expanded and shrunk successively until there is no more square of the types in Figure 4.49. If Dxyzq appears in P and P is modified to avoid Dxyzq once, then LJxyzq will not appear again. If edge (z, y) is removed from P, then (z, q) is removed from P also. Since there are at most  O(IVI) squares in G,  u can be expanded and shrunk at most  Theorem 4.15 The Recover Algorithm runs in  ) 4 O(1V1  time.  O(IVI) times. I  Chapter 4. Square-Free Two-Factors  158  Proof. First we will analyze how much work is needed for each step. Note that Steps 2,—.d6 may be performed more than once. The analysis below is for performing each of them once. (i) Step 1 takes  O(IVI) time:  Finding the directed path P, 1 takes (ii) Step 2 takes  O(IVI) time.  O(IVI) time:  Changing P takes O(IVI) time. (iii) Step 3 takes  OGVI) time:  At the beginning of the step we search for a pseudovertex takes  ‘Uk  to be expanded. It  O(IVI) time since there are at most O(IVI) pseudovertices. Changing P takes  O(IVI) time. (iv) Step 4 takes O(1V1 ) time: 2 We have to compare a pair of edges in P to check whether they are the same edge. This takes  ) 2 O(1V1  (v) Step 5 takes  time. Modifying P takes 0(1) time.  ) 2 O(1V1  time:  At the beginning of the step, it’s checked whether there exists a square described. We can use the same method as in Lemma 4.12 to find such a square. So this takes  ) 2 O(1V1  time. Finding the pseudovertex o containing all of the four vertices x, y,  z and q takes  0(IVI)  time. In the paragraph below we explain how we get this  bound. It takes O(IVI) time to modify P. Here we assume that we find the pseudovertex o in the following way: Scan each pseudovertex in the list of pseudovertices containing x and check whether it contains all of y, z and q. If we find one, keep it and scan for another pseudovertex. If another pseudovertex containing all of y, z and q is found, then between the pseudovertex  Chapter 4. Square-Free Two-Factors  159  we have and the one we just found we find one is inside the other and we keep the smaller one. Scan for another pseudovertex. By repeating this procedure, we will find the pseudovertex o. Since checking whether a pseudovertex contains all of y, z and q takes (vi) Step 6 takes  0(IVI) time, it takes 0(1 Vt ) time to find the pseudovertex o. 2  0(1 Vt ) time: 2  Similar analysis as Step 5 can be applied. (vii) Step 7 takes 0(1) time: (viii) Step 8 takes 0(1) time: An expansion procedure of a pseudovertex is either Steps 2.2 and 46 or Steps 3 and 46 (sometime Step 7 is included). It takes  0(1 Vt ) time to expand a pseudovertex. By 2  Lemma 4.14 each pseudovertex is expanded at most  0(IVI) times. Since there are at  most  0(IVI) pseudovertices, an expansion procedure of a pseudovertex is performed at  most  ) times. Steps 1 and 8 are performed only once in the course of the algorithm. 2 0(1 Vj  So the algorithm runs in  0(1 Vt ) time. • 4  Now we will derive an upper bound on the amount of work which is needed to perform the Blossom Algorithm. Theorem 4.16 the Blossom Algorithm runs in  0(IEI 1V1 ) time. 5 .  Proof First we will analyze how much amount of work is needed to perform each step. (i) Step 1 takes It takes  0(IEI) time:  0(IEI)  time to initialize the sets E, E—, E*, and CUE. It takes 0(IVI)  time to let all of deficient vertices roots of F. (ii) Step 2 takes  0(IEI) time:  To select an edge, we might scan all of the edges in E+ U E*.  Chapter 4. Square-Free Two-Factors  (iii) Step 3 takes  ) 2 O(1V1  160  time:  It takes  O(IVI) time to get the path P (resp. Pm). By Lemma 4.12, it takes  ) 2 O(Iv  time to check the existence of a square described. Since at most four paths  are checked, the total amount of work is needed in this step is O(lV ) time. 2 (iv) Step 4 takes  ) 2 O(1V1  time:  Step 4.1 (resp. Step 4.2, Step 4.3, Step 4.5, or Step 4.6) takes 0(1) time. Step 4.4 takes  ) 2 O(1V1  time by an analysis similar to Step 3 except that in Step 4.4 the  vertex b must be found. Finding b takes O(VI ) time since b can be found by 2 comparing each pair of a vertex in P and one in P. (v) Step 5 takes  ) 3 0(1V1  (a) Step 5a takes For at most  time:  ) 3 O(1V1  time:  0(IVI) paths, it’s checked whether there exists a square of the  type described. (b) Step 5b takes  0(IVI) time:  For each square of the types in Figure 4.36, the amount of work is 0(1). The number of the squares is at most O(IV). (c) Step Sc takes O(IVI) time: At the beginning of this section, we give a description how to store a new pseudovertex o. Making a list of vertices in o takes  0(IVD time. For each  vertex in o, adding o to the list of pseudovertices containing it takes 0(1) time. So the total amount of work needed in this step is bounded by (d) Step Sd takes  0(IV).  0(IEI) time:  For each dummy vertex x, it’s checked whether there exists an edge or edges which turn x into a nondummy vertex. Each edge can be checked at most  Chapter 4. Square-Free Two-Factors  161  twice for each of its ends. (e) Step 5e takes  O(IEI) time:  Each edge of which one end is in 0 is scanned, which takes 0(IEI) time. Each pseudovertex is scanned to know whether or not it’s attached to 0, which takes  0(IVD time.  (vi) Step 6 takes  ) 4 O(lVi  time:  The Recover Algorithm takes (vii) Step 7 takes For each e  ) 4 O(1V1  time by Theorem 4.15.  0(IEI IVl) time:  e CUE, the work is as much as Step 3 (which takes O(1V1 ) time). Since 2  CUE ç E, the total amount of work needed in this step is bounded by  ). 2 O(iEi.lVi  An augmentation occurs in Step 6. The deficiency of F is decreased by two at the start and end vertices of an augmenting walk each time when an augmentation occurs. The deficiency of any square-free (0,2)-factor F can be decreased by at most can be performed at most  lvi  2iVI. Step 6  times. Apart from the first time, Step 1 is performed oily  after we get a new F, i.e. after Step 6 is performed. Step 1 is performed as many times as Step 6. Now we will derive how much work is needed between Step 1 and Step 6  -  we  will count how many times each of Steps 2’5 is performed between Step 1 and Step 6. Between Step 1 and 6, each vertex can change label at most 0(1) times (there are at most five labels: odd, dummy odd, even, dummy in a pseudovertex, or nondummy in a pseudovertex) and a pseudovertex can be formed at most  0(IVI) times. So between  Step 1 and 6 changes in .F, i.e. changing the label of a vertex or forming a pseudovertex, can be made at most O(iVi) times. How much work is needed to make a change in F? We will count how many times Steps 25 are performed to make a change in F. In Step 2 choose an edge in E+ U E* from an even vertex or a pseudovertex to a non-odd vertex  Chapter 4. Square-Free Two-Factors  162  (which may change F) and go through Steps 3—5. Sometime some steps are skipped. For example if in Step 5e we find an unmatched edge from a vertex in pseudovertex o to an even vertex or another pseudovertex, then go to Step 3.2. In this case, Step 2 is skipped. But here we assume that we start from Step 2 and each step between Steps 2—5 is performed. After going through Steps 3—’5, either a change in F is made or we reach a conclusion that the edge cannot change F. In the latter case, we store it into set CUE and go to Step 2 to look for another edge which may change F. If each edge in E U E from an even vertex or a pseudovertex to a non-odd vertex is tested and no change in F occurs, then the algorithm stops (there is no square-free two-factor). For each change in F, Steps 2—’5 can be performed at most O(EI) times. Since it takes  ) 3 O(1V1  time to  ). 3 1v1  perform Steps 25, the amount of work for each change in F is bounded by O(IEI.  As mentioned, changes can be made in F between Steps 1 and 6 at most O(VI) times. So the work load from Step 1 to Step 6 (including Steps 1 and 6) is bounded by O(IE V) .  time. The loop from Step 1 to Step 6 can be performed at most O(IVI) times and Step 7 is performed at most once in the course of the Blossom Algorithm. The total amount of work in the course of the Blossom Algorithm is bounded by O(IEI 4.11  ). I 5 V  Further Study  In Section 4.2, our augmenting walk was described it is alternating in operations between -  adding and subtracting edges, and the symmetric difference between any of its initial segment of even length and F is square-free. So we concern ourselves with squares being created locally. As noted in Section 4.1, an augmenting walk having such nice properties doesn’t exist for a L-free two-factor if L  {3, 4}. Let G be the graph in Figure 4.73  (i) and let F be the (0, 2)-factor which consists of wavy edges. Let F’ be the subgraph  Chapter 4. Square-Free Two-Factors  163  which consists of wavy edges in Figure 4.73 (ii). We can easily see that F’ is the only pentagon-free two-factor of G. The symmetric difference F/IF’ is: ,v 1 (v ) ,v 7 (v ) ,8 ,4 ,v 3 (v ) ,5 ,v 4 (v ) ,6 ,v 5 (v ) , { (vo,vi), 7 ,v 6 (v ), (v 3 , ), 9 10 (vio, vu), (v v , ), 11 12 (v v ,v 12 )}. 9  Let P  —  8 ) {(vo,vi),(vi,v , 7 ) ,(v }, v  C  =  3 {(v 4 5 ) , 6 ) ,(v v and },  C’  =  11 , {(v ) 9 ,v ),(v 12 ),(vii,v vio),(vio,v }.  We cannot construct an alternating walk which includes F, C and C’ as in the case of square-free two-factors. If we replace the pentagons v 6 and v 3 2 1 0 9 8 7 1 2 by any other n-gon (n 3  5),  we reach the same conclusion that there is no such augmenting walk as in the case of square-free two-factors. The existence of a nice augmenting walk of an L-free two-factor for L  C {3, 4} as compared with the other cases leads us to think that the problem of  finding a square-free two-factor is in P. Also we believe that if a polynomial algorithm for finding a square-free two-factor is obtained then one for {triangle, square}-free twofactors must also exist. In our algorithms, we use the assumption of squares being vertex-disjoint in G. For example in Step 4.3 in the Blossom Algorithm, if a dummy odd vertex v is reached by an edge e in E+, then v becomes odd. Since squares of G are vertex-disjoint, there is no square containing e and so v can be odd. Another place where the property of squares being vertex-disjoint is used is in Step 5e in the Blossom Algorithm  -  the cases  in Theorem 4.6. We also used the property in some other places. In the algorithm for triangle-free two-factors by D. Hartvigsen [31], if two blocking triangles share the same  Chapter 4. Square-Free Two-Factors  (i)  (ii)  Figure 4.73:  164  Chapter 4. Square-Free Two-Factors  165  edge, then one of the triangles may become no longer a blocking square. Probably this will be possible for the case of square-free, but then we expect the algorithm will be quite complicated. We hope that in future we can either extend our algorithm to solve the problem for a general graph (i.e. the squares of a graph don’t need to be vertex-disjoint) or get an idea of another technique to obtain a simpler algorithm.  Bibliography  [1] R. P. Anstee, Properties of a class of(0, 1)-matrices covering a given matrix, Canad. J. Math. 34, 1982, 438-453. [2] R. P. Anstee, The network flows approach for matrices with given row and column sums, Discrete Math. 44, 1983, 125-138. [3] R. P. Anstee, An algorithmic proof of Thtte ‘s f-factor theorem, J. Algorithms 6, 1985, 112-131. [4] R. P. Anstee, Simplified existence theorems for (g, 27, 1990, 29-38.  f) -factors,  Discrete Appi. Math.  [5] R. P. Anstee, A polynomial algorithm for b-matchings: An alternative approach, Information Processing Letters 24, 1987, 153-157. [6] R. P. Anstee, Minimum vertex weighted deficiency of (g, f)-factors: A greedy algo rithm, Discrete Appl. Math. 44, 1993, 247-260. [7] C. Berge, Two theorems in graph theory, Proc. Natl. Acad. Sci. U.s., 43, 1957, 842-844. [8] J. Bermond and M. Las Vergnas, Regular factors in nearly regular graphs, Discrete Mathematics 50, 1980, 9-13. [9] R. A. Brualdi, Existence theorem for infinite integral matrices, Mathematika 17, 1970, 91-97. [10] R. A. Brualdi, Matrices of 0’s and l’s with total support, J. Combinatorial Theory, Ser. A 28, 1980, 249-256. [11] R. A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra and Its Applications 33, 1980, 159-231. [12] R. A. Brualdi and T. S. Michael, The class of matrices of zeros, ones, and twos with prescribed row and column sums, Linear Algebra and Its applications 114/115, 1989, 181-198. [13] W. Chen, Integral matrices with given row and column sums, to appear in J. Com binatorial Theory, Ser. A 61, 1992, 153-172. 166  Bibliography  167  [14] G. Cornuéjols and W. Pulleyblank, A matching problem with side conditions, Dis crete Math. 29, 1980, 135-159. [15] G. Cornuéjols, General factors of graphs, J. Combinatorial theory B45, 1988, 185198. [16] J. Edmonds, Paths, trees and flowers, Canad. J. Math. 17, 1965, 449-467. [17] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards Sect. 69B, 1965, 125-130. [18] J. Edmonds and E. L. Johnson, Mathing: A well-solved class of Integer Linear Programs, Combinatorial Structure and Their Applications, R. Guy (editor), Gordon and Beach, New York, 1970, 89-92. [19] Y. Egawa, H. Enomoto and A. Saito, Factors and induced subgraphs, Discrete Math. 68, 1988, no. 2-3, 179-189. [20] 5. Even and 0. Kariv, An O(n ) Algorithm for Maximum Matching in General 25 Graphs, Proc. Sixteenth Annual Symp. on Foundations of Computer Science, Berke ley, California: IEEE, 1975, 100-112. [21] D. R. Fulkerson, A network flow feasibility theorem and combinatorial applications, Can. J. Math. 11, 1959, 440-451. [22] D. R. Fulkerson, Zero-one matrices with zero trace, Pacific J. Math. 10, 1960, 831836. [23] L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, 1962. [24] D. R. Fulkerson, A. J. Hoffman and M. H. McAndrew, Some properties of graphs with multiple edges, Canad. J. Math. 17, 1965, 166-177. [25] D. R. Fulkerson and H. J. Ryser, Widths and heights of (0, 1)-matrices, Canad. J. Math. 13, 1961, 239-255. [26] D. R. Fulkerson and H. J. Ryser, Multiplicities and minimal widths for (0, 1)matrices, Canad. J. Math. 14, 1962, 498-508. [27] H. N. Gabow, An efficient technique for degree constrained subgraphs and bidirected network flow problems, Proc. 15th Annual ACM Symposium on Theory of Comput ing, 1983, 448-456.  Bibliography  168  [28] H. N. Gabow, Data Structures for Weighted Matching and Nearest Common An cestors with Linking, Proc. First Annual ACM-SIAM Symposium on Discrete Algo rithms, 1990, 434-443. [29] D. Gale, A theorem on flows in networks, Pacific J. Math. 7, 1957, 1073-1082. [30] M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman and Co. San Francisco, 1979. [31] D. B. Hartvigsen, Extensions of Matching Theory, Ph.D. Thesis, Carnegie-Mellon University, 1984. [32] P. Hell, D. Kirkpatrick, J. Kratochvfl, and I. Kif, On Restricted Two-Factors, SIAM J. Disc. Math. vol. 1, No. 4, 1988, 472-484. [33] M. Las Vergnas, An extension of Tutte’s 1-factor Theorem, Discrete Math 23, 1978, 241-155. [34] L. Lovász, Subgraphs with prescribed valencies, J. Combinatorial Th. 8, 1970, 391416. [35] L. Lovsz, The factorization of graphs, Combinatorial Structures and Their Appli cations, Gordon & Breach, New York, 1970, 243-246. [36] L. Lovász, The factorization of graphs, II, Acta Math Acad. Sci. Hungar. 23, 1972, 223-246. [37] L. Lovász and M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986. [38] A. B. Marsh, III. Matching algorithms, Ph.D. Thesis, The Johns Hokins Univ., 1979. [39] L. Mirsky, Combinatorial Theorems and Integral Matrices, J. Combinatorial Theory 5, 1968, 30-44. [40] B. Monien, The Complexity of Determining a Shortest Cycle of Even Length, Com puting 31, 1983, 355-369. [41] S. Micali and V. V. Vazirani, an O(/j7F. ED Algorithm for Finding Maximum Matching in General Graphs, Proc. Twenty-first Annual Symposium on the Foun dations of Computer Science, Long Beach, California: IEEE, 1980, 17-27. [42] M. W. Padberg and M. R. Rao, Odd Minimum cut-sets and b-matchings, Math. Oper. Res. Vol. 7, No.1, 1982, 67-80. [43] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:Algorithms and Complexity, Prentice-Hall mc, 1982.  Bibliography  169  [44] W. R. Pulleyblank, Faces of matching polyhedra, Ph.D. Thesis, Department of Corn binatorics and Optimization, University of Waterloo, 1973. [45] H. J. Ryser, Combinatorial properties of matrices of zeros and ones, Can. J. Math. 9, 1957, 371-377. [46] H. J. Ryser, Matrices of zeros and ones, Bull. Amer. Math. Soc. 66, 1960, 442-464. [47] H. J. Ryser, Combinatorial Mathematics, Carus Math. Monographs No. 14, Math. Assoc. Amer., 1963. [48] E. Snapper, Group characters and nonnegative integral matrices, J. Algebra 19, 1971, 520-535. [49] E. Tardös, A strongly polynomial minimum cost circulation algorithm, Combinator ica 15, 1985, 247-255. [50] W. T. Tutte, The factorization of linear graphs, Journal of the London Mathematical Society 22, 1947, 107-111. [51] W. T. Tutte, The factors of graphs, Canad. J. Math. 4, 1952, 314-328. [52] W. T. Tutte, A short proof of the factor theorem for finite graphs, Canad. J. Math. 6, 1954, 347-352. [53] W. T. Tutte, The subgraph problem, Annals of Discrete Mathematics 3, 1978, 289295. [54] 0. Vornberger, Complexity of Path Problems in Graphs, Ph.D. Thesis, Universität GH-Paderborn, 1979.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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-0079982/manifest

Comment

Related Items