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

MATCHING THEORY: SUBGRAPHS WITH DEGREE CONSTRAINTSAND OTHER PROPERTIESByYunsun NamB. Sc. (Mathematics) Ewha University, Korea, 1985M. Sc. (Mathematics) Ewha University, Korea, 1987A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIESDEPARTMENT OF MATHEMATICS (INSTITUTE OF APPLIED MATHEMATICS)We accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAApril 1994© Yunsun Nam, 1994In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that errnission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood thatcopying orpublication of this thesis for financial gain shall not be allowed withoutmy writtenpermission.(Signature)______________Department of t4O’tAKThe University of British ColumbiaVancouver, CanadaDateDE-E (2188)AbstractIn this thesis, three generalizations of the matching problem are considered.The first problem is the existence of matrices with given row and column sums. Thisproblem can be interpreted as the f-factor problem of a bipartite graph. The well-knownexistence theorem follows from maxfiow-mincut theorem, but it contains an exponentialnumber (in the number of rows) of inequalities. We generalize the Gale-Ryser theoremand obtain some conditions under which this exponential number of inequalities can bereduced to a polynomial number of inequalities.The second problem is the general factor problem. Let G = (V, E) be a multigraph.An arbitrary subset BL, of {O, 1,2,. . . , deg(v)} is assigned to each vertex v E V. Wecall a B-factor a spanning subgraph F of G such that deg (v) e B for every vertexv e V. A set B is said to have a gap of length p 1 if there exists an integer k suchthat k+ 1,.•.,k+p B, and yet k,k+p+ 1 E B. It’s known that the problemis NP-complete if we allow gaps of length more than one. We extend the algorithm ofCornuéjols for simple graphs and obtain a strongly polynomial algorithm for finding aB-factor when each B doesn’t have a gap of length 2 or more. A new augmenting walkthat need not alternate is introduced.The third problem is the square-free two-factor problem. A square-free two-factor isa two-factor in which the cycles don’t have length 4, i.e. are not squares. We obtain anaugmenting path theorem like Berge’s augmenting path theorem for a 1-matching. Alsowe obtain a polynomial algorithm for finding a square-free two-factor when the squaresof G are vertex-disjoint.IITable of ContentsAbstractTable of Contents iiiList of Figures vAcknowledgement ix1 Introduction 11.1 Basic Graph Theory Terminology 11.2 Introduction to the Matching Problem . . . 21.3 Three Problems in this Thesis 42 Integral Matrices with Given Row and Column Sum Vectors 102.1 Introduction 102.2 Theorems 122.3 The Proof of Theorem 2.4 162.4 Further Study 243 General Factor Problem 253.1 Introduction 253.2 Augmenting Walks 273.3 General Factor Problem with Parity Conditions . . . 283.4 Algorithm for General Factors with Parity Conditions 383.5 General Factor Problem Allowing Gaps of Length 1 . 443.6 Further Study 461114 Square-Free Two-Factors 474.1 Introduction 474.2 A Berge-type Theorem 504.3 A Preview of the Blossom Algorithm 674.4 The Blossom Algorithm 814.5 Some notes for the Recover Algorithm 964.6 The Recover Algorithm 1014.7 The validity of the Recover Algorithm 1174.8 The structure of .F at the end of the Blossom Algorithm 1254.9 A Tutte-type Theorem 1304.10 Efficiency of the Blossom Algorithm 1494.11 Further Study 162Bibliography 166ivList of Figures3.1 . 293.2. 303.3 . 323.4 354.1 514.2 514.3 534.4 554.5 564.6 574.7 584.8 594.9 604.10 614.11 614.12 644.13 654.14 654.15 664.16 674.17 69V4.18 A forest F . 714.19 724.20 734.21 754.22 754.23 774.24 774.25 784.26 794.27 804.28 814.29 844.30 844.31 864.32 864.33 884.34 894.35 894.36 914.37 944.38 954.39 994.40 1004.41 1054.42 1064.43 107vi4.44. 1084.45. 1094.46 1104.47 1114.48 1134.49 1144.50 1164.51 1174.52 1204.53 1234.54 1244.55 1254.56 1284.57 1304.58 A blossom tree 1324.59 1334.60 1344.61 1374.62 1394.63 1424.64 1434.65 1434.66 1444.67 1464.68 1464.69 149vii4.70 . 1534.71 . 1554.72 1564.73 164viiiAcknowledgementMy appreciation is due to many people who have substained me in this endeavour. FirstI would like to thank my supervisor, Prof. Richard Anstee. I cannot express enough mygratitude to him. Without his patient guidance and encouragement, this thesis could nothave been completed. I owe much to his insightful questions and suggestions. I want tothank 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 andideas. I would like to thank Prof. Kee Lam for his caring support while I have been atUBC.Finally, I would like to thank my dad, Sangjoon, and my mom, Taemin, and all themembers of my family for their caring, support and much more.ixChapter 1Introduction1.1 Basic Graph Theory TerminologyIn this section, some basic terminology and notations in graph theory are given. If thereader is familiar with graph theory, then he/she can skip this section. Whenever we usesome 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 ofunordered pairs of elements of V called edges. If an edge e consists of two vertices v andw, then we denote e = (v, w) or (w, v) and say that e joins v and w. Also v and w areend vertices of e and it is said that e is incident with v. If there is an edge joining twovertices v and w, then it is said that v and w are adjacent. If an edge e joins the samevertex, 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 ofvertices. A graph G is a multigraph if it has a loop or more than one edge joining thesame pair of vertices. We call the number of copies of edge e the multiplicity of e. In agraph G, a vertex v is said to have degree k (written deg (v) = k) if there are exactly kedges 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 subgraphof G is a subgraph F of G with F(V) = V. Suppose that V’ is a subset of V. Thesubgraph of G whose vertex set is V’ and whose edge set is the set of those edges of G1Chapter 1. Introduction 2that have both end vertices in V’ is called the subgraph of G induced by V’ and is denotedby G[V’]; we say that G[V’j is an induced subgraph of G.A walk in G is a sequence W =v0e12 the terms of which are alternatelyvertices and edges such that, for 1 i n, e joins two vertices v_1 and v. The integern is the length of W. If the edges e1,e2,.. , e,-, of a walk W are distinct, W is called atrail. If, in addition, the vertices v0,v1,••• , v, of W are distinct, W is called a path.We use the notation A/.B to denote the symmetric difference between A and B, thatis A1B = (A \ B) U (B \ A).We will define here some terminology in complexity theory. An algorithm is pseudo-polynomial if it runs in polynomial time in the numbers in the input, not the size of theinput. Since the size of a number is its logarithm, a pseudo-polynomial algorithm maynot be a polynomial algorithm. We say that an algorithm is strongly polynomial if (i) itruns in a polynomial number of arithmatic operations in the number of numbers in theinput (not in the size of the input), and (ii) all numbers generated by the algorithm havea number of bits which is bounded by a polynomial in the size of the input. Hence astrongly polynomial algorithm is a polynomial algorithm.1.2 Introduction to the Matching ProblemIn this section, some problems which are generalizations of the matching problem areintroduced. The matching problem asks whether there exists a spanning subgraph F ofG of which each vertex has degree one. We call such a subgraph a 1-matching. Theproblem is well studied. There are a number of polynomial algorithms for finding a1-matching [16] [20] [28] [41] and there is an existence theorem for a 1-matching, the socalled 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 factorChapter 1. Introduction 3problem with side conditions, the b-matching problem, etc. Below, we will introduce thedefinitions. 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 theyrun in polynomial time. In [37], it’s written “It is fun to consider the matching problemand those problems related to it. They are of an attractive level of difficulty. On theother hand, most of them are solvable problems, but to solve them certainly requiresnon-trivial methods.”The (g, f)-factor problem is: Given integeral vectors g = (g(v) : v E V) and f =(f(v) : v V) such that g(v) f(v). Does there exist a (g, f)-factor, that is, aspanning subgraph F of G such that g(v) deg(v) < f(v) for each vertex v e V? Ifg f, then we call F an f-factor. Chapter 2 considers f-factors of bipartite graphsand cases where the existence theorem is “easy”. There are polynomial algorithms whichfind 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 e V}, and looking for a B-factor,that is a spanning subgraph F such that deg(v) e B for all v e V. This problem isstudied in Chapter 3.Another generalization of the matching problem is the factor problem with side conditions [14] [32]. The existence problem for two-factors in which the cycles are restricted tohaving 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 generalization. Each edge e of E is assigned a cost Ce. Let b = (b1,b2,• , by1) be a vector ofnon-negative integers. A b-matching is an assignment of positive integer weights Xe toChapter 1. Introduction 4the edges such that, for each vertex v, the sum of the weights on edges incident with vis no more than b. The b-matching problem then consists of looking for a b-matchingof maximum cost where the cost is the weighted sum of the costs on the edges, i.e.E{cexele E E}. This is studied in [5], [42] and [44].13 Three Problems in this ThesisIn this thesis, three generalizations of the matching problem are considered. These appearin 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 notfamiliar with it, then he/she can refer to [16] and [37]. The unifying theme is degreeconstrained subgraphs and the augmenting walks to obtain them.Our contribution in this thesis are many. We generalize in an attractive way theexistence theorem of Gale and Ryser (Theorem 2.2) for (0,1)-matrices of given row andcolumn sums. We generalize further, obtaining a rather nice result that in effect says, inthe maxflow-mincut theorem for this problem, that we can restrict ourselves to looking ata polynomial number of cuts. We extend the algorithm of Cornuéjols for the general factorproblem [15] to the case of multigraphs and obtain a strongly polynomial algorithm. Weintroduce an augmenting walk which does not alternate in the usual way but is naturalfor this problem. Finally we tackle the problem of looking for a subgraph of a graphG that consists of vertex disjoint cycles (including all vertices) but having no cycle oflength 4. We only succeed in obtaining a polynomial algorithm for the case where thesquares 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 witha 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 theChapter 1. Introduction 5knowledge base for Combinatorial Optimization.In Chapter 2, we study the existence problem of matrices with given row and columnsums. This problem is equivalent to the f-factor problem of a bipartite (multi)graph.Let m and n be positive integers, and let R = (ri,... ,Tm) and S = ,s) be nonnegative integral vectors with r1 + + rm = s1 + + s,. Let Q = (qjj) be an ni x nnon-negative integral matrix. Let A = (a) be an m x ii non-negative integral matrixwith row sum vector R and column sum vector S such that qjj for all i and j,denoted A Q. Interpreting Q as a bipartite adjacency matrix of a bipartite multigraphG (vertex i of the first part is joined to vertex j of the second part by qjj edges); wesee that A corresponds to a subgraph of G with vertex i of the first part having degreer and vertex j of the second part having degree sj. The well known existence theoremfor a matrix A follows from the maxfiow-mincut theorem. The conditions consist of anexponential number of inequalities, i.e. an exponential number of cuts. D. Gale [29] andH. J. Ryser [45] proved that we can reduce the exponential number of inequalities to alinear 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 underwhich 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 toget the result. The Gale-Ryser Theorem has been generalized by many people includingD. 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 statementsimple. Perhaps this result will find some application in the way that the Gale-RyserTheorem has found applications, e.g. to Latin squares. We were surprised to find sucha 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 kindof hierarchy: under weaker and weaker conditions, more and more inequalities (still aChapter .1. Introduction 6polynomial in n) are involved in a necessary and sufficient condition for the existence ofa matrix A. This is the first result of this type and it was for this reason the result wasobtained.In Chapter 3, we study the general factor problem. We have given the definitionof the problem in Section 1.2, but we will give here. For each vertex v e V, let Bbe an arbitrary subset of {O, 1,—• , deg(v)}. The problem asks whether there exists asubgraph F such that for each vertex v E V, deg(v) E B,. This problem was introducedby Lovász [36]. A set B is said to have a gap of length p 1 if there exists an integerk such that k + 1,” , k + p B and yet k, k + p + 1 e B. Cornuéjols has shownthat the problem is NP-complete if we allow gaps of length more than one [15]. Alsohe gives a polynomial algorithm when G is simple and each B doesn’t have a gap oflength 2 or more. He reduces the problem to a sequence of problems in which each Bis a parity condition, i.e. all entries in B have the same parity. He reduces the problemwith parity conditions to the 1-matching problem. We extend those results by giving anefficient approach for the case of multigraphs (possibly with loops) and preserving thestrongly polynomial nature of the algorithm. We introduce a new type of augmentingwalk for these matching problems which need not be alternating. A direct applicationof Cornuéjols’ reduction to a multigraph results in a pseudo-polynomial algorithm. Weuse his idea to characterize our new augmenting walks, but our algorithm solves theproblem 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 workand moreover the method is one level removed from the original graph and hence willincur extra costs.At this stage we know of no practical problems requiring the generality of the general factor problem. We give a made up problem involving warehouses at the end ofSection 3.1. Hence it is perhaps hasty to dwell on efficiency. Novertheless our approachChapter 1. Introduction 7provides an efficient algorithm even when the graph is not a multigraph. An extendedset of general factor problems are shown to be solvable directly without reduction to anumber of parity problems.In Chapter 4, we study the two-factor problem with a condition. A two-factor ofG consists of a spanning collection of vertex-disjoint cycles. The problem of finding atwo-factor is in P. On the other hand, it is well known that finding a Hamiltoniancycle in a given graph is NP-hard. Many people have studied the complexity of theproblem of finding a two-factor in which the cycles are restricted to having lengths froma prescribed (possibly infinite) set of integers. In the case that the cycles are restrictedto 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 problemis called a triangle-free two-factor, it was shown by D. Hartvigsen [31] that the problemis in P. At this moment, we don’t know if the square-free two-factor problem (no cyclesof length 4) or the { triangle, square} -free two-factor problem is in P or NP-hard orotherwise. We focus our attention on the problem of the existence of square-free two-factors. We obtain an augmenting path theorem like Berge’s augmenting path theoremfor 1-matching [7]. If we have a square-free (0,2)-factor F of G and H is another square-free (0, 2)-factor of G with more edges, then there exists an augmenting walk W which isalternating and the symmetric difference between F and any initial subwalk of even lengthof W is square-free. When we look for an augmenting walk, we need concern ourselveswith squares being locally created. An augmenting path having such nice propertiesdoes not exist for the case of a L-free two-factor unless L C {3, 4}. We obtain apolynomial algorithm for finding such an augmenting walkin a graph where its squaresare vertex-disjoint. The algorithm we present is extremely complicated, consisting of twonontrivial 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 examplesChapter 1. Introduction 8given in Figures 4.19 and 4.20 indicate the difficulty of solving the problem by augmentingwalks. As in most matching algorithms we have a tree growing phase (the BlossomAlgorithm) that gives labels to vertices depending on the type of augmenting walk bywhich the vertices can be reached from a deficient vertex. Blossoms are collapsed cyclesformed in the tree structure by adding edges under certain conditions. Having determinedthat a desired augmenting walk exists, we then recover that walk from our tree structureby expanding blossoms (the Recover Algorithm). Unfortunately in various cases wemust alter the walk from the expected walk in order to avoid creating squares. Examplesare the paths in Figure 4.45 which are replaced by the paths in Figure 4.48 (in thecorresponding diagrams). Please compare the figures to see the changes. In essence,the Blossom Algorithm has avoided dealing with these situations and simply notes thatthe edges currently examined allow us to give labels as described. Later in the RecoverAlgorithm, we deal directly with these situations.To actually prove the algorithm works is a large task. We use the conditions fortermination of the Blossom Algorithm to prove a Tutte-type Theorem (Section 4.9) givinga necessary and sufficient condition for the existence of a square-free two-factor. Thislatter result unfortunately turned out to be too complicated for ready application. TheRecover 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 beextremely complicated and we wished to finish this thesis in a timely manner. Ourresults 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 adifferent character. In the problem of the existence of matrices with given row and columnsums, we use the standard augmenting walk of network flow theory. In the general factorproblem, we present a new type of an augmenting walk which need not be alternating. InChapter 1. Introduction 9the square-free two-factor problem, we use an augmenting walk that is alternating, butneed some additional restrictions such that the symmetric difference between any initialsubwalk of the augmenting walk and the current square-free (0,2)-factor F we have isalso square-free.Chapter 2Integral Matrices with Given Row and Column Sum Vectors2.1 IntroductionDegree constrained subgraphs of a bipartite graph are solvable with Network Flow Theory. One case that has been extensively studied using Network Flow Theory is the caseof integral matrices with given row and column sums. Let m and n be positive integers, and let R = (ri,... , rm) and S = (s1,... , s) be non-negative integral vectors withr1 +•.. + rm = Si +... + s,. Let Q = (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 = (a) withrow sum vector R and column sum vector S such that qij for all i and all j, denotedA Q. We use Qt(R, 5) to denote the class of all (0, 1)-matrices of size m by ii withrow sum vector R and column sum vector S, which corresponds to Qt (R, 5) when Q isthe matrix of l’s. We can, if we wish, interpret a matrix A e 2t(R, 5) as a f-factor(f = (R, 5)) of a bipartite graph given by Q.We can interpret 2tc(R, S) in terms of network flows. The reader may be referredto [23] for the basics of network flow theory. Matrices in 2Q (R, S) can be consideredas maximum integral flows in the following network. The vertices consist of a sources, a sink t, and R1,• , Rm, Si, .. ,Sn. There is an edge from s to R with capacityr for i = , rn. There is an edge from S to t with capacity s, for j = 1,. .. , n.Finally there are edges from R to S with capacity qjj for i = 1,.• , in and j = 1,• .. , n.Consider a maximum integral flow from s to t of size r1 + + rm. Let be the flow10Chapter 2. Integral Matrices with Given Row and Column Sum Vectors 11from R to Si and let A = (a3). We easily deduce that A e 2t’(R, S). Conversely, froma matrix A in 2t’(R, S) we can construct a maximum integral flow of size r1 + + rm.Now the maxflow-mincut theorem says that 2t (R, S) is nonempty if and only if no cuthas capacity less than r1 + + rm. The number of cuts in the above network is 2m+nBy 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 specialclass 2t(R, S) we can reduce the exponential number of inequalities to a linear numberof them, that is only n inequalities. D. R. Fulkerson [22] observed that the result ofGale and Ryser can be generalized to the class of (0, 1)-matrices with given row sumsand column sums and zero trace. Also R. P. Anstee [1] obtained the generalization tothe class of (0, 1)-matrices with given row sums and column sums and with zeros in aprescribed 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 acertain condition (see Section 2).In this chapter, we get a generalization of Chen’s result, that is if Q and S satisfy somecondition, then we have a necessary and sufficient condition for the existence of a matrixin 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 theycan easily be derived from it. Also we build a kind of hierarchy: under weaker and weakerconditions, more and more inequalities, still a polynomial in n, are involved in a necessaryand sufficient condition for the existence of a matrix in 2t(R, S) (Theorem 2.4). Networkflow theory is employed to obtain our generalization.Chapter 2. Integral Matrices with Given Row and Column Sum Vectors 122.2 TheoremsThroughout this chapter, we will use the following notation:[a,b] {a,a+1,a+2,•..,b}= max {a,O}.By the maxflow-mincut theorem of networks, Q1c(R, S) is nonempty if and only if forallI C [1,m] and J [1,n],qij r — Si (2.1)iEIjEJ iEI iJSo we have to check these 2m+n inequalities. But the following lemma reduces these 2minequalities to 2 inequalities. SLemma 2.1 2t’(R, S) is nonempty if and only if for all J [1, n],(rj—>qjj) (2.2)i=1 jEJ jJProof. (==) Let J be any subset of [1, n]. Let I = {i I r, qii}. Then— q ) + = Ti —jeJ iEI iEI jEJBy (2.1),rj—qjj s,.iEI iEIjEJ iJSo we can get inequality (2.2).(=) For any I C [1,m] and J C [1,n],ri—qij rj—qij)iEI iEI i€J i=1 jEJzSi.iJ IChapter 2. Integral Matrices with Given Row and Column Sum Vectors 13The Gale-Ryser theorem says that there exists a matrix in 2t(R, S) if and oniy if forall J = [1,h], (2.2) holds. In the general case of 2I(R,S), we need to check (2.2) forall subsets J of [1, n], an exponential number of inequalities. For a (0,1)-matrix case, itis enough to check it for only n subsets. We will state the Gale-Ryser theorem formallyhere in the notation of the above lemma.Theorem 2.2 [Gale-Ryser Theorem] [29] [45] Suppose that s1 s2 s,,. Thenthere exists a matrix in 2t(R, S) if and only if for all J = [1, h],(r-h) (2.3)1=1 jJThe following theorem is a generalization of the Gale-Ryser theorem. We will notgive its proof here, because this theorem is a special case of Theorem 2.4. We state itseparately from Theorem 2.4 because it has a simpler flavor.Theorem 2.3 Suppose that(qij—qik) <Si—Sk+l forl<j<k<n. (2.4)Then there exists a matrix in 2t(R, S) if and only if for all J = [1, h],rj—qjj) >s. (2.5)i=1 jEJ jJNote that any given column order could be used which gives you the flexibility, depending on Q, to even have s = s11 — 1. On the other hand, we cannot always ordercolumns to make condition (2.4) hold. It may happen that1(qjj—> s3— 5k + 1We can derive from the above theorem not only the Gale-Ryser Theorem, but alsoFulkerson’s result [22] on the existence of a matrix in t(R, S) with zero trace and Anstee’sresult [1] on the existence of a matrix in 21(R, S) which has zeros in a prescribed set ofChapter 2. Integral Matrices with Given Row and Column Sum Vectors 14positions consisting of at most one position per column. In [13], Chen gives the sametheorem as the above theorem, except that instead of our condition (2.4) he gives thefollowing condition:m—qik S—S+l for 1 j < k nwhere z is the maximum entry of Q. It is easy to verify that his condition is includedin 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) whichappears at the beginning of the proof. We end up imposing regularity condition on Qand 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 1 [j]. Suppose that Q and S satisfythe following: let the j ‘s be such that 1 j < .j < < 121+2 n. Then there exist,j,_1} C ,j21+1} and {j2,j4,” ,j21+2} such that(q— qjj + qjj— qjj +• + qjj1— qjj)s — s + s — s +• +s — s + 2p — 1 (2.6)Then there exists a matrix in 2t’(R, 5) if and only if(rj—qjj) (2.7)i=1 jeJ jJwhereJ = [1, h] U [h1,h2] U [h3,h4] U... U [h21_1,h21]or[h1,h2] U [h3,h4] U ... U [h21_1,h21](1hhih•..21_jn)Chapter 2. Integral Matrices with Given Row and Column Sum Vectors 15We are able to weaken condition (2.4) at the expense of having to look at many morecut inequalities, namely with G(n2’) inequalities.If 1 > L!i], then condition (2.7) holds for all subsets J of [1, n] and it is alreadya necessary and sufficient condition for the existence of a matrix in Qt (R, S). It ismeaningless to consider this case.The following condition is a special case of the condition (2.6): for some k 1 + 1,(qij2k_1— qj)+ S2_1— 5j2k + 1.Since we have (1 + 1) pairs of (j2kl, j2k), at least one pair has the difference less thanor equal , i.e. 2k — J2k—1 [-y]. So we obtain the following corollary.Corollary 2.5 Let 1 be an integer such that 0 1 Suppose thatfor 1<j<k<min{j+[nj,n}.Then there exists a matrix in 2I (R, S) if and only if> (r — qjj)i=1 jEJwhereJ = [1,/i] U [h1,2]U [h3,4] U [h21_1,]or[h1,h2] U [h3,h4] U ... U [h21_1,h21](1hhih...21_in).Chapter 2. Integral Matrices with Given Row and Column Sum Vectors 162.3 The Proof of Theorem 2.4Suppose that 2t’(R, S) is nonempty. Then by Lemma 2.1, (2.7) holds. Now we willdo the other direction of the proof. Suppose that (2.7) holds. We construct the desiredmatrix A inductively by columns by rearrangement of the entries in the rows of A*, whereA* is defined as follows: A* = (at) is the matrix with row sum vector R in which entriesin a row are as far to the left as possible subject to the condition that A* Q. So foreach row i of A* there is an index k so that* * * *a11 = qi, a2 = q12, . . , aJ_ = qik—1, alk — qk,alk+1 = 0, alk+2 = 0, ..., am = 0A row rearrangement of row i is the replacement of row i by a new row of the same rowsum r1. We can envision this operation as corresponding to a sequence of operations ofsubtracting 1 from one entry a1 in column j and adding 1 to another entry alk in columnk. This corresponds to moving a 1 from column j to column k. We always keep A Q.Note that A* can be obtained from any other matrix A Q with row sum vector R byrow rearrangements moving l’s only to the left.Let’s start with the first column. Since t1(rm — qj)+ < s2 + s3 + + Sn,min(r1,q) si and s s. If s = s1, go to the second column. Assumethat s > s1. Move entries from the first column to the next columns by row rearrangements. If the column sum reaches s1, then we can start the construction of the secondcolumn. Suppose not. Let and s be the entry of (i, i) and the th column sum of thecurrent matrix A’. Then = qjj for j = 2,••• , n whenever a1 0. Let I = {i a1 0}and J={2,...,n}. Then(*) (rj—>qjj) rj—qjj)1=1 jEJ iEI jEJChapter 2. Integral Matrices with Given Row and Column Sum Vectors 17>(rj—qjj) = s’iEI JEJ> SiSo we have a contradiction to (2.7).Let us suppose that the first k — 1 columns have been constructed and let us proceedto the construction of column k. If S’k = Sk, go to the next column. Otherwise, two casesarise.(i) s’ > SkShift entries from the kth column to the columns k+1,• , n by row rearrangements,until we obtain the column sum 5k Assume that we have to stop shifting beforethe column sum reaches 9k Then = qjj for j = k + 1,. , n whenever ak 0.LetI = {iIak0}I’ = {iIa=q2jVj>k}I” = [1,n]\ (lul’)Claim 1 There exist e E I and t < k such that a’et < qtProof. Assume that no such pair (e,t). Then= qij for all i e I and all j <k.Let J = [1, k — 1] U [k + 1, n]. Then by an argument similar to (*), we get acontradiction to (2.7). IClaim 2 There exist f E I” and u <k such that af 0.Proof. Assume that no such f and u exist. Then = 0 for all i E I” and all j <k.Let J = [k +1, nj. Then by an argument similar to (*), we arrive at a contradictionto (2.7). IChapter 2. Integral Matrices with Given Row and Column Sum Vectors 18Let’s construct a digraph G = (V, D), where V = {vi,... , Vm} U ....... , W,_i} U{ s, t} and D consists of the following arcs:v—*w3 if a<qw,—v if aOv—+t if iEI”s—*v if iEIIf i E I”, there exists j > k such that < qjj. And ak 0 for all i E I. So ifthere exists a directed path from s to t, then we can shift at least 1 from the kthcolumn to one of columns k + 1,••• , n, by following the directed path. Now assumethat no such directed path exists. LetJ0= {j <k a directed path from s to w}I’ = {i I’ a directed path from s to v}12 = I’\IThenVi1”UI2 &VjEJ0 a=0Vi e I U I. & Vj J0 a = qjjSo for any j(< k), either = 0 for all i E I” U 12 or = qij for all i e 1U1.Claim 3 There exist t and u (<k) such that t <u, a’et < qet for some e e I U I,and 0 for some f E I” U 12.Proof. Assume that no such pair (t, u) exists. Let g be the last column beforecolumn k that has a nonzero a’fg for some f E I” U ‘2 (by Claim 2 there exists suchChapter 2. Integral Matrices with Given Row and Column Sum Vectors 19g). ThenVi e I U Ii & Vj g = qjjViEI”U12 &g<Vj<k a3=OAlso,ViEI”U12 ak=O‘Ii e I U I & Vj > k a = qjjLet J = [1,g]U[k+1, n]. Then by an argument similar to (*), we get a contradictionto (2.7). •Claim 4 There exists another pair (t’, u’) of (t, u) different from (t, u) satisfyingconditions of Claim 3 where t’ < u’ <t < ‘u.Proof. Without loss of generality, we can suppose that a = qij for all i E I U Iand all j (t <j u) and a3 = 0 for all i E I” U ‘2 and all j (u <j k). Thereexists u’ < t such that 0 for some i e I” U 12. Otherwise,Vi E I U 12 & Vj < h1 = 0Vi e I U Ii & h1 Vj h2 a = qjj‘Ii E I U 12 & h2 <Vj <h3 = 0Vi E I U I & h3 Vj h4 = qijwhere h1 = t+1, h2 = u, h3 k+1 and h4 = n. By letting J = [h1,2]U[h3,h4}, wecan get a contradiction to (2.7). Now assume that there is no such t’. Without lossChapter 2. Integral Matrices with Given Row and Column Sum Vectors 20of generality, we can suppose that = 0 for all i e I” U 1 and all j (u’ <j t).ThenVi E I U Ii & Vj h = qijViEI”U12 & h<Vj<hi a=0Vi e I U Ii & h1 Vj h2 = qjjVi E I U 12 & h2 <Vj < h3 a = 0Vi E I U I & h3 <Vj <h4 a = qijwhere h = u’ and h (i = 1,... ,4) is the same as above. Let J = [1, h] U [h1,h2j U{h3,h4]. By an argument similar to (*), we get a contradiction to (2.7). IBy repeating an argument similar to Claim 4, we can get more pairs (t, u) satisfyingconditions of Claim 3. To get the th pair, we would let J = [1, h] U [h1,h2] UU [h2,_1h2] or [h1,h2] U•• U [h2_1,h2]. With condition (2.7) we could getl different pairs of (t, u), unless k 21. Suppose that k < 21. Let J’ {j <k = qij for all i E I U I}. Then J’ is either [1, h] U [h1,h2] U... U [h2_1,h2Jor [h1,h2] U ... U [h21,h2] (hi 1). Since k 21, p is at most l — 1. So we geta contradiction to (2.7) with J = J’ U [k + 1, nj. Now we can assume that k > 21and we have l pairs (jl,j2), , (ji—i,ji) satisfying conditions of Claim 3 withi <12 < <121. For any 2p1, there exists e E I U I’ such that a21 <Also, a21 = 0 for all i E I” U ‘2. So,q2_1 a21 + 1iEIUIi iéIUIi= sj2p_1 + 1For any 2p, there exists e E I” U 12 such that a’• 0. Also, a2 = for allel2pChapter 2. Integral Matrices with Given Row and Column Sum Vectors 21iEIUI1. So,q2 a2 + ( a2 — 1)iEIUIi iEIUIi iEI”U12= si2p—1Since sç = si,... , = Sk1 and s’k > Sk, there exists j > k such that s < 53.Since ak = 0 for all i E I” U 12,> > Sk+l.iEIUIiAlso,qii sjElUliLet 321+1 and 321+2 be k and j, respectively. Then for any {j , j_1} C{jl,j3,” ,j21+1} and {j,j ,j21+2},(qjj— qii +•• + qjj1 — qjj)>D (ii — qii + + qjj1 — qjj)iEIUIi( q — q) +“ + ( — > q)iEIUIi iEIUI iEIUIi iEIUIi(sji— sj + 2) + + (s31—s + 2)= s— s + •• + s—s + 2pThis contradicts (2.6).(ii)‘k < SkMove some entries to the kt column from columns k + 1,•.. , n by row rearrangements, until we obtain the column sum Sk. Assume that we have to stop movingbefore the column sum reaches Sk. Then = 0 for j = k + 1,•.. , n wheneverChapter 2. Integral Matrices with Given Row and Column Sum Vectors 22Tak <qik. LeI {ia<qjk}I’ = {iIIa3=Oforal1j=k+1,—..,n}= (IuI’)’By the same arguments as in the case for s’k > sk, there exist t and u (< k) suchthat a’et < qet for some e e I” and a’fU 0 for some f e I.Construct a digraph G = (V, D) in the same way as case (i), except thatv—+t if iEIs—*v, if iEI”If there is a directed path from s to t, then we are finished. Assume that there isno such path. LetJ0= {j <k a directed path from s to w3 }‘2 = {i e I’ a directed path from s to v}Il = I’\12ThenViEIUI1 &VjEJ0 a=0Vi e I” U 12 Vj Jo a = qi,So for any j(< k), either a = 0 for all i e Jul1 or a = qij for all i e I” U 12.Claim 5 There exists t, u and v (< k) such that t < u < v, a’et < qt for somee e I” U 12, afU 0 for some f e 1U1, and a’gv <qgv for some g E I” U 12.Chapter 2. Integral Matrices with Given Row and Column Sum Vectors 23Proof. We already note that there exists v such that a’gv <qgv for some 9 E I U ‘2.Let v be the last column before column k that has (<qgv) for some g I” U ‘2.Assume that there doesn’t exist u (< v) such that a’f 0 for some f E I U I.ThenViEIUI1 & Vj<h1 a=0Vi e I” U 12 & h1 Vj h2 = qijwhere h1 = v + 1 and h2 = k. Let J = [h1,2j. By an argument similar to (*),we arrive at a contradiction to (2.7). So there exists u (< v) such that a’j 0 forsome f E I U Ii.Now let u be the last column before column v that has nonzero a’f for somef E IUI1. Assume that there is not (< u) such that a’6 <qet for some e E I”U12.ThenVi e I” U ‘2 & Vj h = qjjViIUI1 &h<Vj<h1 a3=0Vi e I” U 12 & h Vj h = qijwhere h = ‘u and h (i = 1,2) is the same as above. By letting J = [1,h] U [h1,2],we can get a contradiction to (2.7). ISimilar to (i), we can get 1 different pairs (t, u) as in Claim 3 and an additional pair(v, k) by letting J = [1, h] U [h1,h2j U ... U [h21_1,h21] or [h1,h2] U ... U [h21_1,h21],unless k 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 ofTheorem 2.4 is completed.Chapter 2. Integral Matrices with Given Row and Column Sum Vectors 242.4 Further StudyIn Theorem 2.4, if 1 > L--] condition (2.7) has to hold for all subsets J of [1, n], yetcondition (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 cutsbecomes exponential.Chapter 3General Factor Problem3.1 IntroductionIn this chapter we consider the following generalization of the factor problem which wasintroduced 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 ofvertex v in G. We let 13 = {BIv e V}. The general factor problem asks whether thereexists a subgraph F such that for each vertex v E V, deg(v) e Br,. A set B,, is said tohave a gap of length p 1 if there exists an integer k e B,, such that k+ 1,, k+p Band k +p+l 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’thave a gap of length more than one. We restrict our attention to Br’s with all theirgaps of length 1. We extend the result of Cornuéjols by giving a strongly polynomialalgorithm for the case of multigraphs (possibly with loops) which seems likely to be moreefficient even for simple graphs. We introduce a new type of augmenting walk for thesematching problems which need not be alternating. It may be possible to obtain a stronglypolynomial algorithm by using the idea of “sparse substitutes” which Gabow used forthe (g, f)-factor problem [27].Suppose that F is a subgraph of G. We say a vertex v has deficiency i with respectto B (written defF(v) = i) ifi = min{Ik — deg(v) k E B}25Chapter 3. General Factor Problem 26The deficiency of F with respect to 13 isdefF= defF(v)vEVOur problem is seeking a subgraph F of minimum deficiency with respect to B, whichwe will call B-optimal or just optimal. A 13-factor is a subgraph F of deficiency 0, butwe consider the more general problem.Throughout this chapter, let g,, (resp. f) be the lower (resp. upper) bound of B,,,i.e. B,, C {g,,,.•, f,,}. First consider the relaxation of the problem where B,, consists ofan interval, i.e. B,,= {gv, g,, + 1, g, + 2,.. , f,,} and we say vertex v has deficiency i withrespect to (g, f) (written dei’ (v) = i) ifi = max{g,, —deg(v),0,deg(v)— f,,}The deficiency of F with respect to (g, f) isdef’F = def5’(v)vEVA (g, f)-optimal s’ubgraph is a subgraph which minimizesOf course we wish to consider more general B,,’s. Given that the B’s are parityconditions (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 certainspecial augmenting walks. These walks are defined in Section 2 and refined by a seriesof lemmas in Section 3. In Section 4 we present our algorithm. In Section 5 we consider general 13. We start with (g, f)-optimal subgraph and then use the reduction ofCornuéjols to a number of problems of the previous type. A (g, f)-optimal subgraph isimportant 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 and5.Chapter 3. General Factor Problem 27Some warehouse problems can be interpreted as a general factor problem. We providethis made up problem to give at least one example where the general factor problem mightarise. It does not involve multigraphs. A factory has to supply n customers and has indifferent potential locations of warehouses. Each location of a warehouse can serve up to2 customers and can only serve some specified customers. A factory wants to select asfew 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 awarehouse and a vertex in B represents a customer. There is an edge between verticesv and w if customer w can be served by location v. Each vertex v in A has a degreeconstraint B,, = {O, 2} and each vertex w in B has a degree constraint B,, = {1}. Asubgraph F of G with the minimum deficiency gives a solution for the factory.3.2 Augmenting WalksIn 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 = (A\B)U(B\A).Let F be a subgraph of G. A sequence of vertices and edges P = v0e1 wheree = (v_1,v) is said to be an augmenting walk in G with respect to F if(i) v0 is a deficient vertex, i.e. deg(vo) B,,0(ii) defFp(vo) <defF(vo)(iii) def (FAP) <def F(iv) there exists no P’ = v0e1 ekvk (k < n) such that def (FAP’) <def FWe say that e has label + if e F. Otherwise, e is said to have label —.Chapter 3. General Factor Problem 28Our augmenting walks are different from other augmenting walks, which alternatebetween + 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 solutionwhich can be obtained from F by augmenting walks.Theorem 3.1 Given a non-optimal subgraph F, there exists an optimal F0 which can beobtained from F by augmenting walks.Proof. Assume not. There exists an optimal F’ and a subgraph F0 such that F0 can beobtained from F by augmenting walks and such that FoLF’I is minimum. Since F0 isnot optimal, there exists a vertex v0 such that defF0 (vo) > defF’ (vo). There exists anedge e1 E F0/F’ such that defF0{€1}(vo) < def(vo). (If deg0(vo) is in a gap, thenchoose any edge in F0LF’ having v0 as an end vertex. If deg0(v0) < g,0, choose anedge in F’ \ F0. If degF0(vo) > f,0, choose an edge in F0 \ F’.) Let v1 be the other endvertex of e1. If defFo{ei} (vi) defp’0(v1), then P = v0e1v1 is an augmenting walk andcontrary to the choice of F0. So defF0{61}(vl) > df’0(Vi). If defF0{€1}(vl) < defi(vi),F” = F’/.{ei} is optimal and IF”AFoI < IF’LFoI, a contradiction to the choice ofF’. So defFo{ei}(vl) > def’i(vi). There exists an edge e2 E (F0A ’) \ {ei} such thatdefFo{ej,e2}(v1) < defFo{ei}(v1). By a similar argument as above, defFo{ei,e2}(v2) >defFo{ei}(v). We continue growing a walk in this way. Since F0AF’ is finite, weeventually get a contradiction. •3.3 General Factor Problem with Parity ConditionsIn this section we study the general factor problem with parity conditions, that is, theelements in B are either all even or all odd. At the end of this section we consider thecase that some Br’s are intervals. Let B = {gv, g + , f} where f = g, + 2r forsome integer r. We assume that each B has this form, if no remark is given.Chapter 3. General Factor Problem 29We examine the reduction of Cornuéjols [15] of the B-factor problem on G to a1-matching problem on G’ where G’ can be constructed as follows. Let {ei,... , ek}be the set of edges incident with vertex v. Let e = (ni, v) for j = 1,••• , k , letW = U {nt}t1,...,k_9Vand let L = t) I 1 j k and 1 t k — 9v},i.e. the graph (W, L) is a complete bipartite graph. Also add edges (n2t_1, n2t) fort = 1,... , r. The graph G’ is the graph obtained from G by replacing each vertex v bythe graph (W, L) as shown in Figure 3.1.nifl2fl2r-1fl2rflkgIf F’ is a maximum cardinality matching of G’, then F is optimal with respect toB where F is the set of edges (u, v) such that v) is in F’ for some j. Let F be asubgraph of G and v be any vertex of G. If deg (v) is in a gap, then we can consider vin G’ as Figure 3.2 (a) or (b), matching as many vertices v and n as possible. We caneasily change from (a) to (b), and vice versa. So this difference will cause no difficultiesin our proofs. Similarly, v in G’ can be considered as (c) if degF(v) < g,, and (d) ifdeg (v) > f’,. If deg (v) e B, all of v are matched like (e), (f) and (g). If deg (v) > g,and deg(v) e B, then at least one of edges (n2t_1, n2t) is in the matching F’ like (e)and (g). If deg(v) <f and deg(v) e B, then at least one of edges (n2t_1, n2t) is notin F’ like (e) and (f).Figure 3.1:aa CD CD‘1 II 0) II-<II I’)0)0 I,a CD CD 11II a CD CD T1II a CD CD‘1 II F\) II CDIa CD CD‘1 II (.11 a CD CD‘1 C.’, a CD CD-I, IICD-C 3 C) :3- CD a CD a CD CDC)Chapter 3 General Factor Problem 31Let F’ be a matching in G’ such that (ui, vi) is in F’ if and oniy if (u, v) e F andas many and n are matched as possible (like Figure 3.2). Then an augmenting walkin G with respect to F corresponds to an augmenting path for a 1-matching in G’ withrespect to F’, and vice versa. So we can characterize an augmenting walk in G using thisreduction.Lemma 3.2 Let P be any augmenting walk in G with respect to a subgraph F, sayP = v0e1—•ev. Except for n, the deficiency at v_1 decreases and the deficiency atv 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,defF{ei}(vo) < defF(vo). Now let’s assume that defF{1,...,€j(v1_1) < defFz{ei,...,e_i}(vi_1)for i k and defF{ei,...,e}(vj) > defF{ei,...,e_,}(vj) for i < k.We can classify vk in the following cases:(i) gVk < degF{1••• 6g 1}(Vk) < fvkIf degF{1... e 1}(VJ) is in a gap, then degF{1...}(vk) E Bvk whatever ek is.So P,= v0e1 .. ekvk is an augmenting walk and defF(vk) > defFAp(vk) = 0. IfdegF{€1...}(vk) is not in a gap, defFz{el,...,ek}(vk) > defFz{el,...,ek_l}(vk) = 0.Adding or subtracting any edge e1 having as an end vertex decreases thedeficiency at vk. Thus defF{eI,...,ek+,}(vk) <defF{e,,...,ek}(vk).(ii) degF{e1...}(vk) < gVkIf ek has label +, then P = v0e1 . ekvk is an augmenting walk and defFtp(vk) <defF(vk). Otherwise defF{el,...,ek}(vk) > defFz{el,...,ek_l}(vk). From Figure 3.3 (a)(the reduction to G’), we can tell that ek+1 must have label +. So defF{e,,...,ek÷l}(vk) <defF{el,...,ek}(vk).Chapter 3. General Factor Problem 32(iii) degF{e1,...,e_}(vk)= gVk < fr,.If ek has label +, then any edge having an end vertex Vk can be ek+1. If not, ek+1must have label + by Figure 3.3 (b).(iv) degF{1••k 1}(vk) = gVk = fvkFrom Figure 3.3 (c) (resp. (d)), ek+1 must have label + (resp.—) if ek has label —(resp. +).(v) degF,{61...1}(vk) fvkSimilar to (ii) and (iii).The proof of Lemma 3.2 is completed. IBy the above lemma, an augmenting walk doesn’t change deficiencies at middle vertices and the deficiencies at v1 and v decrease by one each, i.e. defF/p(v) = defF(v)for i 1, n and defFp(v) defF(v) — 1 for i = 1 and n. The starting and ending(a) (b)eke(c) (d)Figure 3.3:Chapter 3. General Factor Problem 33vertices of P must be deficient, i.e. their degrees are in a gap or outside g and f. Andthe degrees of middle vertices are not in a gap. For convenience sake, we state this factas a lemma.Lemma 3.3 Let P be an augmenting walk with respect to a subgraph F. Then the degreesof middle vertices in P are not in a gap and the start and end vertices are deficient withrespect to F.The next lemmas contribute to a strongly polynomial algorithm for searching for anaugmenting walk by showing that our walks only use vertices whose degrees are betweeng 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 mostonce through a vertex v having g,, < degF (v) < f and deg (v) E B,,.Proof. Let P v0e1 Assume that P goes more than once through a vertex vsuch that 9v <deg(v) <f,, and degp(v) E B,,, that is Vk = v1 = v in P for some k 1.Without loss of generality, we may let k be the first position in P such that v appearsand 1 be the last one. Let’s consider the augmenting path F’ in G’ corresponding to P.If we can omit the edges e+1,... , e from F’ where e is the edge in G’ corresponding toe, then we can omit ek4,” , e1 from P. Let e’k = (viz, Ua) and e+1 = (v’, w”).Let’s consider the following cases:(i) One of ek and e11 has label —, and the other has label + (Say ek has label +, theother case is similar).Since ek has label +, e’k is not used in the matching F’. The vertex Va must bematched since degF(v) E B. So Va is matched to some nt. We can replace theedges between e’k,+l and e in P’ by the matched edge (v’, nt) and the unmatchededge (nt, vb). Thus the edges ek+1,• ,e1 could be omitted. See Figure 3.4 (a).Chapter 3. General Factor Problem 34(ii) Both of ej and e11 have label —.Since deg(v) > g, and deg(v) E B,, at least one of edges (n2t_l,n2t) is in thematching F’ of G’. Since ek and ei+i have label —, e’k and e+1 are in F’. Thus(Va,n2t_l) and (n2t, vb) are not in F’. We can replace the edges between 4+ and ein P’ by the edges (Va,n2t_l), (n2t_l,n2t), and (n2t, vb). Thus the edges ek+1, , ecould be omitted in P. See Figure 3.4 (b).(iii) Both of ej and e11 have label +.Since degF(v) <fr, and deg(v) E B, at least one of edges (n2tl,n2t) is not in F’.If (Va,n2t_l) and (n2t, vb) are in F’ (or (Va, n2t) and (n2t_l, vb)) (like (c)), the edgesbetween e+1 and e in P’ could be replaced by the edges (Va,n2t_l), (n2t_l,n2t) and(n2t, vb). Assume not. Fortunately we could match Va to n2t_l, v” to fl2t withoutcausing a problem. Since ek and e,+i have label +, e’ and e+1 are not in F’. ais matched to one of vertices n, and vb to j• Also n2t_l is matched to VC, andn2t to v’. Without causing a problem, we could match Va to n2t4 instead of nP.Similarly vb could be matched to n2t instead of like (d). We could delete theedges between e+1 and e from F’. Hence the edges between ek+1 and e1 could beomitted.The proof of Lemma 3.4 is completed. ILemma 3.5 Any shortest augmenting walk P goes at most once through a vertex v suchthat deg(v)= g, or f except in the following cases. When deg(v) = liv (resp. f) theedge coming into v is — (resp. +) and the edge going out from v is + (resp.—) in thefirst visit. In the second visit, the edge coming into v is + (resp.—) and the edge goingout is — (resp. +).Proof. We will only consider v having deg (v)= g,. It is similar in the case thatChapter 3. General Factor Problem 35(a)2tfl2t(b)eke1deg(v)= f. Let P v0e1 Assume that P goes through v more than once.Let k be the first position in P such that v appears and 1 be the last one.If at least one of ek and ej1 has label +, then we can omit the edges ek+1, , e1 fromP by the same argument as Lemma 3.4.Suppose that both of ek and ei+i have label —. The edges ek+1, , e1 can be dividedinto closed walks C2 (i = 1,•.• , m) including v only once, i.e. each C starts from v andends in v. If there exists C2 such that both starting edge e8 and ending edge et havelabel +, we can delete edges ek+1, , e8_ and edges et+1,•• , e1 by the same argumentas Lemma 3.4. The new augmenting walk goes through v twice, first arrives with — andleaves with +, next arrives with + and leaves with —.Now, let’s show that such a C, exists. Assume not. Then in each C , at least one ofstarting edge and ending edge has label —. Since ek has label—, ek+1 must have label+ by Lemma 3.2. So the ending edge of C1 must have label —. Thus the next edge, i.e.Figure 3.4:Chapter 3. General Factor Problem 36the starting edge of C2 must have label +, etc. So every starting edge of C2 has label+ and every ending edge has label —. But the ending edge e1 of Cm must have label +since el+l has label — by Lemma 3.2. Thus we get a contradiction. IIn the next lemma, we insert the extra hypothesis that F is (g, f)-optimal. Thenan augmenting path doesn’t go through certain vertices, and avoids certain unpleasantpossibilities such as a pseudopolynomial algorithm when our walks visit a vertex v anumber 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’tgo through vertices v such that deg(v) <gv or> f.Proof. Assume that P goes through some vertices v such that deg(v) <gv or> f. Letu be the last vertex of this type that P goes through. Say deg(u) <gu (it is similarif deg(u) > f). If u is the end vertex of P, then defFp(u) <defF(u), and hence thedegree 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 withrespect to (g, f) at those vertices don’t change. Also the deficiencies with respect to B atthe start vertex of P decreases, so the deficiency with respect to (g, f) doesn’t increase.Thus the deficiency of FL\P with respect to (g, f) is less than of F, a contradiction.Suppose that u is not the end vertex of P, i.e. P = v0e1 vk_lekuek+lvk+1Let F’ = uek+lvk+1 By Lemma 3.2, the deficiency with respect to B at uincreases when ek is added to P and the deficiency with respect to B at u decreases whenek+1 is added to P. So ek must have label — and ek+1 must have label +. For i > k,deficiencies at v relative to (g, f) don’t increase. Thus the deficiency of FAP’ relativeto (g, f) is less than of F, a contradiction that F is (g, f)-optimal. IBy Lemma 3.6, an augmenting walk P with respect to a (g, f)-optimal F starts andends at vertices whose degrees are in a gap. Suppose F is a (g, f)-optimal. We seek aChapter 3. General Factor Problem 37walk of vertices v such that degF(v) E B,, which joins a pair of vertices whose degrees arein a gap. The walk doesn’t increase deficiencies at middle vertices in the way described inLemma 3.2. In an augmenting walk P = v0e1 • ekvI ek+1 can have either label(+ or—) if <deg(vk) <fvk, deg(vk) = 9Vk and ek has label +, or deg(vk) = fvkand ek has label —. If deg(vk) = gVk (resp. fvk) and ek has label — (resp. +), ek+1can have label + (resp.—). Our augmenting walks are close to being paths, which gothrough each vertex at most once with some exceptions described in Lemma 3.5. Wecan find an augmenting walk by a blossom algorithm. It can be completed in O(1V12)or O(IIEII) operations where hEll is the number of edges in the simple graph associatedwith 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 someBe’s are intervals. The difference occurs at an end vertex of the augmenting walk. LetF be a (g, f)-optimal subgraph. An augmenting walk with respect to F starts from avertex whose degree is in a gap, and goes through vertices following the way describedin the above paragraph. But it ends if it reaches either a vertex whose degree is in a gapor a vertex v such that B is an interval and the changes do not increase the deficiencyat v with respect to 23 (i.e. it reaches v by an edge labelled + and deg(v) < fr,, or byan edge labelled — and degF(v) > gv.). If an augmenting walk ends at a vertex v suchthat B. is an interval, then it decreases the deficiency with respect to 23 by one, only atthe start vertex.It is a remarkable invariant of our algorithm that our subgraph remains (g, f)-optimalafter an augmentation, so our subsequent augmenting walks have the same structure. Ifwe don’t have a (g, f)-optimal subgraph, we might have to look for augmenting walksmore than polynomially many times in IVh. We would not obtain a strongly polynomialalgorithm for finding a 23-optimal factor.Chapter 3. General Factor Problem 383.4 Algorithm for General Factors with Parity ConditionsIn this section, we describe an algorithm that finds an optimal solution with respect toB 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 willtake O(1V13 + MCF(IVI)) time where MCF(IVI) is the time for a minimum cost flowalgorithm on a lvi vertex network. Next look for an augmenting walk connecting twovertices 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. Theaugmenting path in his algorithm is alternating, but our augmenting walk is not. Andsome edges can be used twice.The following is a rough outline of the algorithm for an augmenting walk with respectto a (g, f)-optimal subgraph F. We form a multigraph G* on vertices of G such thatg, deg(v) f, with the edges in two classes E, E. The edges of E consist of onecopy of an edge e = (u, v) in F such that 9u deg(u) <f and g deg(v) <fr, andmin{multiplicity of e in F, 2} copies of e such that deg(u) = f or deg(v) = f. Theedges of E consist of one copy of an edge e = (u, v) not in F such that g, <deg(u) <fand 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, thoseedges e=(u, v) in F (resp. not in F) such that deg(u) = f or deg(v) f (resp.deg(u) = g or degF(v) = g) can be used twice in an augmenting walk.Choose any vertex w whose degree is in a gap. We form a directed tree directed outfrom w. The tree grows vertex by vertex (Step 5) where we use the notation p(v) = ‘Uto denote that u is the predecessor of v in the tree. The edges of the tree are storedseparately from G* to keep them from being used again. A vertex v is given a label +Chapter 3. General Factor Problem 39(resp.—) if the edge leaving v can have label + (resp. —). That is, the edge leaving v canhave label + (resp.—) if 9v deg(v) < f or deg(v) = f (resp. g, < deg(v) for degF(v) = gv) and the edge arriving v has label — (resp. +). Note that this is thereverse 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 calleda blossom. We shrink the vertices of the blossom to a single pseudovertex. We givethe pseudovertex labels +,— and these labels apply to all vertices of G contained init (Step 4). One of the vertices of the blossom may be a pseudovertex and so theremay be nesting of blossoms. An outermost blossom or pseudovertex in this inductivestructure is called exposed. For each blossom, one vertex (possibly a pseudovertex) isdistinguished as the base vertex being the vertex of the blossom closest to the root ofthe tree. Another item we introduce here is the true base of a blossom. If the base ofa blossom is not a pseudovertex, then it is the true base. Otherwise the true base isinductively defined as the true base of the base of the blossom. We call a starter walk awalk P v0e1 e,v,, which can be the first part of an augmenting walk, i.e. deg(vo)is in a gap and the deficiency at v0 with respect to B decreases, and the deficiencies atv (1 i n — 1) don’t change.We use the term dual to refer to the replacement of E by E—, g by f, g, deg (v) <f by gu <deg(v) f, F by Fc, and vice versa.Algorithm for Finding Augmenting WalksStep 1. (Initialization)Form a multigraph G* = (V*, E*) possibly with loops where V = {v e Vdeg (v) f } and E* are divided into two classes E, E. The edges of E consist ofone copy of edge e = (u, v) for e F such that g deg(u) <f and Yv deg(v) <fand {the number of e in F, 2} copies of e such that degF(u) = f or deg(v) = f. TheChapter 3. General Factor Problem 40edges of E+ are the dual of E. Choose a vertex w whose degree is in a gap. Put w onthe 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 toanother vertex whose degree is in a gap). Otherwise select one vertex u from the list.Step 3.If u has label —, do Step 4, 5, and 6. Otherwise do Step 7.Step 4. (Search for blossoms)Search for any edge (u, v) E E where v is in the tree and has label —. If there issuch an edge, it forms a blossom in the tree which we shrink to a pseudovertex. Thepseudovertex is given labels + and —, and is added to the list of unscanned vertices. Thevertices contained in the pseudovertex are deleted from the list. Return to Step 2. Ifthere 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, thenput v in the tree with p(v) = u. v gets label + if deg(v) = ge,, otherwise + and —. Thechosen 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 toStep 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 followingthree lemmas verify that our algorithm works correctly. That is, the assertions made inChapter 3. General Factor Problem 41Step 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 + whenb is added to the tree. Then for each vertex v of 0, there exists walks W1 and W2 fromb 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 ofvertices in 0 except b is in P, P U W1 (resp. P U W2) is a starter walk from w tov 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 dipathsbe1u ..be’1v . e’vjoined by the edge e joining u and Vq. First, assume that none of the vertices of 0 arepseudovertices. Let u,. be an arbitrary vertex in 0. Let W1 = be1u.None of u2is in P, so the deficiencies of the vertices in P other than b do not change by adding W1to P. If b has label + (resp.—), then e1 has label + (resp. —). The deficiency of b isnot changed by P U W1. None of u has a change in its deficiency by W1, except u. SoPUW1 is a starter walk. Assume that in PUW1 the next edge has only one label + or —,say +. Then deg(u) = ga,. an e has label —, so u,. must have only label + in the tree.The edge er+1 has label + (if u,. = u, er+1 = e). Let W2 = be’1v . e’qvqeupep • e1ur.Then PUW2 is a starter walk by a similar argument as above. Since er+1 has label +, thenext edge in P U W2 can be label — in any case. Now, let’s assume that one of verticesChapter 3. General Factor Problem 42of 0, say u3, is a pseudovertex and eu38+i is part of W1. The edge e8 hits u3 at its truebase b8 and e8+i hits u at one of vertices of u, x. Using induction, we can constructa walk from b8 to x consisting of nonpseudovertices with the appropriate operations, sothat it can replace u3. Similarly, each pseudovertex in the walk W2 can be expanded.For label + (resp.—), we can get a walk from b to Ur consisting of nonpseudoverticeswhere the union of this walk and P is a starter walk and the next edge can be label +(resp.—). ILemma 3.8 If a vertex v is in the tree with a label + (resp.—), then there is a starterwalk 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 v0e1 in the tree where v0 is w orthe pseudovertex containing w and some v may be pseudovertices. If v = w, then itis trivial. If v0 = v, i.e. v and w are contained in the same pseudovertex, we can getthe desired walk from w to v using Lemma 3.7. Now suppose that vo v. Then ehits va_i at a vertex u, where ‘u may be v_ itself or one of vertices of Vn_ if isa pseudovertex. Without loss of generality, we may assume that there is a starter walkP from v0 to u, and the labels of u and e agree. First, let’s consider the case whenv = 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 isa pseudovertex with its true base b. Then we can construct the desired walk by addingto P the walk from b to v found by the method in Lemma 3.7. ILet’s denote ‘Tn’ the set of descendents of v, i.e. {u I 9(u) = v for some k } whereinductively we define pk(u) = p(p’(u)) for k 2.Chapter 3. General Factor Problem 43Lemma 3.9 If there is a starter walk from w to a vertex v such that we can extend thewalk from v by an edge with label + (resp.—), then v is in the tree with a label + (resp.-).Proof. Let P = v0e1 be the starter walk from w to v (v0 = w and v v).Let’s assume that the label of v and e+i agree for i = 0,... , n — 1. If v, has not beenin the tree yet, then when is being scanned, e is still in G* and so v,., will be givenlabel +.Assume that v, is already in the tree and has label —. Then deg(vfl)= f andthe edge (p(Vn), v) has label +. Since the next edge can be +, er-, must be —. Sop(Vn) v,4. If p(Vn.1) v, then joining v_ and v,, by the edge e forms a blossom,so give v label +. Now suppose that p(Vn_i) = v. Then there exists r (it may be 1)such that yr and v E for r <j n—i. First let’s show that for r <j n—i,Vj has both labels + and —. Assume that v8 (r <s < n — 1) has only one label, say +.Without loss of generality, we may assume that Vj (s <i n — 1) has both labels + and—. If p(v5) = then v3 has both labels (Since the labels of v8 and e8+i agree, e3+ haslabel +. So v. get label — in any case.). So P(Vs) If p(v81) v, then joiningv. and by the edge e8+i forms a blossom which gives v label —. Thus P(Vs+i) = Vs.There exists q such that vq+1 g and v E T8 for s <j q. Since p(Vqi) Vq andp(Vq) Vq1, joining Vq and Vq+1 by the edge eq+1 forms a blossom which contains v. Sov8 gets both labels. So all v (r <j n — 1) have both labels, in particular rl•Since the label of r and er+1 agree and v1 has both labels, joining and yr bythe edge e+i forms a blossom, which contains v,. Hence v gets both labels. •Our algorithm works also when some Bs are intervals, with one exception. In Step5, it stops also if B is an interval and deg(v) <ft.We can get a (g, f)-optimal subgraph F inO(V3+MCF(IVI)) time. We can decreaseChapter 3. General Factor Problem 44the deficiency with respect to B by at most lvi, one per vertex. We need grow a treeat most once from each vertex, and this takes O(ivI2) time. We obtain the followingtheorem.Theorem 3.10 A subgraph with minimum deficiency with respect to B, where each Bis an interval or a parity condition, can be found in O(1VI3 + MCF(IVI)) time.3.5 General Factor Problem Allowing Gaps of Length 1In this section, we study the general factor problem where each B is an arbitrary subsetof {O, 1,. . , deg(v)} without gaps of length 2 or more. We can get a B-optimal factor by solving a “few” general factor problems with parity conditions directly followingCornué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, letl’ = min{t B, all the elements of {t, deg(v)] fl B, have the same parity}u’ = max{t e B all the elements of [t, deg(v)] fl B, have the same parity}andpF— hF Fl p— L6v , jAll the elements of B have the same parity, and either l —1 e B, or l’ = gj,. Similarly,either u’ + 1 E B or u’ = f.Leti,F i FiL) = IvVFor any w E V such that l — 1 E B, letF IB forvV\{w}= {LV}VEv, where LI {l—1} forv=wChapter 3. General Factor Problem 45and for any w e V such that u + 1 E B, letI BF for vEV\{w}F_I _j Vw — j vJvEV, wiiere = ( {u’+1} forTheorem 3.11 (Cornuéjols [15]) The deficiency of F with respect to B is minimum ifand only if there exists no subgraph with smaller deficiency with respect to one of thefollowing families than the deficiency of F with respect to B:(i) B’(ii) £ for w e V such that l — 1 e B(iii) U’ for w V such that u + 1 e BCornuéjols gave an algorithm for finding a B-optimal subgraph which proceeds asfollows. First find a (g, f)-optimal subgraph F. We can only decrease the deficiencywith respect to B by VI. To get an improved solution or find that F is optimal withrespect to B, we use Theorem 3.11 and consider at most 21V1 + 1 general factor problemswith parity conditions. Then we may need to solve O(1V12)general factor problems withparity conditions to obtain a B-optimal subgraph.We must consider the complexity of computing £‘, UF, and BF which involves thecomputation of l’, u. These issues did not arise for Cornéjols for simple graphs. It issensible to imagine that B is given as a partition B = B1 U B,2 U U Bq) whereif k e B1 and 1 e and i <j, then k < 1. Also each B, is a parity condition or aninterval and so can be conveniently expressed by its smallest and largest elements. Thenthe complexity of determining l’ and u is O(logt(v)). We let = maxt(v), and notethat the size of the problem is at least .Theorem 3.12 A subgraph with minimum deficiency with respect to B can be found instrongly polynomial time O(1V15 + IVI2MCF(IVI) + Vlogt).Chapter 3. General Factor Problem 46Even though we cannot reduce the complexity of our algorithm theoretically, we canmake some heuristic improvements as follows: In £ = {L}vEV, let L = including— 1 instead of setting L = {l — 1}. Similarly for U’.3.6 Further StudyWe can consider the following generalization of the general factor problem: For eachvertex v e V, we have costs below(v), above(v) and gap(v) for violating its degreeconstraint. Suppose that F is a subgraph of G. The weighted deficiency of v with respectto F is defined byabove(v) . (g(v) — deg(v)) if deg(v) <g(v)below(v) . (deg(v)— f(v)) if deg(v) > f(v)defF(v) =gap(v) if deg(v) is in a gap0 otherwiseThe vertex weighted deficiency of F is defined by:defF= defF(v)vEVOne of our future tasks is looking for an efficient algorithm finding a subgraph F ofminimum vertex weighted deficiency, perhaps analogous to the results in [6].Chapter 4Square-Free Two-Factors4.1 IntroductionA 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 atwo-factor consists of only one cycle, then the cycle is a hamiltonian cycle. As is wellknown, the problem of finding a hamiltonian cycle of a given graph is NP-hard [30]. Theproblem of finding a two-factor is in P [18]. It is interesting to ask whether or not there isa polynomial algorithm to find a restricted two-factor, especially the following type of arestricted two-factor: a two-factor of G in which the cycles are restricted to having lengthsfrom 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 C {3, 4}. We notedalready that a polynomial algorithm exists if L = q. In the case = {3}, we call ita triangle-free two-factor and it is shown by D. Hartvigsen [31] that it can be solved inpolynomial time. The algorithm is very complicated as in the proof, but not nearly socomplicated as our algorithm in the proof. We found a few errors which we believed tobe 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 might47Chapter 4. Square-Free Two-Factors 48perhaps justify the complexity of our algorithm by the problems proximity to NP-hardproblems.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. Theweight of a subgraph F of G is the sum of weights over all edges of F. The problem isfinding a {triangle, square}-free two-factor which has maximum weight. D. Hartvigsenconjectured that the edge-weighted version of the triangle-free two-factor problem is inP [31]. The case of a two-factor without any restriction can be solved using a b-matchingalgorithm 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 studied. Unfortunately we still don’t know whether or not it is in P. We think that it’s inP. An augmenting path theorem like Berge’s augmenting theorem for 1-matching [7] hasbeen obtained. The augmenting paths are alternating and we need concern ourselveswith squares being created locally. A similar result was obtained in [32] by P. Hell, etal. If a subgraph F of G is not optimal, then there exists an augmenting walk W whichis alternating and the symmetric difference between F and any initial subwalk of W issquare-free. An augmenting path having such nice properties does not necessarily existfor L-free two-factors if L {3, 4}. In Section 4.11, we give an example showing thatthere is no augmenting path for the case L {3, 4} having such properties as in thecase L C {3,4}.Our contribution is a polynomial algorithm for finding a square-free two-factor ofG 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 wastoo complicated. However we have not discovered any impediment for the existence ofa polynomial algorithm for the general square-free two-factor problem. But even theChapter 4. Square-Free Two-Factors 49restricted case we solve seems highly complicated. We use the idea of Edmond’s blossomalgorithm [16] to find an augmenting walk. Our algorithm is more complicated than hisalgorithm and analogous to the algorithm by D. Hartvigsen [31] for the case of triangle-free. We grow a tree from each deficient vertex until two trees are joined. We get a pathjoining two deficient vertices in a shrunk graph, which is obtained from G by shrinking aset of vertices into one single vertex. To recover an augmenting walk in G correspondingto the path, we use an algorithm called Recover Algorithm. We obtain a Tutte-typetheorem which proves the nonexistence of a square-free two-factor when the algorithmstops without having found one. This theorem gives a necessary and sufficient conditionfor 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 anarbitrary 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 inthe general case where the squares need not be vertex-disjoint. Our Blossom Algorithmuses the ideas from Section 2 but does not rely on the result. Section 3 consists of twodescriptions of the Blossom Algorithm. The second one is more detailed than the firstone. A reader will find this sction essential in understanding the Blossom Algorithmpresented in Section 4. The Recover Algorithm is presented in Section 6 beginning witha brief description. Section 5 contains some useful results about the Blossom Algorithmthat tell us how to handle certain cases in the Recover Algorithm. Section 7 proves thevalidity of the Recover Algorithm and hence the Blossom Algorithm. In Section 9 theTutte-type Theorem, Theorem 4.11, is proven. It verifies the termination of the BlossomAlgorithm in Step 7 is correct. Some technical lemmas are proven in Section 8 for usein Theorem 4.11. Having completed the proof that the algorithm works correctly, wecompute its complexity in Section 10. Our algorithm runs in O(EI . 1V15) time. Weconclude with Section 11 a brief consideration of problems for further study.Chapter 4. Square-Free Two-Factors 504.2 A Berge-type TheoremIn this section, we will introduce a Berge-type augmenting walk theorem. We wish toalert the reader that in this section squares of G need not be disjoint; we are able tohandle 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 deficientvertices. For a square-free two-factor, an augmenting walk is rather complicated. Thewalk need not be a trail, since some edges can be used twice. In Figure 4.1, F is nota square-free two-factor. Let F’ = {ei, e3,e9,e8, eio}. Then FAP’ is a square-free two-factor. Note that F’ is not a walk and the reader can easily see that there is no augmentingtrail like for the case of simple two-factors. Let P =v0123970Ifwe alternately add and subtract edges along P to F starting from addition, then theresulting one is FLP’. Note that edge e2 is subtracted first and added later.Let P =v0e12 be a walk where e, = (v_1,vi). DefineFP=FU{e :iodd}\{e, :ieven}Let Cvwxy denote a square in G whose vertices in cyclic order are v, w, x and y. DenotePk the initial siibwalk of P of length k, i.e. Ph =v0e12 ekvk. Let F be a squarefree (0,2)-factor. A walk P =v0e12 ev is said to be an augmenting walk in Gwith respect to F if(i) v0 and v are deficient, i.e. deg(vo) and deg(vfl) <2,(ii) edge e2 (resp. e2i+i) is in F (resp. not in F) and edge e appears in P only oncewith a possible exception. The exception is the following: In Figure 4.2 if edge(v, w) is chosen as e21+i and any other edge in Elvwxy is not in P2, then (w, x)Chapter 4. Square-Free Two-Factors 51Figure 4.1:must be chosen as 82j+2 (by (iii)) and later (w, x) can be chosen as e2k+1 for somek > i,(iii) for any i, F P2 doesn’t have any square, and(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-freetwo-optimal subgraph which can be obtained from F by augmentations. Our augmentingChapter 4. Square-Free Two-Factors 52walk is almost a trail, except that only some edges can be in P twice. Even though it’snot alternating between edges in F and not in F, edges along P are alternately addedand subtracted. The spirit of alternation is preserved. Note that if we alternately addand subtract edges along any initial subwalk of even length, then the resulting factor issquare-free.The proof of Theorem 4.1 follows the proof idea of Theorem 4 in [32] where thetriangle-free case is also considered, though the case arguments here become more complicated.Theorem 4.1 Suppose that F is a square-free (0,2)-factor of G and non-optimal. Thenthere is an augmenting walk with respect to F.Proof. We will prove the theorem by contradiction. Assume not, that is there is noaugmenting walk with respect to F. Let F0 be such that FLFoI is minimum over allsquare-free subgraphs F0 of G with def F0 <def F. Then F0 is as close to F as possibleamong less deficient subgraphs. Without loss of generality, we can assume that F0 isa (0,2)-factor and F0 has the minimum number of vertices v with deg0(v) < deg(v)among the subgraphs described above.Since def F0 < def F, there is a vertex v0 such that defF0(vo) < defF(vo). Sincedegp(vo) deg0(vo) 2 (by Lemma 4.2), degp(vo) < deg0(vo) and there is an edge(vo,vi) e F0 \ F. Let P be a maximal walk, P = v0e1 satisfying thefollowing conditions:(i) All e21 (resp. e2) are in F0 \ F (resp. F \ F0) with some exceptions. The exceptionalcase is the following: In Dvwxy, (w, x) and (y, v) F fl F0, (x, y) E F and (v, w) F0(Figure 4.3). The edge (w, x) can be chosen as e2 and later it can be chosen as e2k+1(k>i).(ii) It doesn’t have the following eleven forbidden configurations (Figure 4.4):Chapter 4. Square-Free Two-Factors 53EF0Figure 4.3:(a) There is an edge (w, w’) E F \ P22 with w v22, (v2+i, w) E F \ (F0 U P2) and(v2,w’) E F\P2.(b) There is an edge (w, w’) F \ P2 with (v21,w) E (F fl F0) \ P2 and (v2,w’) EF\(F0UP2J.(c) There is an edge (w,w’) E F \ (F0 U P2) with w v22, (v2+i,w) and (v22,w’) E(FnF0)\P2.(d) There is an edge (w, w’) e F \ (F0 U F21) with w v22, (v2+1,w) E F \ (Fo U P21)and (v21, w’) E F0 fl P2g.(e) There is an edge (w, w’) e F \ (F0 U F21) with (v21,w) E F0 fl P2 and (v21, w’) eF\(FoUP2).(f) There is an edge (w, w’) E (F fl F0) \ P2 with w v22, (v2i,w) e F \ (F0 U P21)and (v21,w’) E(F0\F)UH21.(g) There is an edge (w,w’) E (F fl F0) \ P21 with (v21i,w) € (F0 \ F) U H21 and(v21,w’) E F \ (F0 UP21),(h) There is an edge (w, w’) e F0 fl P21 with w v22, (v2i, w) E F \ (F0 U F22) and(v21,w’) E F\P22.Chapter 4. Square-Free Two-Factors 54(i) There is an edge (w, w’) e F0 fl P2 with (v2i,w) e (F fl F0) \ P2 and (v2,w’) eF\(F0UP2).(j) There is an edge (w, w’) e F0 fl P2 with w v22, (v21,w) E F \ (F0 U P22) and(v2,w’) e (Fo\F) UH2.(k) There is an edge (w, w’) E F0 fl P2 with (v21,w) e (F0 \ F) U H2 and (v2,w’)F\(F0UP2J.where H2 is the set of edges (w, x) in a square of the type in Figure 4.3 which are in P2,as e2k for some k < i (it may be in P2 ase21+i).In Lemma 4.3 we show that F e F2, doesn’t contain a square for any i, in Lemma 4.4we show that the end vertex v, of P is deficient with respect to F and n is odd, andin Lemma 4.5 we show that F P doesn’t have any square. Thus P is an augmentingwalk, which contradicts the assumption we made at the beginning. ILemma 4.2 Suppose that F is a square-free (0,2)-factor of G which is non-optimal andF0 is as defined in Theorem 4. 1. Then deg0(v) deg(v) for every vertex v of G.Proof. Assume that there is a vertex v such that deg0(v) <deg (v). Thus there existsan edge (u, v) in F \ F0. Two cases are considered depending on whether F0 U {(u, v)}has a square or not.Case 1 F0 U {(u,v)} doesn’t have a square:Suppose that there is an edge (u,w) in F0 \ F. Let F’ = F0 U {(u,v)} \ {(u,w)}.Then def F’ def F0 and F’FI < IFoLFI, and we have a contradiction to thechoice of F0. Suppose that there exists no edge (u, w) in F0 \ F. Then deg0(u) < 2.Let F’ = F0 U {(u, v)}. Then F’ is a square-free (0,2)-factor, def F’ < def F0, andIF’AFI < IFoFI. This also contradicts the choice of F0.Chapter 4. Square-Free Two-Factors 55F-(F0UF)F-fl(might be in I)(b)(a)(d)(C)(f)(i)(e)w(h)(g)(j) (k)-VN4WW6(FflI)-(Ii— F)uH2Figure 4.4:Chapter 4. Square-Free Two-Factors 56Case 2 F0 U {(u, v)} has a square:A square in F0 U {(u, v)} must contain edge (u, v) since F0 is a square-free (0, 2)-factor.Claim 1 F0 U {(u, v)} has exactly one square.Proof. Assume that there are two squares in F0 U {(u, v)}. Let LJuvxy and Duvx’y’ bethe two squares (Figure 4.5). Then the edges (v, x), (x, y), (y, u), (v, x’), (x’, y’), and(y’, u) are in F0. Since deg0(v) <2, x = x’. Since deg0(x) 2, y= y’. This completesthe proof of Claim 1.ruFigure 4.5:Let Ouvxy be the square in F0 U {(u, v)}. At least one edge in Duvxy is not in Fsince 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’ = F0 U {(u,v)} \ {(u,y)}. Then def F’ def F0 and F’LFI < IFoAF, acontradiction to the choice of F0.Case B. (v,x) is not in F:Since deg0(v) < deg(v), there is an edge (v,w) in F \ F0 where u w. Assume thatF0 U {(v, w)} has Jvwy’x’. Then we have the configuration shown in Figure 4.6. Sincedeg0(v) <2, x x’. Since deg0(x) 2, y = y’. Similarly u = w, a contradiction thatu w. We can conclude that F0 U {(v, w)} doesn’t have any square. By an argumentsimilar to that of Case 1, we can arrive at a contradiction to the choice of F0.Chapter 4. Square-Free Two-Factors 57Case C. (x,y) is not in F:Without loss of generality, we can assume that both (v, x) and (u, y) are in F (otherwisewe have Case A or B). Two subcases are considered.(a) degF(y) = 1:Let F’ = F0 U {(u, v)} \ {(u, y) }. Then F’ is a square-free (0, 2)-factor and def F0 = def F’and IF’FI = FoFI. Since deg,(v) = deg0(v) + 1 = 2, deg/(v) = deg(v) >deg0(v). Since degI(y) deg0(y)— 1 = 1, degI(y) = deg(y) < deg0(y). Anddegl (t) = deg0(t) for every vertex t( v, y). SoI{t e V : deg,(t) < deg(t)} = I{t e V : deg0(t) < deg(t)} — 1This contradicts the choice of F0.(b) deg(y) = 2:There exists an edge (y, z) in F \ F0.Claim 2 F0 U {(u, v), (y, z)} \ {(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. ByClaim 1, (y, z) must be in the square (like in Figure 4.7).Either x’ = x or x’ = u. If x’ = x, then v = w and so it contradicts that deg0(v) <2.If x’ = u, then Dyx’wz is not in F0 U {(u, v), (y, z)} \ {(u, y)}. This completes the proofof Claim 2.Figure 4.6:Chapter 4. Square-Free Two-Factors 58Suppose that there is no edge (z, w) in F0 \ F. Then deg0(z) <2, and F’ is a square-free (0,2)-factor where F’ = F0 U {(u, v), (y, z)} \ {(u, y)}. Also def F’ <def F0 <def Fand IF’AFI < IF0A I, a contradiction to the choice of F0. So there is an edge (z,w)in F0\F. Let F’ =0U{(u,v),(y,z)} \{(u,y),(z,w)}. Then defF’ = def F0 andIF’FI < IFoFI, a contradiction to the choice of F0. •Lemma 4.3 Suppose that F is a square-free (0,2)-factor of G which is non-optimal andP is as defined in Theorem .1 (p. 52). Then F P2 doesn’t have any square.Proof Assume that F eP2 has Uvwxy. Two cases are considered depending on whetheror 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) EF0flP2,and (w,x), (x,y) and (y,v) e F\P2.(B) (v,w) and (w,x) eF0flP2,and (x,y) and (y,v) e F\P2.Figure 4.7:(C) (v, w) and (x, y) e F0 fl P2, and (w, x) and (y, v) e F \ F2:.Chapter 4. Square-Free Two-Factors 59(D) (v, w), (w, x) and (x, y) e F0 fl P2, and (y, v) E F \ P2g.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 e21 = (v, w) and k be such that e2k+1 = (w, x). Without loss ofgenerality, we can assume that j < k. Then one of the following three cases (Figure 4.8)must occur, using the fact that F0 has no square.(i) (ii) (iii)x______XFigure 4.8:(i) (x,y) and (y,v) F0:If v2k = x, then choosing (v2k, v2k+1) = (x, w) violates the forbidden configuration(e). If V2k = w and v2k+1 = x, then we have to choose V2k+2 = y (otherwise we havethe forbidden configuration (d)).(ii) (x,y) E FflF0 and (y,v) E F:If v2 = v, then choosing (v2,v2+1) = (v, w) violates the forbidden configuration(g). If v2j = w and v2+i = v, then we have to choose v2j=y (otherwise we havethe forbidden configuration (f)).(iii) (y,v) e FnF0 and (x,y) e F:It’s similar to (ii).Chapter 4. Square-Free Two-Factors 60Case C. LJvwxy is type (C):Let j be such that 82j+1 = (v, w). Without loss of generality, we can assume that(x,y) e P23 and v23 = v. If (w,x) Fo ((i) in Figure 4.9), then we have to choosev22 = x (otherwise we have the forbidden configuration (h)). If (w, x) e F0 fl F ((ii) inFigure 4.9), choosing (v2,v21) = (v, w) violates the forbidden configuration (i).(i) (ii)Figure 4.9:Case D. Dvwxy is type (D):Let j be such that e2j+l = (v, w). Without loss of generality, we can assume that (x, y) eP23. If v2j = v, then choosing (v23, v2f+1) = (v, w) violates the forbidden configuration(k). If v2j = w and v241 = v, then we have to choose v2j = y (otherwise we have theforbidden configuration (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) = e2_1 and (v, w) = e23 = e2k+1 for some j and k (j < k).If V = V2k and w = v21, then s must be v22 (we don’t have any other choicefor v2k+2). If w = V2k and v = V2k+1, then s must be V2k_1. So (s,w) must be inP, 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-FactorsFigure 4.10:61(ii)()=S WLI(iii)-----aFigure 4.11:Chapter 4. Square-Free Two-Factors 62Since y t, (v, y) must be in F \ F0. By a similar argument as above, (v, y) mustbe in P.(ii) (v,t) = (v,y):Since x s, (x, y) must be in F \ F0. Since t = v2j_2, x must be v23_3 and (x, y)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. ILemma 4.4 Suppose that F is a square-free (0,2)-factor of G which is non-optimal andP is as defined in Theorem 4.1 (p. 52). Then the end vertex v, of P is deficient withrespect to F and n is odd.Proof. Assume not. Then either v is not deficient with respect to F or n is even. Firstsuppose that n is odd, but v is not deficient with respect to F. If vertex v is not deficientwith respect to F, then deg0(v) = deg(v) = 2. The vertex v has an equal number(zero, one, two) of incident edges of F0 \ F and F \ F0. Either edge (v_1,v) is in F0 \ For (v_1,v) is in F0 fl F and used for the second time (Figure 4.3). If (v_1,v) is inF0 \F, it is clear that there is an edge e e F\ (F0 UP) which is incident to v. If (v_1,v)is in F0 fl F and used for the second time, then it is used as e2k for the first time and thenext edge e2k+1 is in F0 \ F. In this case also, there is an edge e e F \ (F0 U P) which isincident to v. So in both cases we arrive at a contradiction to the maximality of P.Now suppose that n is even, i.e. n = 2i for some i. Then either(i) there is no edge e E (F0 \ (F U P)) U which is incident to v, or(ii) each choice of (v2,v21) yields one of the forbidden configurations in Figure 4.4Chapter 4. Square-Free Two-Factors 63where H1 is a set of edges in H2 which is in P2 once as e2k, but not as e2i+i.Since deg0(vfl) deg(v) by Lemma 4.2, the number of edges in F0 \ F incident tov is greater than that in F \ F0. So there exists an edge e E (F0 \ (F U F)) U H whichis incident to v. Case (i) cannot occur, so it must be case (ii). That is, for each choiceof (v2,v2i+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 v22 = w and v22=by (a), (c), (d), (f), (h) or (j).Claim 1 There is at least one choice of (v2,v2+i) which doesn’t lead to situation (A).Proof. Suppose that for a choice v2+ = v, there is an edge (w, w’) which violates (b).We will show that (v2_1,) is in F \ F0. Assume that (v2_1,) F \ F0. Then(v2_1,v21) is in a square of the type in Figure 4.3 and is in F fl F0. Let Dxyv2_1vbe the square (Figure 4.12 (i)). Since deg(v2) < 2, x = w’. Similarly y = w. Sincedeg0w 2, v2_1 = v. Since v2_1 cannot be a choice of v21, (v2_i,v) must be inF \ F0. Since there are two edges (w’, v2) and (v2_1,v2) in F \ F0 incident to v2, thereis a vertex v’( v) with (v2, v’) e F0 \ F. The edge (v2, v’) must not be in F, so canbe a choice ofv21. Now we will show that the choice V2j1 = v’ doesn’t lead to (A).Assume that it does. Let (y, y’) be the edge which violates (b), (e), (g), (i), or (k) by thechoice v21 = v’ (Figure 4.12 (ii)). Then (v2, y’) must be in F \ (F0 U F). Since onlyone edge in F \ F is incident to v2, y’ = w’. In all of the cases, (y, y’) must be in F F.Since (w, w’), (y, y’) and (v2,w’) are in F P and incident to w’(= y’), y = w. ThusDv2y’y ’ must be in case (b), (e) or (g). In case (b) or (e), (y, y’), (y, v’) and (w, v) mustbe in F F and incident to w(= y), and so v = v’. In case (g), (y, y’), (y, v’) and (w, v)are in F0, so v = v’. In all of the cases, we arrive at a contradiction that v v’.Chapter 4. Square-Free Two-Factors 64By a similar argument, we can show that if for some choice of (v2,v2+1) there is anedge (w, w’) which violates (e), (g), (i) or (k), then there is another choice of (v2,v2+1)which doesn’t lead to (A). This completes the proof of Claim 1.Let v be a vertex which can be a choice ofv21. By Claim 1, we can assume that thechoice v21 = v doesn’t lead to (A).Claim 2 If for the choice v21 = v there is some edge (w, w’) which forces v2+ = wby (c) or (d), then situation (B) doesn’t occur (that is, no other vertex is required to bev2+).Proof. Suppose that w is required to be v2+ by (c). Assume that there is another vertexy required to be v22 (Figure 4.13). Since (v2_1,v2) e F, (v2,w’) and (v2, v) are onlyedges in (F \ F) U Fo incident to v2. So w’ y’. Since (y, y’) must be in F $ F, w = yand a contradiction to the assumption that w y.When w is required to be v22 by (d), we can show that there is no other vertexrequired to be v22 by a similar argument. This completes the proof of Claim 2.Claim 3 If the choice v21 = v leads to (B), then there is another choice ofv21 whichleads to neither (A) nor (B).(i) (ii)Figure 4.12:Chapter 4. Square-Free Two-Factors 65PFigure 4.13:Proof. Without loss of generality, we can assume that neither (w, w’) nor (y, y’) forces= w and v22= y by (c) or (d). Here we will consider only the case that w isrequired to be v22 by (a). By a similar argument, the other cases can be verified. Twocases can be considered depending on whether (v2,w’) e F0 or not.Casel. (v2,w’)EFflFo:This configuration is shown in Figure 4.14. Since (v2,w’) and (v2, v) are the only edgesin (F \ F) U Fo incident to v2, = y’. Since (y, y’) must be in F e F, w = y.__Figure 4.14:Case 2. (v2,w’) e F \ F0:If w’= y’, then we arrives the same conclusion as in Case 1. Suppose that w’ y’. Then(v2, y’) must be in F0 \ F. So Dvv2y’y must be in case (f) or (j). Suppose that it’s case(f). Then (v21, y’) g P (since (v2_1,v21) E F and (v2,w’) F \ P). Now we will showthat we can choose v21= y’, i.e. the choice v2j1 = y’ leads to neither (A) nor (B).Assume that we cannot choose v2÷ = y’. Let Dv2u’uy’ be any square in cases (a)’(k)Chapter 4. Square-Free Two-Factors 66(Figure 4.15). Since (v2_i,v2) e F fl F, (u2,v), (v2,w’) and (v2, y’) are the only edgesin (F \ F) U Fo incident to v21. So u’ is either v or w’.(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 v21=doesn’t lead to any square in cases (a)(k). Similarly for the case that u= y.(ii) u’ = w’ ((ii) in Figure 4.16):Since (u, u’) is in F P, a = w. If (u, y’) E F \ F, then y’ = v and a contradiction.Suppose that (u, y’) E F0. Then u = y (since (v2, y’) and (y, y’) are in F0 andincident to y’). So w = y and we arrive another contradiction.If Ovv2yy’ is in case (j), we will arrive the same conclusion. This completes the proof ofClaim 3.The proof of Lemma 4.4 is completed. ILemma 4.5 Suppose that F is a square-free (0, 2)-factor of G which is non-optimal andF is as defined in Theorem 4.1 (p. 52). Then F P doesn’t contain a square.Figure 4.15:Proof It can be proven by a similar argument as in Lemma 4.3. IChapter 4. Square-Free Two-Factors 67(i) (ii)Figure 4.16:4.3 A Preview of the Blossom AlgorithmOur Blossom Algorithm either finds a square-free two-factor of a given graph G or provesthat there is none. In this section and subsequent sections we impose the restriction thatthe squares of G are vertex disjoint. In this section, we will give a rough outline of thealgorithm 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 fromeach root. They form a forest F. Later we find that it’s different from a forest in otherblossom algorithms. In others, trees are vertex-disjoint, but not in ours. We abuse thenotation slightly and still call it a forest. If we find an augmenting walk F, then weaugment F by alternately adding and subtracting edges along P to F (Step 6). If newF 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 Algorithmu,=Chapter 4. Square-Free Two-Factors 68and others arises in the procedure of finding an augmenting walk, i.e. tree-growing. OurBlossom Algorithm is more complicated than other blossom algorithms. An edge canbe used twice and there are four possible labels for a vertex, more labels than in otherblossom 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 simultaneously. Start with F = {all deficient vertices} and add vertices and edges to F as treesgrow. When a vertex v is added to F, v is given one of the following labels: dummyodd, odd, or even. A vertex v is even if v is added to F with a matched edge. A vertexv is odd if v is added to F with an unmatched edge and either matched edge incident tov can be added to F. A vertex v is dummy odd if v is added to F with an unmatchededge 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 thebeginning 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 areal 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, wedeal with the current shrunk graph which is obtained from G by shrinking all currentpseudovertices.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 nosuch 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 ordummy odd depending on whether or not there is a square of G where all its unmatchededges belong to F,, U {(v, w)} but not any of its matched edges. Note that we check thisChapter 4. Square-Free Two-Factors 69in the current shrunk graph, not in G. We don’t need to concern ourselves with the edgesinside a pseudovertex. This is the power of the blossom approach. If there is no suchsquare of G for P, U {(v, w)} in the shrunk graph, then using the Recover Algorithm wecan recover an alternating walk P in G from a deficient vertex to w ending with the edge(v, w) such that P e F doesn’t have a square. To recover an alternating walk in G, wewill 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 (seeFigure 4.45i-.s4.50). If there is no such square, let w be odd and vertices which are joinedto w by a matched edge be even. If there is such a square (like Figure 4.17), let w bedummy odd and only the vertex which is joined to w by the matched edge in the squarebe even (in Figure 4.17 only u is even, not u’).(i) (ii)a pseudovertexFigure 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 differenttrees, i.e. the edge (v, w) joins two trees, we can find an augmenting walk (there aresome exceptions where we cannot have an augmenting walk and they are described inStep 4.5). If v and w are in the same tree, then adding the edge (v, w) to .T forms a cyclein F and we shrink the set of vertices in the cycle into one vertex, i.e. a pseudovertex,Chapter 4. Square-Free Two-Factors 70in (there are some exceptions where the set of vertices cannot be shrunk and they aredescribed in Step 4.5). Some vertices in the cycle might be pseudovertices. There may besome special vertices in a pseudovertex as follows: If there is a square of G where all itsunmatched edges belong to P but not any of its matched edges where P is the directedpath in F from a root to v ending with an unmatched edge, then call such a vertex v adummy vertex.After forming a pseudovertex, let an end vertex of a matched edge, which is incidentto any nondummy vertex in the pseudovertex, be even (Step 5e). If any matched edgejoins any nondummy vertex in the pseudovertex to an odd vertex or a nondummy vertexin 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. InFigure 4.19, we start growing a tree from vertex r. If the vertices v and w are evenwith predecessors u and t respectively, then we cannot form a pseudovertex using theedge e. This is one of the cases in which a pseudovertex cannot be formed using an edgejoining two vertices which are even or pseudovertices. Later a pseudovertex o is formedusing one of the edges e (i = 1, 2, 3) and contains all of the vertices inside the markedcircle. Now we can breakthrough along the edge f and find an augmenting walk (fromthe Recover Algorithm). Note that we have to use the edge e’ twice to breakthroughalong f. Moreover any augmenting walk must use the edge e’ twice. This indicates whyany algorithm for the problem must handle this possibility.In Figure 4.20, we start growing a tree from vertex r. First the pseudovertex whichis marked by the smaller circle is formed. The vertex v is dummy. (Let P be the pathstarting from r to v through vi’s. The reader can see that F P contains Dv2v3v.) Sothe edge f cannot be added to F. Later another pseudovertex, which is marked by thebigger circle, is formed containing the previous pseudovertex and v becomes no longerChapter 4. Square-Free Two-Factors 71o : even•:dummy odd• dummy in• apseudoveexa pseudovertexroot rootFigure 4.18: A forest .TChapter 4. Square-Free Two-Factors 72Figure 4.19:Chapter 4. Square-Free Two-Factors 73•0SFigure 4.20:Chapter 4. Square-Free Two-Factors 74dummy. 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 usingblossoms, it seems unlikely that you could specify that order in the algorithm. We hopethese two examples help to explain the complexity of our algorithm. We believe thecomplexity is a unavoidable outcome of the blossom approach.Above, we have given a rough description of our Blossom Algorithm and examplesshowing why the algorithm is so complicated. Note that if G has no square, then ouralgorithm is the standard blossom algorithm. Now we will describe the difference betweenour Blossom Algorithm and others and some terminology which may help a reader tounderstand the algorithm in the next section.(i) A dummy odd vertex v may be later reached by another edge in a tree-growing. Ifit is a matched edge, then v becomes even. If it is an unmatched edge, then there isno square of G containing the edge since we deal here with a graph whose squares arevertex-disjoint. So v becomes odd and the vertex (u’ in Figure 4.17) prevented frombeing even now becomes even.(ii) A dummy vertex v in a pseudovertex may be reached by an unmatched edge later ina 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 aredescribed 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 aneven label with P = v, w, x). Second for either y or x’. If w becomes even, then y iseven with P, = 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 asmall change in F, we can avoid using e twice in P (the details are in Step 4 of theRecover Algorithm).Chapter 4. Square-Free Two-Factors 75(iv) Trees in .T are stored using the notation p(v) = w to denote that w is a predecessorof v in a tree. A vertex v may have two predecessors. In this case, either one is chosento be p(v). Suppose that v has two predecessors w and w’ and w is chosen to be p(v). Ifvertex x has v as its predecessor and w is not in P, i.e. w’ is in P, then P = (P’,v,x)is recorded instead of p(x) = v. For example, suppose that in Figure 4.22 first v becomesdummy odd (v has predecessor w’) and x becomes even, and later v becomes odd (w isanother 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 = (P(), v) in a recursive way, if no remark isgiven (such as P, = (Pa, x, v)). In the algorithm, we use the notation root(v) to denotethe root of the tree in which v lies.Figure 4.21Chapter 4. Square-Free Two-Factors 76Here we want to make a short note about choosing one predecessor as p(v) when v hastwo predecessors. Suppose that v has two predecessors w and w’. Then v is in a squareof G (see Steps 4.1 and 4.3) and one predecessor is in P for only one successor x of vwhich 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 becomesodd or even, then v has two predecessors in F. These two predecessors might be fromdifferent trees. In F trees are not vertex-disjoint ((i) in Figure 4.23). In (iii), it was notedthat some edge can be used twice in F. An edge might be in two different trees, so inF trees are not edge-disjoint either. If two predecessors of a vertex are in the same treeor 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 usedtwice in F into two, then F has a usual forest structure, i.e. trees are vertex-disjointand edge-disjoint and each tree fits the usual definition of a tree ((ii) in Figure 4.23). Wedon’t split vertices or edges explicitly in the algorithm (there are some complications foredges 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 twovertices v and w which are even or a pseudovertex and both are in the same tree, thenadding (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),p2b ) are common edges on P, and P from v (resp. w) to its root.In a usual blossom algorithm, the base b is defined as the first common vertex on thepaths 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 Pand P’ in F from roots to v (Figure 4.25 (i)). If some part of P including v is shrunkChapter 4. Square-Free Two-Factors 77Figure 4.23:(i) (ii)rootbroot root(ii)I(iii)(p/% IFigure 4.24:Chapter 4. Square-Free Two-Factors 78into 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 maybe shrunk into a pseudovertex, like Figure 4.25 (ii). Two pseudovertices are said to beattached to each other at vertex v. If two pseudovertices are attached to each other, formanother pseudovertex including the two pseudovertices.(ii)- -IS. —Oroot(viii) Suppose that an edge e is used twice in F. Then there are two directed paths Pand F’ from roots to the end vertices of e (Figure 4.26). If some part of P including e isshrunk into a pseudovertex o, then in P the portion which is in o is replaced by o. Butkeep 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(I) S/IIIFigure 4.25:rootF//I!0rootarootChapter 4. Square-Free Two-Factorsroot79(i) (ii)‘4’arootroot-ProotFigure 4.26:jtpnsaoX1AUpJOpW0IjTci‘llUt3U1JU’LSt)J)I{U)1{J‘ainbsooiusop‘jjj°xaoAoptIosdpsutopoueptpopouuopMijtou‘qdiijunnjsijpou.ioaqUUflpousaLvnbsvsvaijprsSttuq‘spppwsjoAuounqouopqspappwuns!jpaiaqjo91nbsustaiaipueuttjedpopatpestjj(x)uiqjouopO‘12 ’JU0tWOUOt{OSflOMOSSflJUt05 WpaUOUeTfJOffl2utsnxaoAopnsde111103OM“!°“-‘°SP-To‘JU0tOUT{OSU°Mfip9yvfiiUtIteUItUTpflSJfROfltMMXpue0sM1aAopUaSdoojuiutoCopiaoustaETf‘seStT{UIXpue0UIUTThUOxaaaopnsdioueuuojuq‘xx1AopnSd31(gdjs)0OpoipeStxx1Aopnsd‘ippo‘punojS0xioAopnosdioje‘jdurexiOUeUtSflOUVtAeMpaepuesUtouxoJoAopnosde111103o‘uiijuOeoquntpsmSUOtIUAy(xt):IJt!T100.1100.1IIS—IpaULIOjIeStJaAopnsdoaqj08sJoPeci-0MJ 1arci-arvnbSiChapter 4. Square-Free Two-Factors 81doesn’t have a square. At various times in the algorithm we call some square a blockingsquare if some P, creates a square, i.e. the augmentation along path P,, is blocked by thesquare. 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 atthis 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 withp(x)= y. Later it becomes useful if a pseudovertex containing the edge (y, v) is formed.Figure 4.28:If we pick up an edge which is currently useless, store the edge in the set CUE(currentlyuseless edges) to prevent picking it up repeatedly in Step 2. Whenever any change ismade in F, empty the set CUE and edges in this set become available again.4.4 The Blossom AlgorithmIn this section, we will present our Blossom Algorithm. We wish to remind the readerthat set E* consists of edges which can be used twice ((iii) on p. 74) and set CUE consistsof currently useless edges ((xi) on p. 81).(i) (ii)/Chapter 4. Square-Free Two-Factors 82Blossom AlgorithmStep 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 vto a non-odd vertex w:e = (v,w) e 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 inTheorem 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 apseudovertex, 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 toChapter 4. Square-Free Two-Factors 83Step 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 matchededges. If no such a S exists, go to Step 4.4. Otherwise, i.e. the augmentation alongP U {e} (resp. P U {e, (w,p(w))}, P U {e}, or P U {e, (v,p(v))}) is blocked, checkwhether (w,p(w)) (resp. (p(w),p2w)), (v,p(v)), or (p(v),p2v) ) is a matched edge andbelongs 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 u1 and u2 be the ends of twomatched edges incident with w (ui and u2 must not be odd). For i = 1,2, if u, is neithereven nor a pseudovertex, then let it be even, p(u) = w, and E =— {(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 unmatchededge (u,x),(ii) (u,x) e E*, and(iii) xis dummy odd with P = (Pq,’u,x),then let x be odd with P = (Pr, w, ‘U, x), and no longer call Dwuxz a blocking square.Let E = E — {(w, u)} and E* = — {(u, x)}. Note that y is neither odd nornondummy in a pseudovertex. If y is neither even nor dummy in a pseudovertex (i.e. yis F or dummy odd), then let y be even, p(y) = x and E = E — {(x, y)}.Chapter 4. Square-Free Two-Factors 84Reset CUE = and go to Step 2.Step 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 = (P,v,w),= E — {(x,v)}, and E = E— {(v,w)}. If u’, which is the end vertex of theother matched edge incident with w, is not even, then let u’ be even, p(u’) = w, andE = E—{(w,u’)}. Reset CUE = and go to Step 2.In cases (i) and (ii), if u is not even, then let w be dummy odd, p(w) = v, andE = E — {(v,w)}. Let u be even, P = (P,w,’u), and E = E — {(w,u)}. CallFigure 4.29:Chapter 4. Square-Free Two-Factors 85Dvwux a blocking square. Additionally in case (i), let E* = E* U {(v, w)}. ResetCUE = and go to Step 2.In case (iii) and the case that in (ii) u is even, let CUE = CUEu {(v,w)} and go toStep 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 beodd, p(w) = v, and E+ = E+ — {(v, w)}. If u’ is not even, then let u’ be even, p(u’) =and E = E — {(u’,w)}. Reset CUE = q and go to Step 2.Step 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 whetheror 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)),. ,(p’1w),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) inFigure 4.36).Case 2. root(v) = root(w)Let b be the first vertex such that (b, p(b)) and (p (b),p2 (b)) are common edges on the pathsP, 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 withno matched edge. Check whether a square S of G exists where all its unmatched edgesbelong to P, U {e, (w,p(w)),... , (p’1w),p’(w))} but not any of its matched edges. IfChapter 4. Square-Free Two-Factors 86I66root (v) root (w)(x,y) €F(z,q)eF,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 inFigure 4.32 where another vertex y is deficient and P,, = (b, x, y, z) is part of one of thepaths P, or P, yet not both of them. Reset P = (y,x,b,z). So root(v) root(w). Goto Case 1.Figure 432:I II I(c) Suppose that root(v) = root(w) and the assumptions of cases (a) and (b) do not hold.Chapter 4. Square-Free Two-Factors 87Then 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 inFigure 4.34. Let CUE = CUE U {(v, w)} and go to Step 2. If only one of x or y is evenand 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 noteven, 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 ablocking 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 — {(v,w)}, and E = E— — {(x,v)}. CallUvwxy a blocking square. Reset CUE = and go to Step 2. Otherwise, i.e. x is evenor 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 iseven or a pseudovertex, then let E* = E*— {(v, w)} and go to Step 2. If y is odd, thengo 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*— {(v,w)} and E = E- — {(w,y)}. Reset CUE = qS and goto Step 2.Chapter 4. Square-Free Two-Factors,(v,w) is any unmatched edge88/(x,y) F(ii) (iii)—/I ‘II JI/I Io o(x,y)F p(v)x p(w)y(vi)(vii)_ S, ‘(i)(v)p(y)x p(w)x(v,y)€ II:?(vi)—.5.— —p(y)4x p(w)*xI SIFigure 4.33:Chapter 4. Square-Free Two-Factors(1)rJYp(y)=v p(x)=wFigure 4.34:p(y)=v p(x)=y89UFigure 4.35:Chapter 4. Square-Free Two-Factors 90Step 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 ofG exists where all its unmatched edges belong to P, U {e, (w, p(w)),... , (pk_l (w) ,k (w)) }but not any of its matched edges (p1(w) = v). Interchange the roles of v and w, and doit again. If any square is found, then it is one of the squares xyzq shown in Figure 4.36.(ii) — — — —.—(I)SSIIIISIIChapter 4. Square-Free Two-Factors(iii)III SI SI SI SI SI SI SI II II I91(iv),SI SI S(v) (vi) (vii)(viii) (ix)Figure 4.36:Chapter 4. Square-Free Two-Factors 92Step 5b. (Let some of the squares found in Step 5a be blocking squares and turn someof 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 (allof 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. Supposethat y is even and p(y) = z. Then (v,w) is either (q,x) or (x,y). Let CUE = CUE U{(v, w)} and go to Step 2. Suppose that y is even and p(y) z. Then (v, w) is (z, q) andp(z)= y. Reset p(z) = q, E = E U {(y,z)} \ {(z,q)}, and E = E U {(x,y)}. LetCUE = q and go to Step 2. Suppose that y is dummy odd. Then (v,w) is (z,q) andp(z)= y. Reset p(z) = q, E = E \ {(z,q)}, and E = E U {(x,y)}. Let y be evenand p(y) = z. Reset CUE and go to Step 2. If y is odd or a pseudovertex, thencontinue 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. Supposethat x is even and p(x)= y. Then (v,w) is (q,x). Let CUE = CUE U {(v,w)} and goto Step 2. Suppose that x is even and p(x) y. Then (v, w) is either (y, z) or (z, q). Letp(z) = q and p(y) = z if not. Let E = E U {(x, y)}\{(v, w)} and E = E U {(q, x)}.Reset CUE = çb and go to Step 2. Suppose that x is dummy odd. Then (v, w) iseither (y, z) or (z, q). Let p(z) = q and p(y) = z if not. Let E = E \ {(v, w)} andE = E U {(q, x)}. Let x be even and p(z)= y. Reset CUE = and go to Step 2. If yis odd or a pseudovertex, then continue this step (all of x, y, z and q will be shrunk intoone vertex).If a square of type (viii) is present, then choose one appearing for the smallest k, andreset P, = (Pq, x, y). Go to the beginning of Step 5 with b = q.In cases (i) (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) whereChapter 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 v and from b to w, respectively.In cases (ix) and (x), x is not dummy and Dxyzq is not a blocking square. We canreach x through (Ps, q, x) in (vii) (resp. (Pr, z, q, x) in (viii)). If there exists a blockingsquare of type (vii) and (viii), then no longer is it a blocking square and x dummy. If xis 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 thepath 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, thenlet o be a root. Otherwise, let P0 = 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 avertex in a pseudovertex in 0) belongs to 0, then both ends are even. No longer call xa 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 (xcan 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 isdeficient, 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 adummy 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 Dyxzq ablocking square. If q is dummy odd, let q be odd and E = E* — {(z,q)} in (i). LetChapter 4. Square-Free Two-Factors 94u(r/ y) be the end of the matched edge which is incident with q. If u is not even, thenlet u be even with P = (P0, q, u). If q is even, then go to Step 4.4 with Pm,, = (z, q).(i) (ii)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 anondummy vertex in another pseudovertex x where (t, x) P, and (t, x) P0, then, ifnot in the special case below, go to Step 4.4 with Prn,, = (x, o). The special case is thatP = (Pu, z, x) and P0 = (Ps, y, o) are in a blocking square as in Figure 4.38. Supposethat y and z are pseudovertices. Then (y, z) is neither the stem of y nor of z. Letp(o) = y, p(x) = z and E = E U {(y, z)}. Go to Step 4.4 with F,,,,, = (x, o). If eithery or z, say y, is a pseudovertex, then no longer call Dxzyt a blocking square, and letp(o) y, p(x) = o, E = E U {(y, z)} and E = E— U {(x, z)} \ {(t, x)}. If both y andz are real vertices, then let p(x) = o and E = E U {(x,z)} \ {(t,x)}If there is any unmatched edge in F from a vertex t in 0 to an even vertex or anotherpseudovertex x where (t,x) g P3,, and (t,x) g F0, then go to Step 3.2 with v = o andw = x.,Chapter 4. Square-Free Two-Factors 95Figure 4.38:If there is any pseudovertex x attached to 0, i.e. a vertex in x is on P or Ps,, thengo to Step 4.4 with = (x,o).For a vertex z which is either dummy odd or not in .F, and joined to a nondummyvertex in o by a matched edge, let x be even and p(x) = o. For a vertex x of,T such thatp(x) e 0, let p(x) = o. Note that p(x) 0 in the following case: p(x) = y and y 0,but P \ {(x, y)} is different from P6 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 tothis one is Step 4, then go to Step 2 in the Recover Algorithm withF = P U {e, (w,p(w)), (p(w) ,p2 (w)),... , (p’(w),p(w))}where p(w) = root(w) and look for an alternating walk ending at root(w) with anunmatched edge. If the previous step is Step 5, then some deficient vertex x which wasdummy previously became nondummy and so we go to Step 2 in the Recover Algorithmwith P = P0 and look for an alternating walk ending at x with an unmatched edge. Atthe end of the Recover Algorithm we get an alternating walk F, and we reset F = F Pand go to Step 1.IChapter 4. Square-Free Two-Factors 96Step 7. (No square-free two-factor)This step is for the proof of Theorem 4.11. If CUE = , then STOP. Otherwise, for eache = (v, w) E CUE do the following: If either v or w (say v) is .1, then there existsa square S of G where all of its unmatched edges belong to F,, U {e} but not any of itsmatched edges; let S be a blocking square, w be dummy odd and p(w) = v. Otherwise,i.e. each of v and w is even or is a pseudovertex and then there exists a square S of Gwhere all its unmatched edges belong to F,, U {e} (resp. P, U {e, (w,p(w))}, P,,, U {e}, orF,,, U {e, (v,p(v))}) but not any of its matched edges. Let S be a blocking square. NowSTOP.4.5 Some notes for the Recover AlgorithmIn Step 5 in the Blossom Algorithm, we stated that if any edge in P or P is incident toa dummy vertex x or its mate z in another pseudovertex, then x is no longer a dummyvertex. In this section, we will prove the statement and make some notes which are usefulfor the next two sections.Theorem 4.6 In Step 5, if any edge f in P,,b or Ps,, i.e. (pk_l(v), pk(v)) or (p1(w), pk(w)),is incident to a dummy vertex x or its mate z in another pseudovertex, then x is no longera dummy vertex.Proof. Since x is dummy, it belongs to a blocking square xyzq of type (i) (iv) inFigure 4.36 on p. 91. Without loss of generality, we can suppose that f is in P,,b. Lett be the end of f 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’. Wewill distinguish cases where LJxyzq is of type (i), (ii), (iii) or (iv). In each case we willdistinguish between the cases where f is incident to x or z. Figure 4.39 may help tounderstand the following.Chapter 4. Square-Free Two-Factors 97Case A Dxyzq is type (i) and f is incident to x:If f is unmatched, then u is even by P = (Pt, x, u). Suppose that f is matched. Since xis dummy, x’ is not in P,. Then there exists an unmatched edge in P which is incidentto 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 andnot (z, q). Without loss of generality, we can assume that f is such an edge. Then u iseven 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 = (i,j) be the edge nextto (z, q) in P. Then either i or j belongs to x’, say i. If (x, y) is in P (i.e. P3 =(P,q,x,y,... ,i,j)), then ‘u is even by (P,v,p(v),p2v),... ,j,j,... ,y,x,u). Otherwise,u is even by (P,v,p(v),p2(v),... ,j,(P)’,z,y,x,u). See (d)-(2) in Figure 4.39.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 ofChapter 4. Square-Free Two-Factors 98generality, we can assume that f 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 ior 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. Notethat both (q, z) and (z, y) cannot belong to P, (otherwise, z belongs to a pseudovertexand x is not dummy). Without loss of generality, we can assume that (z, y) g P,. Thenit is even by P = (Pt,z,y,.x,u).The proof of Theorem 4.6 is completed. I(h)(a) (b)xChapter 4. Square-Free Two-Factors 99(d)(i)(e) (g) (2)x,Figure 4.39:Chapter 4. Square-Free Two-Factors 100In the Blossom Algorithm, ancestors of some vertex are sometimes changed. It happens in the following cases (Figure 4.40)(a) (b) (c)(d) (f)FcL—i’(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.F-‘IIIa a a a(e)Figure 4.40:(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 changedfrom (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. Incases (a) and (b), (v, w) remains as the stem of v. We use these comments in Theorem 4.8.4.6 The Recover AlgorithmIn this section, we give an algorithm to recover an alternating walk in G corresponding toa directed path in ..F. If v is even (resp. (dummy)odd), then the algorithm will producean alternating walk P from root(v) to v ending with a matched edge (resp. an unmatchededge). If v is in a pseudovertex, then the algorithm can recover alternating walks endingwith both a matched edge and an unmatched edge. The subgraph F P doesn’t haveany square, except when either v is dummy odd or v is a dummy vertex in a pseudovertexand P ends with an unmatched edge. If it is in the latter cases, then there is only onesquare in F P and the square contains v.Our Recover Algorithm follows the usual procedure in blossom algorithms with somedifferences. 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 Pand then we make a small change in P to get rid of the square (Steps 5 and 6). InChapter 4. Square-Free Two-Factors 102Step 4, we make a change in P if the same edge appears in P twice. In the usual blossomalgorithm, the order of expanding pseudovertices is not important, but it is important inour algorithm. We order our choice of a pseudovertex to be expanded according to therule which is stated at the beginning of Step 3. Otherwise, we might get a square whichwe 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 toour algorithm running in exponential time.During the algorithm, we will deal with the graph obtained from G by shrinkingpseudovertices in the current P. As the algorithm progresses, pseudovertices in P areexpanded. When we expand a pseudovertex o, the pseudovertices in o but not in Pwill be opened, i.e. each of those pseudovertices will be replaced by the subgraph of Ginduced by the set of vertices in the pseudovertex. During the Recover Algorithm, wewill 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 103Otherwise 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 createa square (see Step 4.2 in Blossom algorithm). Add (va, w) and w to the end of ]3Step 2.2 (v is a pseudovertex)Recall the structure Q(v) from the Blossom Algorithm. Suppose that v. is formed bythe 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):bf1u . . . n,1fubgiwi...wm_igmwmwhere some ui’s and wi’s might be pseudovertices. The vertex v is u, w, or belongs toone of u or w3. Say that v is n or belongs to u.If v had been dummy previously and became nondummy when v was formed andwe look for a walk ending at v with an unmatched edge, then Theorem 4.6 tells how tohandle 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 endingat v with an unmatched edge, do the following: In cases (i)(iv) in Figure 4.36, thereexists w in v such that (v, w) is matched. Either f or f+i is (v, w) and the other isunmatched. If ft (resp. f+i) is (v, w), letP = v0e1 v_iebg1w . . wm_igmwmeuifiui_i . .. f+iufu-1(resp. P = voe1v1 . . . v_jebf1n. u_ifuf+iuj+i ). In case (v) in Figure 4.36, thereis no such w. From now on look for an alternating walk ending at q or y with a matchededge. At the end of the algorithm, add (q, x) or (y, x) respectively to P to obtain theChapter 4. Square-Free Two-Factors 104desired walk. Without loss of generality, we can choose q and assume that q is ‘a1 or inu. LetP v0e1 •v_1ebgiw • • wm_igmwmeuifiui_i .. . f’a2f’a1If u is a real vertex which is not dummy and we look for a walk ending at v with amatched edge, then choose f or f2+i which is matched, say f. LetP = v0e1 v_iebf1u u_f2.Similarly for the case that ‘u is a real vertex and we look for a walk ending at v with anunmatched edge.If u is a pseudovertex, then letP = v0e1 v_iebf1u • .and rewrite P using the notation of (*). Do Steps 4’-6 and go to the beginning ofStep 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 tov1 for a pseudovertex satisfying the following:(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), theno 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 105iiFigure 4.41:Recall the structure Q(vk) from the Blossom Algorithm and suppose that Vk is formedby the following two dipaths and edge e:bf1u •u1_fbgiwi . . wm_igmwmIf neither ek nor ek+l is the stem of ‘Uk, then do Step 7. Say that ek is the stem of Vk andek+l hits vk at u. Similarly for the case that ek+l is the stem of Vk.If u is a real vertex and ek+l is matched (resp. unmatched), then choose f, or f+iwhich is unmatched (resp. matched). If f, (resp. f+i) is chosen, letP =v0e1 vk_lekbf1u • u1_1fuek+1vk+l(respectively,P = v0e1• vk_lekbglwl . wm_lgmwmeulf1u1_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 f,or f+i, say f, is unmatched and belongs to a square of G (i.e. case (i) in Figure 4.42),then letP = v0e1 vk_lekbglwl Wml9mWmeuifiui_1... u1+1f+luek+1vk v_iev.Chapter 4. Square-Free Two-Factors 106Otherwise (case (ii) in Figure 4.42), choose f or f+i which is unmatched and let P bechosen in the same way as above.(I) (ii)S I I ‘. ,II Vk — —— _c?/ I Vk .-.——oFigure 4.42:If u is a pseudovertex, ek+1 is matched, and ek+1 hits u at a vertex x which hadbeen dummy previously and became nondummy when pseudovertex vk was formed, thenTheorem 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)whereF’ = v0e1 vk_lekbflul . ..then letP = v0e1 vk_lekbglwl wm_igmwmeu,fiu1_ 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 letP = v0e1 vk_lekbflul u1_1fuek+1vk+1 v_iev.Chapter 4. Square-Free Two-Factors 107(I) (ii)_____ -‘‘S. f+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 frommatched to unmatched, one of the cases in Figure 4.44 must occur.In case (i), let ek = (q,z), Vk = z, and ek+1 = (z,y) in P.In case (ii), let ek = (y,z), Vk = z, and ek+1 = (z,q) in P.Go to Step 5.Step 5.If an unmatched edge (z, q) in P belongs to a square of the type in Figure 4.41 and noneof (z, y), (q, x) and (x, y) is in P, then the square is one of the cases in Figure 4.45. Herewe assume that (x, y) is not in P if (x, y) is in a pseudovertex in P which has not beenexpanded yet.k÷1Chapter 4. Square-Free Two-Factors 108(i) (ii)Figure 4.44:All of x, y, z and q belong to a pseudovertex o, and x and y belong to a pseudovertexin o. Neither (y, z) nor (q, x) is the stem of the pseudovertex containing x and y, exceptcase (iv). In case (iv), (q, x) is the stem of the pseudovertex. Assume that o is formedby the following two dipaths and edge e:bf1u . . .u1_fbgiwi..wm_igwand 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.2or 3 before we started the current steps 4’-..’6. In cases (v) and (vi), a pseudovertex in ocontaining 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 orsome uh (1 h i) or otherwise. First suppose that z and q are in neither b nor anyh (1 h i). Note that b has not been expanded yet if b is a pseudovertex. Let k beChapter 4. Square-Free Two-Factors 109(iv)//(v)V(vi)/UI///Figure 4.45: >pChapter 4. Square-Free Two-Factors 110such that 13k = b and j(> k) be such that e3 = (z,q) in P. SetP = v0e1 ekvkflul.. fue’qev. • ev2where e’ = (x, q). See (i) in Figure 4.48. If z and q are in b or some h (1 h < i), oneof the cases in Figure 4.46 must occur (we subdivide it into two subcases depending onwhether or not there is some vd in P which is the end vertex in ‘11h of fh+1 and vd appearsafter (z,q) in P):/Figure 4.46:In the both cases, uh or a pseudovertex in u is expanded in eitherfor some k, fh = ek. Let j(> k) be such that e = (z, q). In (a), setP = v0e1 ekuhfh+luh+1. . fue’zejvi . .Step 2.2 or 3 andwhere e’=(y, z). In (b), there is some Vd which is the end vertex in uh of fh+1 or apseudovertex containing it. LetP =v0e1 ekuhe’u1fu_1f1 . .. fh+lvded+lvd+1 eV(a) ,,---- - -/where e’ = (y,z). See Figure 4.47Chapter 4. Square-Free Two-Factors 111/In case (ii), if b is a pseudovertex then b has not yet been expanded. Let k be suchthat vk = b and j(> k) be such that e3 = (z, q). SetP =v0e1 ekvkflul fue’zevwhere e’ = (y,z). Note that z and q cannot be in any Uh (1 h < i) (edge (z,q) is in .Tafter a pseudovertex containing x and y is formed, so (z, q) is not in See Figure 4.48(ii).Case (iii) is similar to (ii). See Figure 4.48 (iii).In case (iv), x and y belong to u1 and let j be such that e = (z, q). SetP =v0e1where e’ = (z, y). See Figure 4.48 (iv). When u is expanded, we will handle the difficultyof having e3 = (z, q) appear twice in Step 4.In case (v), b appears twice in P. Without loss of generality, we can assume that (r, b)appears in P before (t, b). Then vd = Uk = b, ed+1 = (b, r), and ek = (t, b) for some d andk (d < k). Let j be such that e3 = (z, q). Then v = z or a pseudovertex containing z,Figure 4,47:Chapter 4. Square-Free Two-Factors 112and v_1 = q or a pseudovertex containing q. SetP = v0e1 edvdflul vd+3ed+3vd+2e tekvkwhere e’= (y, z) and e” = (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 6Step 6.Note that we have completed Step 5 before this step. If there is a square of G whereall its unmatched edges belong to P but not any of its matched edges, then it’s one ofthe cases illustrated in Figure 4.49. The proof of Theorem 4.8 helps a reader understandhow 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 followingtwo dipaths and edge e:bfiui...ui_ifjujbg1w .. Wm_l9mWmand x and y belong to u. In cases (ii) and (iii), q = b. Possibly z and q might be insome or w in case (i), but not in cases (ii) and (iii). In case (i), if z and q are insome u, then j > i. In either Step 2.2 or 3, ‘u or a pseudovertex in u containing x andy has been expanded. Let u be the pseudovertex expanded in either Step 2.2 or 3 and jbe such that e3 = (z,q).In case (a) in (i), let h be such that eh is the stem of u. SetP = v0e1 v_1eveuehvh• evChapter 4. Square-Free Two-Factors(vi)‘I113(iii)SS(iv) (v)— —/Figure 4,48:Chapter 4. Square-Free Two-Factors 114\/Figure 4.49:Chapter 4. Square-Free Two-Factors 115where e’ (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).SetP = v0e1 • v3_ieve uekvk • evwhere e’ = (z,y). See (ii) in Figure 4.50.In case (iii), let k be such that Vk is q or a pseudovertex containing q. Then Vk_2 is yor a pseudovertex in u containing y, and Vk_1 is a pseudovertex in u containing x. SetP = v0e1 evevk_2ek_1vk_1ekvk•• evwhere e’ = (z, y). See (iii) in Figure 4.50.Note that u is reshrunk again in this step. In Lemma 4.14, we show that eachpseudovertex can be expanded at most O(IVI) times. Return to where Steps 4r’.,6 werecalled 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 = ek and f In (a), let u bethe real vertex where edge e and f are incident. LetP = v0e1 vk_lekuek+lvk+1 evand go to the beginning of Step 3. In (b), assume that e is the stem of Vk and expandpseudovertex Vk, 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 wehave the alternating walk which we were looking for.Chapter 4. Square-Free Two-Factors 116(i)(a)_— —— (b) ,__ — — — —,\IIII(ii)/\(iii)IIIIIFigure 4.50:Chapter 4. Square-Free Two-Factors 1174.7 The validity of the Recover AlgorithmIn Step 3 in the Recover Algorithm, we stated that there is a pseudovertex in P satisfyingconditions (i) and (ii) if there is a pseudovertex in P. In this section, we will prove thestatement 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 existsa pseudovertex in F satisfying conditions (i) and (ii).Proof. Assume that there is no such pseudovertex, Clearly there is a pseudovertexsatisfying condition (i). Let w1,w2,•• , wk be pseudovertices satisfying condition (i).For each i, there exist Dxyzq of the type in Figure 4.41 and a pseudovertex o whichprevent the pseudovertex w from being expanded by condition (ii). The pseudovertexo is not an ancestor of w. The pseudovertex o is either wj or an ancestor of wj forsome j i. Construct a digraph G’ = (W, D) in the following way: The set W is{ i = 1,2,• , k} and the set D consists of arcs w —+ w3 where o is either wj or an(I) (ii)/I/\/stem0\stem/Figure 4.51:Chapter 4. Square-Free Two-Factors 118ancestor of w3. Then each vertex w in G’ is the tail of some arc. Since G’ has a finitenumber of vertices, then there is a dicycle. Let C = w12 w1 be the dicycle. Then ois either w+i or its ancestor (here we consider 1 as 1 + 1). Without loss of generality, wecan assume that among (z1, qj) (zi, q) is the last added to F. When edge (z1, qj) is added,the pseudovertex w1 has been formed already. After edge (z1, qi) is added, a pseudovertexis formed containing w and o. Since w1 is either o or its descendent, w1 is in thenew pseudovertex or its descendent. After all of (z1, qj) (i = 1•.• , 1 — 1) are added to F,for j > i, w is either in a pseudovertex containing w2 and o or its descendent. When(zi, q) is added to F, the pseudovertex w1 has been formed already and is either in apseudovertex containing w1 or its descendent. Since 01 is either w1 or its ancestor, eitherw1 and o1 are in a pseudovertex or Wi is a descendent of Oj when (zi, q) is added. If Wi and01 are in a pseudovertex, then the edge (zi, qi) must not be added. So w1 is a descendentof Oi, contrary to the assumption. INow, we will show that at the end of the Recover Algorithm we get an alternatingwalk which we look for.Theorem 4.8 A walk P which we get at the end of the Recover Algorithm is an alternating walk from root(v) to v and P F doesn’t contain any square, except when v isdummy 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 toverify that P F doesn’t contain any square except that when v is dummy or dummyodd there exists a square containing v. Without loss of generality, we can assume thatv is neither dummy nor dummy odd. We will prove by induction on the running of theRecover Algorithm that P e F 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. Theinductive step is that when a pseudovertex is expanded and we get new P at the endChapter 4. Square-Free Two-Factors 119of Step 6 there is no square of G where all its unmatched edges belong to P but notany matched edges. Clearly there is no such square of G for the initial P, i.e. P inStep 1. Assume that there is a P having such a square. Let * be the P and Dvwxybe the square. Without loss of generality, we can assume that there is no such squarefor previous P’s. Let P’ be the previous P and o be the pseudovertex in P’ which isexpanded. Since Elvwxy appears after o is expanded, at least two vertices in flvwxy arein 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. Firstconsider the case that a pair of vertices which are adjacent in Dvwxy are in u. Withoutloss 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 bematched. 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 inP*). It must be one of the cases in Step 5. Now suppose that a pair of vertices which arenot adjacent in Elvwxy are in it, say v and x are in it. Without loss of generality, assumethat neither w nor y is in u (otherwise, it’s the previous case that two adjacent verticesin 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 completesthe proof of Claim 1.From now on we can assume by Claim 1 that any pair of vertices in Dvwxy doesn’tbelong to a pseudovertex in o. All of the four vertices v, w, x and y cannot be in o. (If allv, w, x and y are in o, then Evwxy is a square of type (ix) or (x) in Figure 4.36. Withoutcreating a square, we can reach each vertex with a matched edge and an unmatchedChapter 4. Square-Free Two-Factors 120edge.) So either two or three vertices are in o. There exists an edge in Dvwxy joining avertex 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 isunmatched. If there is such an edge, then it’s the stem of o.Proof. Let F’ = v0e1 • and vk be pseudovertex o. Let e be an unmatched edgein Dvwxg joining a vertex in o and a vertex not in o. Then either e is ek or ek+1, or avertex in o is added to F twice (it must be one of the cases in Figure 4.52). Either ej orek+1 is the stem of o, say ek. In Step 3, P is chosen such that P doesn’t create a squarecontaining ek+1. Thus e cannot be ek+1. Suppose that e situated as in one of the cases inFigure 4.52. In case (i), there is no square containing e. In case (ii), flvwxy must havealready appeared when we formed F’. This completes the proof of Claim 2.(i) (ii)S,‘ 0 SI SI I II () I I\__ IFigure 4.52:As mentioned above, we have two possibilities: (A) Three vertices in Dvwxy are in o.(B) Two vertices in Dvwxy are in o.Case A Three vertices in Dvwxy are in o:Without loss of generality, we can assume that y is not in o. When pseudovertex o wasII, 0Chapter 4. Square-Free Two-Factors 121formed, one of (v, y) or (x, y) satisfies one of the following three cases: (i) matched andbelonged to P0, (ii) unmatched and didn’t belong to P0 (it might not have been in F),or (iii) belonged to a pseudovertex. (Note that P0 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 beingdummy, until we encounter one of the cases in Step Sd in the Blossom Algorithm. Saythat (v,y) is such an edge, i.e. (v,y) was as in case (i), (ii), or (iii). If (v,y) was matchedand belonged to F0, (v, y) was the stem of o and stays as the stem of o until the end of theBlossom 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 andwas the stem of o when pseudovertex o was formed (it’s not any case on p. 100). Wecannot have case (i) or (ii). Now suppose that (v, y) belonged to a pseudovertex u. Sincev belongs to both u and o, either u is inside o or u and o are attached to each other. If u isinside o, then y belongs to o, a contradiction. It’s not possible that u and o are attachedto 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 pseudoverticesare 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 andx are in o. At least one edge in Dvwxy is unmatched. Say that (v, w) is unmatched. ByClaim 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 vmust be in o, a contradiction that matched edge (v, y) is not in o. So the two verticeswhich are in o must be adjacent in Dvwxy. Without loss of generality, we can assumeChapter 4. Square-Free Two-Factors 122that 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 P0, (ii) unmatchedand didn’t belong to P0 (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). Ineach case, we will distinguish between the cases where both (w, x) and (v, y) are matchedor not.(i) (x, y) E P0 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 continuesto have p(w) = or forms a pseudovertex either with x’ or an ancestor of x’. Buteventually w and v are in the same pseudovertex and then the pseudovertex mustcontains 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 onlyvertex-disjoint squares, there is no square containing edge (t, y). The vertex y mustbe odd or nondummy in a pseudovertex and v must be even with p(v) = y. Thevertex 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 123(ii) (x, y) P0 and is unmatched:(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 byClaim 2. Then one of the following cases must occur (Figure 4.53):(I) (ii)/ OFigure 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 ata 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/II//-2Chapter 4. Square-Free Two-Factors(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 atthis 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 u124matched and E P0. So (w, x) g P0. If (w, x) g Ps,, then another pseudovertex isformed, which contains o, x and y (see (i) in Figure 4.54). In Steps 5 and 6, wemodify P to avoid Evwxy. Suppose that (w, x) E Pr’. Since (w, x) is in a squarecontaining (x, y), x’ does not have both w and y as predecessors in SP. The vertexy 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).(i) (ii)I SI S\X-,F0/Figure 4,54:Chapter 4. Square-Free Two-Factors 125has been expanded already, p(o) u and neither (w, x) nor (v, y) is in P0. If either(w,x) or (v,y) is in P, say (v,y), then (w,x) is not in P. Another pseudovertexmust be formed, which contains a and o ((i) in Figure 4.55). The edge (x, y) mustbe matched (if (x,y) is in *, then (v,y) is in .P*). If neither (w,x) nor (v,y) isin P, then another pseudovertex must be formed, which contains u and o ((ii) inFigure 4.55). In Steps 5 and 6, we modify P to avoid Dvwxy.(I) (ii)/ ,/ \\IL_i: ol1 \\/\\,ll,!Figure 4.55:The proof of Theorem 4.8 is completed. I4.8 The structure of F at the end of the Blossom AlgorithmIn this section, we will describe the structure of F when the Blossom Algorithm terminates. 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) <2for the current F.When the algorithm terminates, each vertex v is one of the following: (dummy)odd,\— —Chapter 4. Square-Free Two-Factors 126even, a vertex in a pseudovertex (either dummy or nondummy), or v F. The vertexhas the following properties:(i) If a vertex v is odd, then there are two matched edges incident to v. The otherends 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 isin a blocking square and the other has an end which is dummy odd, even, a dummyvertex 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 vertexor 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 theother 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 toa vertex not in F,(vi) There is no unmatched edge where its ends are even vertices or vertices in a pseudovertex, with the exception of a stem of a pseudovertex or an edge in a blockingsquare,(vii) There is no matched edge between two pseudovertices, except for the followingthree 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 isthe following: it’s a matched edge from an (dummy)odd or a nondummy vertex inChapter 4. Square-Free Two-Factors 127another pseudovertex, or an unmatched edge from an even vertex or a vertex inanother pseudovertex. It may be in a blocking square, and(ix) In a pseudovertex, its true base or dummy vertices can be deficient, but no othervertices can be deficient. If there is a deficient vertex v which is neither the truebase of the pseudovertex nor a dummy vertex, then there is an augmenting walkfrom 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 verticesin a blocking square might have been changed after it was created. At the end of thealgorithm, 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 apseudovertex.Let o be any pseudovertex. Let E(o) be the set of edges where it’s not in a blockingsquare, and its one end is a nondummy vertex in o and the other end is even or in anotherpseudovertex. Let BS(o) be the set of edges in blocking squares of which at least onevertex 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 matchededges are in H(o). If v is a dummy vertex and the blocking square containing v is nottype (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 amatched edge from a (dummy)odd or a nondummy vertex in another pseudovertex or anunmatched edge from an even vertex or a vertex in another pseudovertex. If the stem isan unmatched edge from an even vertex or a vertex in another pseudovertex, then thereChapter 4. Square-Free Two-Factors 128(I)(v)(vH)(H) (iii)(viii)(iv)c)(vi)Figure 4.56:Chapter 4. Square-Free Two-Factors 129are 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)oddvertex or a nondummy vertex in another pseudovertex. Then there is another matchededge incident to b, of which the other end is even or a vertex in a pseudovertex. So thematched edge is in H(o). If the stem is from an odd vertex, then it’s not in H(o) andthere is only one matched edge in H(o) incident to b. Otherwise (i.e. the stem is froma dummy odd vertex or a nondummy vertex in another pseudovertex) it is in H(o). Inthis 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 eincident to b (if there is no matched edge, then an augmentation is made since b is notdummy). The end of e which is not b is either even or a vertex in a pseudovertex, so eis in H(o).Suppose that b is dummy in o. Then b belongs to a blocking square of type (viii) inFigure 4.56. There is no matched edge in G[O] U BS(o) which is incident to b. By thedefinition 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 aretwo matched edges in H(o) incident to v. If v is a dummy vertex in o and the blockingsquare containing v is not type (viii) in Figure 4.56, then there is one matched edge inH(o) incident to v.Lemma 4.10 There are two matched edges in H(o) incident to the true base b, exceptwhen 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 onematched edge in H(o) incident to b. If b is a dummy vertex, then b belongs to a blockingsquare 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 1304.9 A Tutte-type TheoremIn this section, we will derive a Tutte-type theorem for a square-free two-factor when G isa graph whose squares are vertex-disjoint. Also the theorem gives a necessary conditionfor the existence of a square-free two-factor of G when G is an arbitrary graph. At thismoment we don’t know whether it is also sufficient in a general graph. The theoremproves that if the Blossom Algorithm terminates without a square-free two-factor thenthere is no square-free two-factor in G. A similar, though incorrectly worded, theoremfor triangle-free two-factors is in [31], which uses the idea of vertex splitting.Given G = (V, E). Let S V and A (V \ S). Construct the graph GA[V \ 5] asfollows: For v e A, if deg[\] (v) = 0, do nothing. Otherwise, replace v with verticesv1,v2,••• , Vk and edge (u, v) with (‘u, v) such that(i) every vertex v has degree 1 or 2 after splitting, and(ii) every vertex v of degree 2 is in a square or a diamond where a diamond is thefollowing type of a graph (Figure 4.57).Let B C V \ (S U A) have the following long list of properties: If v E B, there existsU, in GA[V \ S] which is a square or a diamond with vertices v, w, x and y such that(i) none of w, x and y belongs to B,Figure 4.57:(ii) the degree of v in GA[V \ S] is greater than 2,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 otherpart (i.e. the part not in a square) a degenerate petal. If there exists a diamond in theresulting 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 inG[V \ (S UT)] are joined by an edge in a square, and some edges, squares and degeneratepetals are attached to one of subgraphs (Figure 4.58). Call a component in GT[V \ S] ablossom tree.Define a center in the following way: Form a graph G from GT [V \ S] by deletingedges in a square which has a split vertex from G[V \ (S U T)}. If a square has only onesplit vertex and two vertices which are in one component of the resulting graph G, thenput back in the graph G the edges in the square (Figure 4.59). Call a component in theresulting 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 whichis not adjacent to the vertex in Dvwxy is a split vertex of a vertex in B. The othertwo 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 theother two vertices are split vertices.Chapter 4.. Square-Free Two-Factors 132G[V-(S UT)]a degenerate petala component inFigure 4.58: A blossom treeChapter 4. Square-Free Two-Factors 133a component in GFigure 4.59:(r) One pair of vertices which are adjacent in Dvwxy are split vertices and the othertwo vertices belong to different centers.(s) One pair of vertices which are not adjacent in flvwxy are split vertices and theother 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 vertexin 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 splitvertex of a vertex in A and the other end is a split vertex of a vertex in B. Denote byan odd blossom any blossom tree where each center has an odd number of petals andhas neither a degenerate petal nor a square petal of type (p’). The reason we definean odd blossom as one having neither a degenerate petal nor a square petal arises onone centerIIII/)1/Chapter 4. Square-Free Two-Factors 134(p,)(r)a center(q)(t)(s)0Figure 4.60:Chapter 4. Square-Free Two-Factors 135p. 148(a component of type (v) is not an odd blossom). Call a blossom tree which is notan odd blossom an even blossom. An isolated vertex and an isolated edge are consideredto be even blossoms. An isolated square is considered to be an odd blossom with onecenter and one square petal of type (p). A blossom tree with no center, i.e. no vertex inV \ (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,q0 = the number of square petals of type (q) in odd blossoms,= the number of square petals of type (r) in odd blossoms,s0 = the number of square petals of type (s) in odd blossoms, andt0 = the number of square petals of type (t) in odd blossoms.LetC(S, T) = 21T1—degG[V\5](v)— 3BI, andyEAD(S, T) = c0 + p0 + q0 — t0 + 2p’.Theorem 4.11 G has a square-free two-factor if and only if for all S and T with anassociated splitting as described earlier in this section,21S1 C(S,T)+D(S,T)Proof. (=) Let F be a square-free two-factor of G. Choose S and T be any pair ofdisjoint subsets of V and split vertices of T as described in earlier this section. Divide TChapter 4. Square-Free Two-Factors 136into two sets A and B satisfying the description earlier. Let F’ = F fl G[V \ S]. Clearly,21S1 2V \ S — 21F’I= 21V \ SI — C(S,T) — 21F’I + C(S,T)= 21V\ (SUT)I + deg[V\s](v) +31B1 —2IF’ +C(S,T).yeAIt’s enough to show that21V \ (S U T)I + degG[V\S](v) + 31B1 — 21F’I D(S, T) (4.8)yEALet A’ be the set of split vertices of vertices in A, B’ be the set of split vertices of verticesin B which are tips of square petals, B” be the set of split vertices of vertices in B whichare tips of degenerate petals. Equation (4.8) holds if for each component C in the graphGT[V \ 5],2I(V\(SUT)) nC+ deg(v) +IB”flCI —21F’flCIvEA’UB’J cc+p+qc—tc ifCisanoddblossom ()( 2p otherwisewhere cc is the number of centers in C and similarly for Pc, qc, t and p. An oddblossom doesn’t have a square petal of type (p’). If C is an odd blossom, then p’c = 0.Let2 ifv is in V\ (SUT) (i.e. in acenter)2 if v is in A’ and a tip of a square petalb(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, thenLHS of (4.9) is 0. Except for a tip of a degenerate petal, a vertex v cannot have degreeChapter 4. Square-Free Two-Factors 137more than b(v) in F’ fl C. A vertex v is said to be short if v has degree less than b(v) inF’ fl C. The shortage of a subgraph Q of C is VEQ[b(v) — deg,flØ(v)]. We have to showthat 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 squareis an odd blossom with one center and one square petal of type (p)). Suppose that C isnot an isolated square. Tips of square petals are least short when they are matched inthe following way (Figure 4.61):(i) (ii) (iii)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 inC has at least shortage one except one center in a square petal of type (s) and (t).(iv) (v) (vi)Figure 4.61:Chapter 4. Square-Free Two-Factors 138Proof. Let Q be any center in 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 asquare petal except type (q), there is only one matched edge having one end in Q. In asquare petal of type (q), there are three matched edges having one end in Q. Let 1 bethe number of edge petals of Q, p be the number of square petals of type (p). Similarlyfor qq, rQ, Sq and tQ. Thendeg,(v) = 21F’ fl QI + 1 +PQ + 3qQ + rQ + Sq + tq.vEQanddeg,(v) b(v) = 2IQ.vEQ vEQSince Q has an odd number of petals, 1 + Pq + 3qQ + rQ + Sq + tq is odd. Sodeglfl(v) 2Q—1vEQThen 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. Then there are more thanCC — SC — t centers which have at least shortage one, so the shortage of C is more thanc + PC + q — tC (= cc — sc — t + PC + q + Sc’). If some center not in the exceptionalcases described in the above claim doesn’t have shortage at least one, then there existan edge petal which is not matched or a square petal where its edges are not matched inthe 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 atits tips and a tip of a degenerate petal has degree one in F’ fl C. If not, then there is avertex which has more shortage than we have assumed and we can borrow some shortagefrom it. Suppose that there exists a square petal U of type (p’) which has less than twoChapter 4. Square-Free Two-Factors 139units of shortage at its tips. Clearly, U has at least one unit of shortage at its tips andwe have to look for another unit of shortage from another place. To have only shortageone, the vertex b’ in B’ must have degree two in F’ fl C. The tip of the degenerate petalwhich is split from the same vertex as b’ must have degree 0 in F’ fl C, so we can borrowone 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 showthat 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 onwhat type of a square petal U is (Figure 4.62):In case (i), the tips which is adjacent to b’ have at least shortage one, so U has atleast four units of shortage at its tips. Since an isolated square is an odd blossom withone center and a square petal of type (p), this is two more units of shortage than we have(i)_ (iiFigure 4.62:Chapter 4. Square-Free Two-Factors 140assumed.In case (ii), U has at least four units of shortage at its tips similar to case (i). If Uis 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 thanwe 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 similarto 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 unitsof shortage than we have assumed. Even if U is in an odd blossom and the two units ofshortage in the two centers we have assumed are “transferred” to tips of U, we have stillone 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 isin an odd blossom. If U has only two units of shortage at its tips, then the other tip ofU has degree two in F’ fl C. So the shortage in the center cannot be “transferred” to atip of U, and we still have one extra unit of shortage. If U has more than two units ofshortage 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 theBlossom Algorithm to G. At termination, let F be the square-free (0, 2)-factor which wehave and S be the set of odd vertices, and let T = A U B where A is the set of evenvertices 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. Splita 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. Notethat every square petal is a blocking square, but not every blocking square is necessarilyChapter 4. Square-Free Two-Factors 141a square petal (see Figure 4.65).For every odd vertex v, there exist two matched edges which are incident to v. Thematched edges are incident to either an even vertex or a vertex in a pseudovertex. So21S1 = Fl — IF’I where F’ is the same as described before. Since there exists a vertexwhich is matched by less than two edges, 21V1 > 2F and 21S1 < 2V \ S — 21F’I(41S1 = 21F1 — 21F’I <21V1— 2IF’I). Now it’s enough to show that21V\ S — 21F’I = C(S,T) + D(S,T).That is,21V \ (S U T)I + > deg[V\8](v) + 31B1 — 21F’I = D(S,T).yEAThis 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) anisolated vertex, (ii) an isolated edge, (iii) an isolated square, (iv) a number of pseudovertices joined by edges, or (v) a center consisting of vertices not in F. Possibly somecomponent consists of only split vertices. If it’s not case (i), (ii) or (iii), we include thiscase 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 nomatched edge which is incident to v, then v is a root at the beginning of the algorithmand so has an even label. If there is one, then its other end w is odd and v gets an evenlabel 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 nondummyin a pseudovertex. Suppose that a vertex v is not in F. Then there are two matchedChapter 4. Square-Free Two-Factors 142edges incident to v and no end of the two matched edges is odd. So degGT[V\s](v) 2,contradicting degGT[V\S] (v) = 1. An end of an isolated edge cannot be a vertex not in F.)If an end of e is a split vertex of a vertex in B, then e is a degenerate petal and must bea matched edge by Property (ii) on p. 126. If both ends of e are split vertices of verticesin A, then e must be matched (otherwise e joins two even vertices and a pseudovertexwhich contains both ends of e must be formed). In any case, e must be matched. Soboth 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 isolatedsquare are blocking squares and only type (i) in Figure 4.56 will be isolated (others joinedat pseudovertices). By the algorithm they are one of the following (Figure 4.63):(i) (ii):dummy oddQ : evenIn 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 blockingsquare, they, excluding dummy vertices they contain, belong to one center and the edgemust be the stem of one of them. Note that if two vertices in a blocking square belongto one center and another vertex is in a pseudovertex, then we consider the pseudovertexcontaining the third vertex to be in the center containing the other two vertices. InFigure 4.63:Chapter 4. Square-Free Two-Factors 143Figure 4.64, pseudovertices x, y and z belong to one center.Figure 4.64:Some blocking squares are not square petals. That is, a blocking square of which twoor three vertices are in pseudovertices in one center (Figure 4.65).Figure 4.65:(‘; apseudovertexone centera pseudovertexClaim 2 Component C has neither a degenerate petal nor a square petal of type (p’).Chapter 4. Square-Free Two-Factors 144Proof. By Property (ii) or (iii) in p.126, an end of an edge in a degenerate petal cannot benondummy in a pseudovertex. So C could not have any degenerate petal. A square petalof type (p’) must be a blocking square of type (i) in Figure 4.56. In Figure 4.66, for vertexq to be in a pseudovertex, either (q, x) or (z, q) must be the stem of the pseudovertexcontaining q. So either x or z must be in a pseudovertex. Thus C cannot have a squarepetal 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 Q in C has an odd number ofpetals. The center Q consists of one or more pseudovertices excluding their dummyvertices if any. Since two pseudovertices are joined by an edge which is the stem of one ofthem, every pseudovertex in Q, except one pseudovertex, has its predecessor in Q. Theexceptional pseudovertex is an ancestor of all pseudovertices in Q. Call this pseudovertexthe base of Q. By Property (viii) in p. 126 either the true base of the base of Q is oneof the roots, or its stem is a matched edge from an odd vertex, an unmatched edge froman even vertex which might be in a square petal, or an edge from another center or adummy 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 ofthe base of Q and an unmatched edge from an even vertex. A square petal which is nottype (q) has two edges incident to a vertex in Q; and one of the edges is matched and theChapter 4. Square-Free Two-Factors 145other is unmatched. However, if one of the edges is the stem of the base of Q, both of theedges must be either matched or unmatched. In a square petal of type (q), all four edgesare 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 thesquare petal is type (viii) in Figure 4.56. In the exceptional cases, two of the edges arematched. A blocking square which is not a square petal has two matched edges incidentto 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 hastwo incident matched edges in C. The true base has two incident matched edges in Cwith 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, in1 be the number of square petals of Qwhich are not type (q), m2 be the number of square petals of Q which are type (q), andii be the number of blocking squares attached to Q which are not square petals. Then21Q1 21F’ ‘ QI + 1 + m1 + 3m2 + 2n ± 1. (4.11)By Equation (4.11), 1 + ïni + m2, the number of petals of Q, is odd. This completes theproof 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 twovertices 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’ whichare split now and in a square petal (resp. not in a square petal, i.e. in a center). Eachcomponent in C’ is either one center with only edge petals and square petals of type (q)Chapter 4. Square-Free Two-Factors 146rFigure 4.67:(i) (ii) (iii) (iv)(vii)0a center(vi)Figure 4.68:Chapter 4. Square-Free Two-Factors 147or one of the cases in Figure 4.68. Each case in Figure 4.68 has a square petal of typedifferent from (q) and may have more than one center which are joined by edges in thesquare petal. Let U be the square petal. Note that each center might have edge petalsand 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’. Supposethat a component R in C’ consists of one center with only edge petals and square petalsof type (q). Then R has one unit of shortage at its base or at the tip of the edge petalwhich is the stem of the base, one unit of shortage per square petal of type (q) (the samereason as given in the proof of Claim 3), and one unit of shortage per vertex in D”. Nowsuppose that a component in C’ is one of types in Figure 4.68. For each center, one ofthe edges in U is the stem of its base. It has two units of shortage at the tips of U, oneper square petal of type (q), and one per vertex in D”. So the total shortage in C’ ism + 2n + c + 1 where m is the number of components in C’ with only edge petals andsquare petals of type (q), n is the number of components in C’ which is one of types inFigure 4.68 and 1 is the number of vertices in D” (also the number of vertices in D’). Ifwe put vertices in D’ and D” back together to recover C, then the shortage at verticesin D’ and D” disappear. So LHS of (4.9) is in + 2n + qc — 1.Letn1 = the number of components which are type (i),= the number of components which are type (ii) and (iv),n3 = the number of components which are type (iii), (v) and (vi), andn4 = the number of components which are type (vii).Thenn =n1+n234,andChapter 4. Square-Free Two-Factors 148c =n2+2n334m.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). ThenP1 + r1 + 2r + s1 + 2s + t1 + 2t + 3t,n1 = p’+r2+st3,= p°+r1+stn3 = r°+s°+t’, andn4 = t0.So LHS of (4.9) ism+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 oftype (i) in Figure 4.56. A square petal of C must be of type (p’) and the edges in thesquare petal must be matched as in Figure 4.69. There is shortage two at its tips. Eachedge petal is matched by Property (v) on p. 126 and a tip of each degenerate petal hasdegree one in F’ fl C. Since a vertex in a center is not in F, it has degree two in F’ fl Cby property (iv) on p. 126. LHS of (4.9) is 2p 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 squarepetal or a degenerate petal, then C is an even blossom. Suppose that C doesn’t haveeither a square petal or a degenerate petal. Then C has only edge petals. Since a vertexin a center is not in F, it’s matched by two edges both of which are in C by propertyChapter 4. Square-Free Two-Factors 149p(y)=xX,Z :eveny :dummy oddFigure 4.69:(iv) on p. 126. Each edge petal is matched by Property (v) in p. 126. So each centermust have an even number of edge petals. This completes the proof of Claim 4.The proof of Theorem 4.11 is completed. I4.10 Efficiency of the Blossom AlgorithmIn this section, we derive an upper bound on the amount of work done by the BlossomAlgorithm in solving the square-free two-factor problem. In Theorem 4.15 we showthat the Recover Algorithm runs in O(1V14) time. Using this theorem it’s shown inTheorem 4.16 that the amount of work to perform the Blossom Algorithm is bounded byO(EI . 1V15) time. In the algorithms, we omit some technical details. In this section wewill give rough outlines of each of them so that we can verify our complexity estimates ofeach. 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 tocheck 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 checkit.Chapter 4. Square-Free Two-Factors 150We assume that we store a pseudovertex in the following way: Make a list of verticesin a new pseudovertex o and keep the cycle and base structure of the pseudovertex o inQ (0) (as mentioned in Step 5c in the Blossom Algorithm). Each vertex keeps a list ofpseudovertices containing it. For each vertex in the pseudovertex o, add o to the list ofpseudovertices containing it.Here we will describe how to check the existence of a square which blocks augmentation along some path. At the beginning of the Blossom Algorithm, we find all of thesquares in G using the algorithm which is designed by B. Monien [40]. His algorithmtakes O(1V12) time to find a square in G. If we find a square in G, then delete the fourvertices in the square from G and look for another square (in our graph the squares arevertex-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 graphare vertex-disjoint, there are at most 11 squares. So after O(VI) iterations we get allof the squares of G. It takes O(1V13) time to find all of the squares of G. The followinglemma shows how to check the existence of a square which blocks augmentation along apath and how much work is needed.Lemma 4.12 For a path P appearing during the algorithms, it takes O(1V12) time tocheck whether there is a square S where all its unmatched edges belong to P but none ofits matched edges belongs to P.Proof For each unmatched edge e in P, check whether there is a square containing edgee. 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 edgesin the square are in P. This takes 0(IVI) time since P contains at most 0(IVI) edges (apath P appearing during the algorithms pass through each vertex at most twice).Chapter 4. Square-Free Two-Factors 151Since there are at most O(IVI) unmatched edges in F, we go through the aboveprocedure at most O(IVI) times. The total amount of work is bounded by O(IV2). IThe following lemmas are needed for proving that the Recover Algorithm runs inpolynomial 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 nowhas been expanded before. Without loss of generality, we can assume that in previoustimes when we went through Step 5 and modified P, none of Uh’s in the new P hadbeen expanded before. In this proof, pseudovertices except o will be denoted by capitalcharacters.Claim 1 Since pseudovertex o was expanded, edge (z, q) or a pseudovertex in o containing (z,q) has been in P.Proof. Assume that neither edge (z, q) nor a pseudovertex in o containing (z, q) had beenin P and later (z, q) itself or a pseudovertex containing (z, q) was added to P. That is oneof 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 containinga, 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 Pby Dabcd. Since both U and B contain the edge (z, q), one of the following cases mustoccur: (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) wasChapter 4. Square-Free Two-Factors 152added to , the edge (c, d) must be in a pseudovertex (otherwise Dabcd was ablocking square during the Blossom Algorithm). When (a, b) was added to ‘, apseudovertex 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 byflabcd was made (since U is the smallest pseudovertex such that U contains theedge (z, q) and the intersection of U and P is nonempty when the modification ofP by Dabcd was made). So one of case (i) or (iv)(vi) in Figure 4.45 cannot occurby 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 isinside o, then we arrive a contradiction by an argument similar to case (A). Supposethat 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 thisproof, the modification of P by Dabcd was made before o was expanded. So wearrive 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(I)I(ii)Figure 4.70:S//153Proof. Since uh was expanded before (z, q) appeared in P, either (z, q) is in one ‘11d(1 d h) or u was not in P. First suppose that (z, q) is in one d (1 d < h). Sincethe 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 pseudovertexcontaining a, b, c and d. Then U must contain u. We can classify it into the followingcases: (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.II,I BI /I /I/IIIuB// uS/I/— — ——II/I(B) U is inside 0:Chapter 4. Square-Free Two-Factors 154Since U contains u, U must be u2. The pseudovertex U was not in F, hence Dabcdcould 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). ThenUh was in P before and later it was removed from P. So one of situations in Figure 4.45and 4.49 occurred and uh was removed from P. Let Iabcd be the square which madethe change in P and B be the pseudovertex containing a, b, c and d. Then ‘uh is in B.Since uh is in B and o, one of the following cases must occur: (A) B and o are the samepseudovertex, (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 (z, q), then we must form a pseudovertexcontaining a, b, c and d, but not edge (z, q), hence contradicting that B and o arethe same pseudovertex. Similarly we arrive at a contradiction when edge (z, q) wasadded 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 pseudovertexwas formed containing a, b, c and d, but not edge (z, q). If (z, q) was added toF before the pseudovertex U was formed, then the pseudovertex U must not beinside o.Chapter 4. Square-Free Two-Factors 155S..SSS-7/Case B B is inside 0:The pseudovertex B is ‘uh or inside ‘uh. So Dabcd affected only part of uh and the portionof P which is in uh 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 wasremoved from P or remained in P when a change in P is made by Oabcd. So it’s notpossible that (z, q) is in P and Uh is removed from P. So at least one of edges of Ilabcdis 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 beenexpanded before edge (a, b) appears in P. So uh has not been expanded either.(a) (b)////—U// \S/Figure 4.71:(c)B156\—I II II I-çChapter 4. Square-Free Two-Factors(a) (b)//0I’\(d)III0___—_•_%BB(e)// //00\ /—// /I II I—III/‘-0-’Figure 4.72: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 contradictionwhen 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. ILemma 4.14 During the Recover Algorithm, a pseudovertex can be expanded at mostO(IVI) times.Proof. Suppose that a pseudovertex u has been expanded more than once during the Recover Algorithm. The possible places during the Recover algorithm where a pseudovertexis reshrunk are in Steps 5 and 6. In Lemma 4.13 it is shown that in Step 5 pseudoverticesuhs have not been expanded before. Hence Step 6 is the only place where a pseudovertexis reshrunk. If u is reshrunk in Step 6, u is the last pseudovertex which was expanded andwill be the next pseudovertex to be expanded. The pseudovertex u will be expanded andshrunk successively until there is no more square of the types in Figure 4.49. If Dxyzqappears 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 atmost O(IVI) squares in G, u can be expanded and shrunk at most O(IVI) times. ITheorem 4.15 The Recover Algorithm runs in O(1V14) time.Chapter 4. Square-Free Two-Factors 158Proof. First we will analyze how much work is needed for each step. Note that Steps 2,—.d6may be performed more than once. The analysis below is for performing each of themonce.(i) Step 1 takes O(IVI) time:Finding the directed path P,1 takes O(IVI) time.(ii) Step 2 takes 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 ‘Uk to be expanded. Ittakes O(IVI) time since there are at most O(IVI) pseudovertices. Changing P takesO(IVI) time.(iv) Step 4 takes O(1V12) time:We have to compare a pair of edges in P to check whether they are the same edge.This takes O(1V12) time. Modifying P takes 0(1) time.(v) Step 5 takes O(1V12) 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 takesO(1V12) 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 thisbound. It takes O(IVI) time to modify P.Here we assume that we find the pseudovertex o in the following way: Scan eachpseudovertex in the list of pseudovertices containing x and check whether it containsall of y, z and q. If we find one, keep it and scan for another pseudovertex. If anotherpseudovertex containing all of y, z and q is found, then between the pseudovertexChapter 4. Square-Free Two-Factors 159we have and the one we just found we find one is inside the other and we keep thesmaller one. Scan for another pseudovertex. By repeating this procedure, we willfind the pseudovertex o. Since checking whether a pseudovertex contains all of y,z and q takes 0(IVI) time, it takes 0(1Vt2) time to find the pseudovertex o.(vi) Step 6 takes 0(1Vt2) time: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 and46 (sometime Step 7 is included). It takes 0(1Vt2) time to expand a pseudovertex. ByLemma 4.14 each pseudovertex is expanded at most 0(IVI) times. Since there are atmost 0(IVI) pseudovertices, an expansion procedure of a pseudovertex is performed atmost 0(1Vj2) times. Steps 1 and 8 are performed only once in the course of the algorithm.So the algorithm runs in 0(1Vt4) time. •Now we will derive an upper bound on the amount of work which is needed to performthe Blossom Algorithm.Theorem 4.16 the Blossom Algorithm runs in 0(IEI . 1V15) time.Proof First we will analyze how much amount of work is needed to perform each step.(i) Step 1 takes 0(IEI) time:It takes 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 160(iii) Step 3 takes O(1V12) time:It takes O(IVI) time to get the path P (resp. Pm). By Lemma 4.12, it takesO(Iv2) time to check the existence of a square described. Since at most four pathsare checked, the total amount of work is needed in this step is O(lV2) time.(iv) Step 4 takes O(1V12) time:Step 4.1 (resp. Step 4.2, Step 4.3, Step 4.5, or Step 4.6) takes 0(1) time. Step 4.4takes O(1V12) time by an analysis similar to Step 3 except that in Step 4.4 thevertex b must be found. Finding b takes O(VI2) time since b can be found bycomparing each pair of a vertex in P and one in P.(v) Step 5 takes 0(1V13) time:(a) Step 5a takes O(1V13) time:For at most 0(IVI) paths, it’s checked whether there exists a square of thetype 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). Thenumber 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 newpseudovertex o. Making a list of vertices in o takes 0(IVD time. For eachvertex 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 0(IV).(d) Step Sd takes 0(IEI) time:For each dummy vertex x, it’s checked whether there exists an edge or edgeswhich turn x into a nondummy vertex. Each edge can be checked at mostChapter 4. Square-Free Two-Factors 161twice 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. Eachpseudovertex is scanned to know whether or not it’s attached to 0, whichtakes 0(IVD time.(vi) Step 6 takes O(lVi4) time:The Recover Algorithm takes O(1V14) time by Theorem 4.15.(vii) Step 7 takes 0(IEI IVl) time:For each e e CUE, the work is as much as Step 3 (which takes O(1V12)time). SinceCUE ç E, the total amount of work needed in this step is bounded by O(iEi.lVi2)An augmentation occurs in Step 6. The deficiency of F is decreased by two at thestart 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 2iVI. Step 6can be performed at most lvi times. Apart from the first time, Step 1 is performed oilyafter we get a new F, i.e. after Step 6 is performed. Step 1 is performed as many timesas Step 6. Now we will derive how much work is needed between Step 1 and Step 6 - wewill 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 areat most five labels: odd, dummy odd, even, dummy in a pseudovertex, or nondummy ina pseudovertex) and a pseudovertex can be formed at most 0(IVI) times. So betweenStep 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 2choose an edge in E+ U E* from an even vertex or a pseudovertex to a non-odd vertexChapter 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 oto an even vertex or another pseudovertex, then go to Step 3.2. In this case, Step 2 isskipped. But here we assume that we start from Step 2 and each step between Steps 2—5is performed. After going through Steps 3—’5, either a change in F is made or we reacha conclusion that the edge cannot change F. In the latter case, we store it into set CUEand go to Step 2 to look for another edge which may change F. If each edge in E U Efrom an even vertex or a pseudovertex to a non-odd vertex is tested and no change inF occurs, then the algorithm stops (there is no square-free two-factor). For each changein F, Steps 2—’5 can be performed at most O(EI) times. Since it takes O(1V13) time toperform Steps 25, the amount of work for each change in F is bounded by O(IEI. 1v13).As mentioned, changes can be made in F between Steps 1 and 6 at most O(VI) times. Sothe 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 7is performed at most once in the course of the Blossom Algorithm. The total amount ofwork in the course of the Blossom Algorithm is bounded by O(IEI V5). I4.11 Further StudyIn Section 4.2, our augmenting walk was described - it is alternating in operations betweenadding and subtracting edges, and the symmetric difference between any of its initialsegment of even length and F is square-free. So we concern ourselves with squares beingcreated locally. As noted in Section 4.1, an augmenting walk having such nice propertiesdoesn’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 subgraphChapter 4. Square-Free Two-Factors 163which consists of wavy edges in Figure 4.73 (ii). We can easily see that F’ is the onlypentagon-free two-factor of G. The symmetric difference F/IF’ is:{ (vo,vi), (v1,7),(v7,8),(v3,4),(v4,5),(v5,6),(v6,v3), (v9,v10), (vio, vu), (v11,v12), (v12,v9)}.LetP — {(vo,vi),(vi,v7),(,8},C = {(v3,4),56,andC’ = {(v9,vio),(vio,v11),(vii,v2,}.We cannot construct an alternating walk which includes F, C and C’ as in the case ofsquare-free two-factors.If we replace the pentagonsv01236andv789123 by any other n-gon (n 5),we reach the same conclusion that there is no such augmenting walk as in the case ofsquare-free two-factors. The existence of a nice augmenting walk of an L-free two-factorfor L C {3, 4} as compared with the other cases leads us to think that the problem offinding a square-free two-factor is in P. Also we believe that if a polynomial algorithmfor finding a square-free two-factor is obtained then one for {triangle, square}-free two-factors must also exist.In our algorithms, we use the assumption of squares being vertex-disjoint in G. Forexample in Step 4.3 in the Blossom Algorithm, if a dummy odd vertex v is reached byan edge e in E+, then v becomes odd. Since squares of G are vertex-disjoint, thereis no square containing e and so v can be odd. Another place where the property ofsquares being vertex-disjoint is used is in Step 5e in the Blossom Algorithm - the casesin Theorem 4.6. We also used the property in some other places. In the algorithm fortriangle-free two-factors by D. Hartvigsen [31], if two blocking triangles share the sameChapter 4. Square-Free Two-Factors 164(i)(ii)Figure 4.73:Chapter 4. Square-Free Two-Factors 165edge, then one of the triangles may become no longer a blocking square. Probably thiswill be possible for the case of square-free, but then we expect the algorithm will be quitecomplicated. We hope that in future we can either extend our algorithm to solve theproblem 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 columnsums, 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, f) -factors, Discrete Appi. Math.27, 1990, 29-38.[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 algorithm, 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, DiscreteMathematics 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 withprescribed 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. Combinatorial Theory, Ser. A 61, 1992, 153-172.166Bibliography 167[14] G. Cornuéjols and W. Pulleyblank, A matching problem with side conditions, Discrete Math. 29, 1980, 135-159.[15] G. Cornuéjols, General factors of graphs, J. Combinatorial theory B45, 1988, 185-198.[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 LinearPrograms, Combinatorial Structure and Their Applications, R. Guy (editor), Gordonand 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(n25) Algorithm for Maximum Matching in GeneralGraphs, Proc. Sixteenth Annual Symp. on Foundations of Computer Science, Berkeley, 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, 831-836.[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 graphswith 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 bidirectednetwork flow problems, Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, 448-456.Bibliography 168[28] H. N. Gabow, Data Structures for Weighted Matching and Nearest Common Ancestors with Linking, Proc. First Annual ACM-SIAM Symposium on Discrete Algorithms, 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 andCo. San Francisco, 1979.[31] D. B. Hartvigsen, Extensions of Matching Theory, Ph.D. Thesis, Carnegie-MellonUniversity, 1984.[32] P. Hell, D. Kirkpatrick, J. Kratochvfl, and I. Kif, On Restricted Two-Factors, SIAMJ. 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, 391-416.[35] L. Lovsz, The factorization of graphs, Combinatorial Structures and Their Applications, 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 Theory5, 1968, 30-44.[40] B. Monien, The Complexity of Determining a Shortest Cycle of Even Length, Computing 31, 1983, 355-369.[41] S. Micali and V. V. Vazirani, an O(/j7F. ED Algorithm for Finding MaximumMatching in General Graphs, Proc. Twenty-first Annual Symposium on the Foundations 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 andComplexity, Prentice-Hall mc, 1982.Bibliography 169[44] W. R. Pulleyblank, Faces of matching polyhedra, Ph.D. Thesis, Department of Cornbinatorics 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, Combinatorica 15, 1985, 247-255.[50] W. T. Tutte, The factorization of linear graphs, Journal of the London MathematicalSociety 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, 289-295.[54] 0. Vornberger, Complexity of Path Problems in Graphs, Ph.D. Thesis, UniversitätGH-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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0079982/manifest

Comment

Related Items