UBC Graduate Research

Unweighted Matching in Random Graphs Nelson, Kristina Dec 17, 2014

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

Item Metadata

Download

Media
42591-Nelson_Kristina_MATH448_Unweighted_matching_2014.pdf [ 308.28kB ]
Metadata
JSON: 42591-1.0220735.json
JSON-LD: 42591-1.0220735-ld.json
RDF/XML (Pretty): 42591-1.0220735-rdf.xml
RDF/JSON: 42591-1.0220735-rdf.json
Turtle: 42591-1.0220735-turtle.txt
N-Triples: 42591-1.0220735-rdf-ntriples.txt
Original Record: 42591-1.0220735-source.json
Full Text
42591-1.0220735-fulltext.txt
Citation
42591-1.0220735.ris

Full Text

The University of British ColumbiaUnweighted Matching In Random GraphsKristina Nelson, for Math 448December 17, 2014We study the application of Edmond’s Blossom algorithm for unweighted matchingon random graphs generated with the Erdo¨s-Re´nyi model. Since its publication in1965 [1], the blossom algorithm has been the subject of great interest and research, notonly in the field of matching theory but also as a linear programming problem. In thefirst part of this report we introduce the background and prerequisite graph theoreticdefinitions before describing the operation of the blossom algorithm itself.In the second part of this essay we describe our investigations around the operationalrunning time of the algorithm and attempts to improve this value. The reader maytake the results as a sort of collection of best practices and observations regarding theimplementation of the blossom algorithm. Empirical data on the running time of codeis often invaluable in the discovery and resolution of bottlenecks. As this very reportwill demonstrate, human intuition is prone to failure in this area.1 Background and NotationThis essay will use the standard notation for a simple graph G = (V,E), where V = V (G)is the vertex set and E = E(G) the edge set, whose elements are unordered pairs of distinctvertex. Observe this prevents double edges or loops from appearing. We will denote theedge between vertices x, y ∈ V (G) by (x, y). If e = (x, y) is some edge, we say vertices xand y are incident on e.We will say G′ = (V ′, E′) is a subgraph of G if G′ is a graph, and if V ′ ⊂ V, and E′ ⊂ E.A walk is a sequence of edges and vertices of G such that each edge is incident with the1vertices sequentially before and after it. A path is a walk in which each edge and vertexappears only once. A cycle is a walk where each edge and vertex appears only once - savethe first and last vertices which must be the same. In a slight abuse of notation we willfrequently speak of paths and cycles as subgraphs.A tree is a graph containing no cycle as a subgraph. A rooted tree is a tree with asingle vertex singled out as the ‘root’. Vertices can then be the ‘parent’ or ‘child’ of theirneighbour, the parent vertex closer (having a shorter minimum path) to the root than itschild.A matching M ⊂ E(G) is a subset of the edges such that no two edges share a commonvertex. We say that vertex x is matched with vertex y in M if (x, y) ∈M , and x unmatchedif no edge incident to x appear in M . There are three particularly important cases. M is amaximal matching if it is not the proper subset of any other matching. That is, for anyedge e /∈M , {e}∪M is not a matching. A maximum matching is by definition one with thelargest cardinality. A maximum matching will always be maximal, but the converse maynot hold. Finally, a perfect matching is one in which every v ∈ V (G) appears in exactlyone edge of the matching. This is also referred to as a 1-factor as each vertex has degree 1in the subgraph H = (V,M).As noted above, in searching for a maximum matching it is not enough to simply addedges until it becomes impossible to continue. This will only guarantee a maximal matching.There is, however, a variation on this procedure that does allow the iterative constructionof a maximum matching. For this we will need two more definitions.Given graph G and matching M , an alternating path is one in which the edges alternatebetween being in M and E\M . An augmenting path is an alternating path with bothendpoints unmatched vertices. Augmenting paths are important because with them we canimmediately extend the given matching. Let P be any augmenting path, then we claimM ′ = (M\P ) ∪ (P\M), the symmetric difference, forms a new matching. To see this noteremoving the edges of P from M makes all vertices of P unmatched: the endpoints wereunmatched to begin with, and by the alternating property all ‘interior’ vertices were matchedwith an adjacent vertex of P . Then, since the edges of (P\M) are within P , these can besafely added to the matching without creating a doubly-matched vertex. The result is a newmatching M ′ with strictly larger cardinality: the endpoints of P have become matched in M ′.The augmenting path trick suggests a new algorithm to build a maximum matching:simply find and ‘swap’ augmenting paths until there are no more. We hope that when theaugmenting paths run out, a maximum matching has been found. As it turns out, this isprecisely Berge’s lemma.2Theorem 1.1. Berge’s Lemma (1956, Claude Berge)Given graph G, a matching M ⊂ E(G) is a maximum matching if and only if G has noaugmenting paths with respect to M .One must be careful in apply this technique however, as the search for an augmentingpath, if done naively, can be exponentially expensive. To see this, consider trying to findan augmenting path from a given unmatched vertex v0 ∈ V (G). A natural algorithmwould be to extend alternating paths rooted at v0, adding matched or unmatched edges,as required, onto the end of each path at every step. The problem arises as some verticesmay be reached in two distinct ways: after travelling along a matched edge, and after anunmatched one. Then we must exit that vertex in each case, potentially doubling the size ofthe remaining problem. For a concrete example, see Figure 1.1 where around the first, thirdand final diamonds we have two choices of augmenting path. The blue highlights one of the8 resulting paths: here the third and final diamonds have been traversed in the same shapebut the first is different. It is clear that this structure could be extended, and with theaddition of each pair of diamonds, requiring 6 vertices, we double the number of augmentingpaths. Thus any algorithm that considers all augmenting paths will be exponential in |V (G)|.Figure 1.1: A graph with left and rightmost vertices unmatched, matched edges bolded.The blue selection highlights one possible augmenting path.Edmond’s blossom algorithm (1965) was the first to circumvent this exponential cost.The idea introduced was to remove, via graph contraction, a specific odd-cycle structure, a‘blossom’, when encountered during the augmenting path search. We discuss the algorithmin greater detail in the next section. First we explain what exactly we mean by ‘contracting’parts of our graph G to vertices, and for this we require a few final definitions.Given graph G = (V,E), and U ⊂ V a non-empty collection of vertices we will define theresult of contracting U to be a new graph G′ = (V ′, E′) where V ′ = V \U ∪ {w}, w a newvertex of G′ we will call the contraction of U , and E′ = {(x, y) ∈ E : x, y /∈ U} ∪ {(x,w) :3x ∈ V \U and (x, u) ∈ E for some u ∈ U}. Recall that the edge (x, u) is an unordered pair,so this definition will add an edge between vertices x and w whenever x was connectedto some vertex in U . Given a subgraph H of G, by the contraction of H we mean thecontraction of its vertex set, as defined above.We will need for any matching, M on G to interact nicely with any contractions thatmight occur. If G′ is the result of contracting some non-empty U ⊂ V (G), then letM ′ = {(x, y) ∈M : x, y ∈ V \U} ∪ {(x,w) : x ∈ V \U and (x, u) ∈M for some u ∈ U}. Wewill refer to M ′ as the contraction of M . Note that if U is not chosen carefully M ′ may notbe a matching at all.2 Optimizing Edmond’s Blossom AlgorithmSeveral variations on Jack Edmond’s famous blossom algorithm were implemented. C++code from the LEDA algorithm library [2] was built upon. We were most interested in theoverhead incurred by the contraction and expansion of blossoms during the algorithm. Forthis reason, in addition to Edmond’s original algorithm, we implemented several versionswhich attempt to reduce the number of blossoms contracted.The three algorithms to be discussed will be creatively referred to as: (1) The BlossomAlgorithm, (2) The Blossom Algorithm With Queue, (3) The Naive Algorithm.2.1 The Blossom AlgorithmWe now introduce the formal definition of a blossom. We will do so on arbitrary graphG = (V,E) with matching M . It is important to realize that this graph need not be the onethe blossom algorithm is originally called on. Throughout the algorithm certain subgraphs,blossoms in fact, of the current graph will be contracted, each time producing a new graph.In this way the underlying graph changes throughout the algorithm. Finding a blossomhowever will always mean doing so on the current graph. This leads to a recursive structure,with blossoms being found in graphs created by the contraction of previous blossoms. As aresult, blossoms may very well contain the vertices previous blossoms were contracted into.Consider any graph G, with matching M ⊂ E(G). The blossom structure consists of acycle and has a connecting ‘stem’. The blossom cycle, C, is of odd length, |C| = 2k + 1,and contains exactly k matched edges. Observe this implies the cycle will be alternatingexcept for two adjacent edges, both unmatched. Call the vertex between them the root.Cycle C is then connected at the root to an even-length alternating path, the stem, ending4in some unmatched vertex. See Figure 2.1 (a) for a 5-cycle blossom.Before diving into the algorithm itself, it will be handy for us to set up a few preliminaryresults regarding the contraction of blossoms. First suppose the algorithm is at somestep with graph G and matching M the current state. Whenever the matching algorithmencounters a blossom the odd cycle will be contracted to a single vertex, producing a newgraph, G′, and contracting the matching into M ′. We would like for M ′ to be itself amatching.Proposition 2.1. Let G be a graph, M ⊂ E(G) a matching and assume there exists someblossom in G. We claim the new graph, G′, produced by contracting the blossom has M ′,the contraction of M , as a valid matching of G′.Proof:Let C be the blossom’s cycle, and w ∈ V (G′) the contraction of C. Observe that eachvertex of C was matched with one of its neighbours, save for possibly the root. Thus atmost one edge between the contracted vertex set and remainder of the graph could havebeen matched. We therefore have at most one edge in M ′ incident on w. Since all otheredges and vertices remain as they were in G, M ′ is a matching.It can further be shown that the new graph, G′, contains an augmenting path withrespect to M ′ if and only if G did with respect to M . In fact the augmenting path inG may be reconstructed from an augmenting path in G′. As the reader may expect,Edmond’s algorithm therefore involves contracting blossoms as we search for an augmentingpath. When such a path is found the algorithm translates it back into an augmenting pathof the original graph, intuitively by re-expanding the blossoms in reverse-chronological order.Proposition 2.2. Let G be a graph, M ⊂ E(G) a matching on it and C a blossom. DefineG′, and M ′ to be the graph and matching after contracting C. Then there exists anaugmenting path in G with respect to M if and only if one exists one in G′ with respect toM ′.Rather than provide a complete proof, which can be found in [3], we discuss the expan-sion process. To see how it works, suppose graph G′ was created from G by contractingblossom cycle C into vertex x. Let P ′ be a u − v augmenting path in G′. Let S be the‘pre-image’ of P ′ in G, namely those edges and vertices of G that are also found in P ′ plusthose edges and vertices of cycle C if x ∈ P ′. If P ′ does not contain x, we have immediatelythat the edges and vertices of S - being equal to those of P ′ - form an augmenting path.So we suppose P ′ contains x (see Figure 2.1 (b)). The two halves of P ′ before and after x5individually correspond to alternating paths in G, let them be P1 and P2 respectively. Weshow they can be connected by an alternating path through C.As in Figure 2.1 (a), let root and y be the two vertices of C connecting it with ouralternating paths. Because both of these vertices are ‘mapped’ to x, and P ′ is alternating,we have that exactly one of them is matched to a vertex outside of C. Without lossof generality, let it be root as in the figure. Since root matched outside of C, its twoadjacent edges within C must be unmatched (so this coincides with our earlier definitionof a blossom’s root). We can then choose the cycle path from root to y which ends on amatched edge (because |C| odd and C alternating, such a direction always exists). Let thisbe P3; in Figure 2.1 (a) this is the red half of the cycle. By then concatenating P1 with P3and P2 we can construct a u− v augmenting path of G.(a) Augmenting path in G (b) Augmenting path in G′Figure 2.1: Figure (a) displays a blossom cycle in red and purple. The red portion of theblossom taken with the path from root to u, and path from y to v forms an augmentingpath. Figure (b) shows the result of contracting the blossom to vertex x. (edges and verticesin the matching are bold, grey/dotted lines denote the arbitrarily long alternating path).We now describe (1), The Blossom Algorithm, in greater detail. The precise C++ imple-mentation can be found online at github.com [5]. In the remainder of this section we will6assume for simplicity that the graph in question is connected. Of course if it were not thematching algorithm could simply be run on each component individually.As usual let G = (V,E) be our graph and M our matching - initially M empty. Asmentioned above, at highest level our algorithm is simply to find augmenting paths, andaugment by them, until the matching is complete. In practice our implementation iteratesover all vertices of G and on finding an unmatched vertex the algorithm checks for anaugmenting path containing it. Since the matching will only be updated by taking thesymmetric difference with an augmenting path, we have that a vertex, once matched,remains matched throughout the algorithm. Furthermore, if a vertex has no augmentingpath rooted at it in the current state of M , we have the useful result that the vertex will notacquire an augmenting path at any later point during the algorithm either, see [4]. Thus asingle check of each vertex is sufficient to remove all augmenting paths and complete thematching.The Bipartite Case:Edmond’s algorithm succeeds by making each of the |V | searches for an augmentingpath relatively cheap. Recall that a graph G is bipartite if its vertex set may be split intotwo disjoint sets, A,B ⊂ V s.t. for all (x, y) ∈ E, x ∈ A and y ∈ B or the reverse holds. Wefirst consider the case where G is bipartite. This way, we can explain how an ‘alternating’tree is grown during the search for each augmenting path, without having to deal withblossoms just yet.Given an unmatched vertex v ∈ V , we explore via a modified breadth-first searchoutwards from it. At each step the tree of visited vertices, rooted at v, is extended byadding a path of length 2: x1, x2, x3 where x1 already in the tree and matched to theirparent, x2, x3 not yet in the tree, (x1, x2) unmatched and (x2, x3) matched. As a result,every path from root (vertex v) to leaf in the resulting tree will be even in length andalternating. We will refer to this as an alternating tree. Observe that finding an secondunmatched vertex adjacent to a leaf of this tree immediately gives us an augmenting path.In a bipartite graph growing the alternating tree from unmatched v ∈ V (G) is enough tofind an augmenting path from v, if one exists. To see this suppose there exists an augmentingpath from v and let u ∈ V be the unmatched vertex it terminates at. Then, since anyaugmenting path is of odd length, v and u must be in distinct sets of the bipartition and soall paths between them of odd length as well. Thus the search from v will find u on theend of an odd length path, and as this path is within the alternating tree it will then beaugmenting. We have in general that if an augmenting path exists, our search will find itor at least another augmenting path.7The General Case:While sufficient for the bipartite case, the above alternating tree algorithm may missaugmenting paths in a general graph. An example of this can be seen in Figure 2.2 where abreadth-first search of the type described above from vertex v will miss the augmentingpath traveling the long way around the cycle from v to x then to u. The important insighthere is that an alternating path entering a blossom through its root may leave again via anunmatched edge from any vertex of that blossom. This because each vertex is reachablefrom the blossom’s root by the two paths around the odd cycle, and one of those pathsmust end with a matched edge.Figure 2.2: A graph containing blossom and unmatched vertices u and v (matched edgesand vertices are bold). If the alternating tree is grown from u to v in a breadth-first mannerv will appear unreachable.Edmond’s blossom algorithm begins the search for an augmenting path from eachunmatched vertex by growing an alternating tree as in the bipartite case. However when ablossom is encountered - that is, when an edge is found that would complete a blossomcycle in the alternating tree - it is contracted. This contraction changes the current graphand matching as described previously, but also modifies the alternating search tree. For thealgorithm to continue recursively we need that the new tree is alternating as well.Suppose contracting blossom C of graph G with matching M produced new graph andmatching G′ and M ′. Let x ∈ E(G′) be the vertex C was contracted to, and T ⊂ G bethe alternating search tree with unmatched root r. Then we define T ′ ⊂ G′ as the set of8vertices and edges of T also in G′, plus vertex x. This is the contraction of T . We claimT ′ is an alternating tree in G′ with respect to M ′. Let y be the vertex in T the root of Cwas matched with. Then we have that y is matched with x in G′ (with respect to M ′). Byproposition 2.1 M ′ is a matching and so this is the only vertex matched with x. Any r toleaf path P ′ in T ′, passing through x, therefore takes a matched edge into x and unmatchededge out. Let the vertex following x, if any, be z. Then because the r to y and z to leafpaths were unchanged by the contraction and both alternating in G, both are alternatingin G′ as well. Additionally, as y and z matched with child vertices (vertices farther thanthemselves from the tree’s root) in G and G′ (by the previous work) we have that thesepaths concatenate with the y, x, z path in G′ to form an alternating r to leaf path. Thispath is precisely P ′, and so all paths of T ′ alternating as desired.Thus after contracting a blossom we arrive at a new graph, matching and alternatingtree and may continue our expansion of the tree, recursively contracting any blossoms wecome across. The blossom algorithm does exactly this, until either an augmenting pathhas been found, or the alternating search tree spans the entire current graph. In thelatter case we claim no augmenting path exists, implying one does not exist in the original(un-contracted) graph either. For a rigorous proof of this, and more precise descriptionof this version of the blossom algorithm, we direct the reader to Gabow’s 1972 publication [4].We have, with the addition of blossom contraction, that we are able to run a breadth-firstsearch for the augmenting path in the general graph case as well. This way the exponentialcost of checking all augmenting paths can be avoided: on finding an augmenting pathin the contracted graph the algorithm simply transfers it back to the original graph asdescribed previously. Completing such a search from every unmatched vertex in G once isthen sufficient to find a maximum matching.2.2 ModificationsWe have given an overview of Edmonds’ original algorithm, implemented as (1). We nowdiscuss the modifications made in (2) and (3). The C++ implementation of each of thesealgorithms can be also found online at github.com [5].(2) The Blossom Algorithm With QueueThe changes made in creating (2) from (1) were essentially details of implementation,however we feel they are important to note here as they resulted in a significant speed upof the running time, see Figure 2.4.The part of code modified was the underlying implementation of the queue used duringour breadth-first augmenting path search. Loosely speaking, a queue is an ordered container9or collection of elements such that new elements are added at the front of the queue, as thenew first element, and only the last element can ever be removed. This way elements areremoved from the queue in the same order they were inserted.Essentially algorithm (2) was the result of switching the queue implementation from anarray-based queue to the C++ standard library (STL) deque, or doubly-ended queue. Thearray-based queue simply stored queue elements sequentially in memory, with a pointer tothe front and back for O(1) access. The drawback to this technique was the large overheadin allocating the array ahead of time. By switching to the STL deque we allowed thelibrary implementation to decide when and how much space to allocate, resulting in a moreconservative usage of memory.(3) The Naive AlgorithmA number of changes were made in (3) in an attempt to reduce the number of blossomsformed during the search for augmenting paths. A new breadth-first searching method waswritten, BFSnaive, which ignored the new alternating paths introduced by any blossomsfound as the alternating tree was grown. This way the breadth-first search complexitywas retained, while the overhead of blossom contraction avoided. However it is certainlypossible that the only augmenting paths of the current matching were contained among thealternating paths skipped by BFSnaive. Thus BFSnaive may not always find an augmentingpath when one exists.A second feature added to BFSnaive was the ability to limit the maximum searchdepth, or height, of the alternating tree. Given this algorithm (2) first calls BFSnaive withmaximum depth one on each vertex v ∈ V - effectively attempting to match every vertexwith one of its neighbours. After this BFSnaive is called again, but with maximum depth 3.The algorithm could easily be modified to continue increasing the maximum depth, but forthe purpose of our tests we returned to using the breadth-first search call of algorithm (1)at this point, effectively running Edmonds’ on G with the partial matching found from theprevious steps.2.3 Regression TestingAll graphs used to analyse the behaviour of our 3 algorithms were randomly generatedusing the Erdo¨s-Re´nyi random graph model. These graphs were created by including eachedge of a 10, 000 vertex graph with probability ranging from p = 0.00001 to p = 1 (the codemay be found on github [5]). As all graphs were generated immediately before use and thendiscarded the correct maximum matching size was rarely known, outside of an estimation,before running the algorithms. For this reason new bugs could remain undetected for sometime if they did not dramatically alter the algorithm speed or matching size. To help10alleviate this problem, a testing suite of fixed graphs was constructed and frequently run.Eight graphs were used in total, their generating probabilities and maximum matching sizescan be found in Figure 2.3. The ‘correct’ matching sizes were decided by by algorithm (1),before any modifications to the algorithm. By regularly running the tests we were able toensure all algorithms agreed on the maximum matching of each of these graphs throughoutcode development.1 0.5 0.25 0.1 0.01 0.001 0.0001 0.00001|M | 5000 5000 5000 5000 5000 5000 2723 450Figure 2.3: Regression test data, each column corresponds to a graph on 10, 000 vertices.The first row contains the probabilities used to generate the graphs, the second the resultingsize of a maximum matching on that graph.2.4 Complexity and Running TimeThe time complexity for our implementation of Edmond’s algorithm on a graph G = (V,E)is O(|E||V |α(|E|, |V |)) where α is the 2-argument inverse Ackermann’s function, as theliterature frequently notes α(x, y) < 4 for all practical purposes [7]. A derivation of thecomplexity can be found in [4], though there they use a Gabow-Tarjan set-union in blossomcontraction to shave off the α(|E|, |V |) factor.Though the complexity was unchanged with the queue to deque changes made in algo-rithm (2) we saw a decrease in actual running time, especially as the graph became moresparse (see Table 2.4). As discussed in section 3.2, this is most likely attributable to theimplementation of the queue used in the breadth-first search step of the algorithm.In Figure 2.4 it appears that the additions made to algorithm (3), the initial attemptto match each vertex with their neighbour and then with a vertex distance three away,induced a significant speed up. However this effect was further investigated by measuringand removing the time spent on memory allocations, as shown in Figure 2.5. Here wecan see the operational time of algorithm (3) is actually slightly greater than that of (2)- though these measurements were made with calls to the C++ clock() function, and soinclude some margin of error (on the order of microseconds).111 0.1 0.01 0.001 0.0001 0.00001Alg (1) 0.24100 0.27834 0.28442 0.28789 0.20476 0.04024Alg (2) 0.24458 0.21663 0.22215 0.21906 0.15875 0.03429Alg (3) 0.02273 0.02248 0.02344 0.03070 0.04977 0.00358Figure 2.4: Time, in seconds, for algorithms (1) The Blossom Algorithm, (2) The BlossomAlgorithm With Queue, and (3) The Naive Algorithm, to find maximum matchings onrandomly generated graphs. Time includes that of memory allocation. Columns indicateprobability p used to generate graphs, |V (G)| = 10, 000 for all. Times were averaged over 4runs. See code online [5].1 0.1 0.01 0.001 0.0001 0.00001Alg (2) 0.01053 0.01108 0.01407 0.01466 0.00461 0.00071Alg (3) 0.01088 0.01285 0.01367 0.01661 0.00804 0.00112Figure 2.5: Time, in seconds, for algorithms (2) The Blossom Algorithm With Queue, and(3) The Naive Algorithm, to find maximum matchings on randomly generated graphs. Timeexclude that of memory allocation. Columns indicate probability p used to generate graphs,|V (G)| = 10, 000 for all. Times were averaged over 4 runs. See code online [5].We believe the algorithm (1) to (2) speed up in running time seen when memory alloca-tion time is included is due to the lack of allocation overhead in our neighbour matching stepwith BFSnaive. It is very likely that the operations performed during this step, especially ina dense graph, are very close to those the original algorithm (1) would make. The differenceis that the original algorithm must allocated space for a full breadth-first search from avertex, even when it ends up matching that vertex with its neighbour.3 Matchings on a Few Special Classes of GraphThough the asymptotic expected behaviour of our algorithm was tested on randomlygenerated graphs, we also investigated the running time on two special cases of graph.3.1 Maximal Matchings in Odd-Sized GraphsA perfect matching certainly cannot be found given G with |V (G)| odd, but we wonderedif the maximum matching would be easier to find. The odd vertex out could potentially actas a free parameter and allow for a greater number of maximal matchings. However this12advantage did not appear experimentally. In fact as can be seen in Table 3.1, for densegraphs the free vertex caused a significant slowdown in the algorithm’s speed.To determine if this was due to a final, futile, blossom-heavy search being performedout from the unmatched vertex, we modified the algorithm to terminate before that vertex.This caused a slight speed up, as can be seen from the third row of Table 3.1, however indense graphs the even case remains mysteriously far quicker.1 0.1 0.01 0.001 0.0001 0.0000110, 000 0.21615 0.20522 0.20817 0.21473 0.15445 0.032669, 999 no skip 3.76749 0.57122 0.25309 0.21138 0.15119 0.032859, 999 with skip 3.65503 0.55409 0.23924 0.21274 0.14782 0.03180Figure 3.1: Time, in seconds, including that of memory allocation, for algorithm (1) to findmaximum matchings on graphs on 10, 000 and 9, 999 vertices. Columns indicate probabilityp used to generate graphs. Running times were averaged over 4 tests. The final row displaysrunning times when the algorithm skips attempting to match the final vertex. See codeonline [5].3.2 Tutte’s TheoremWe were interested in investigating graphs lacking a perfect matching for more subtlereasons than that they contained an odd number of vertices, or an odd sized component.These are graphs to which Tutte’s theorem usefully applies.Proposition 3.1. (Tutte’s Theorem) Graph G = (V,E) has a perfect matching if and onlyif for all U ⊂ V , the subgraph induced by V \U has at most |U | connected components withodd size.In the above theorem, the ‘induced’ subgraph of U is the subgraph H = (U,E′) where(x, y) ∈ E′ ↔ (x, y) ∈ E and x, y ∈ U .Unfortunately the problem of actually finding graphs of this kind proved to be a hardone, especially on large vertex sets. We were able to find examples on 1, 000 vertices, butwere unable to find large differences in the running times there. The average running timeof algorithm (1) on five of these graphs was 0.007311 seconds, while five graphs with perfectmatchings took an average of 0.006904 seconds each. We note however that the difficulty offinding a random graph on 10, 000 or more vertices with this condition implies that thiscase is a rare one and likely insignificant to the asymptotic behaviour of the algorithm ingeneral.134 Asymptotic BehavioursThe asymptotic behaviours of a number of graph properties were examined, as we investi-gated possible contributors to the running time trends. For the remainder of this sectionwe let n = |V (G)| and p be the probability used in generating our random graphs via theErdo¨s-Re´nyi model.4.1 BlossomsIn the interested of determining the cost of blossom contraction to the overall algorithm werecorded the number of blossoms found and contracted in the graph during the operation ofalgorithm (1). We discovered for fixed n = |V (G)| the number of blossoms seems to jumpdramatically around probability p = 2n (see Figure 4.1).5/n 3/n 2/n 1/nn = 100 34 12 1 0.2n = 1, 000 512 130.4 1 0n = 10, 000 9014.6 2726.8 1 0.2n = 100, 000 201167 63421.2 1 0Figure 4.1: Average number of blossoms contracted when running algorithm (1) on 5randomly generated graphs. Rows indicate graph size |V (G)|, columns the probability pused in generating the graph, defined with respect to the number of vertices n.We investigated the expected number of cycles and matching size but neither seemedobviously related to the trend in blossoms found. For example, the expected number ofcycles of size k in a random graph generated with probability p on n vertices is(nk)pk, andthe total number of cycles therefore∑nk=3(nk)pk = (p+ 1)n − 1− (n2)p2.4.2 Matching SizeOne other trend we found interesting was that of the maximum matching size. Givenprobability p = c/n, for c fixed, the max matching appeared to grow linearly with n = |V (G)|(see Figure 4.2).145/n 3/n 2/n 1/nn = 100 49.6 45.4 41 25.8n = 1, 000 494.8 464.8 382.8 277n = 10, 000 4960 4634.4 3930.8 2733.6n = 100, 000 49637.8 46408.4 39161.8 27220.8Figure 4.2: Maximum matching size, averaged over 5 randomly generated graphs. Rowsindicate graph size |V (G)|, columns the probability p used in generating the graph, definedwith respect to the number of vertices n.We hypothesized that the maximum matching size was largely controlled by the numberof odd components, an odd component being perhaps the simplest structure without aperfect matching. In Figure 4.3 we have the average number of odd components found.5/n 3/n 2/n 1/nn = 100 2.4 6.4 14.8 40.8n = 1, 000 10 55.2 131.2 406n = 10, 000 71.2 500 1415.6 4078.8n = 100, 000 681.6 5042 14156.8 40921.2Figure 4.3: The average number of odd components found in 5 randomly generated graphs.Rows indicate graph size |V (G)|, columns the probability p used in generating the graph,defined with respect to the number of vertices n.Given the number of odd components in a graph we can upper bound the matching sizeby noting each pair of odd components effectively reduce the maximum matching size byone. Comparing Table 4.3 with 4.2 we see that n/2 minus half the value of each 4.3 tableentry is indeed an upper bound on the size of the resulting matching.4.3 AcknowledgementsThe author would like to thank fellow student Paul Liu for his ongoing support and proof-reading help; her parents who didn’t seem to mind (nearly enough) when their daughterpostponed returning home for the holidays by a week to complete various projects (amongthem this essay); and finally Professor Richard Anstee, for taking time out of his day todiscuss this, the ‘least-applicable’ case of matching, as well as his endless supply of questions,practical advice and conversation.15References[1] J. Edmonds. Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17:449-467,1965.[2] LEDA C++ class library by Algorithmic Solutions.http://www.algorithmic-solutions.com/leda/about/index.htm[3] R. Tarjan. “Sketchy Notes on Edmonds’ Incredible Shrinking Blossom Algorithmfor General Matching” (Course Notes). Department of Computer Science, PrincetonUniversity.http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf[4] H. Gabow. An Efficient Implementation of Edmonds’ Maximum Matching Algorithm.Journal of the ACM, 23(2):221-234, 1976.[5] Edmonds’ Blossom Algorithm C++ implementation.https://github.com/krstnmnlsn/blossom[6] ‘Nitron’. An In-Depth Study of the STL Deque Container.http://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container[7] Wikipedia article on the (inverse) Ackermann function.http://en.wikipedia.org/wiki/Ackermann_function#Inverse16

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.42591.1-0220735/manifest

Comment

Related Items