imagine you're the head of a summer camp and your task is to group the attendees into pairs to make it as fair as possible you told each attendee to write cards with names of people they'd like to be paired with given these cards you'd now like to find a matching which in this case means the same thing as pairing such that the amount of people that wanted to be with one another is maximum you certainly could test all possible combinations but this would for larger groups take quite a while in this video we'll be describing
the much faster blossom algorithm for maximum matching in a graph developed by check edmonds a pioneer in many fields of computer science formally a graph consists of vertices connected by edges a matching in a graph is a subset of edges such that no two share a vertex the matching is maximum if it contains the most edges possible compared to other matchings for the given graph also we'll call vertices that are not in the matching exposed the core idea behind the algorithm are augmenting paths an augmenting path in a graph is an alternating sequence of matched
and unmatched edges where the first and the last vertex is exposed as the name suggests augmenting paths can improve or augment the size of the currents matching by switching the matched and unmatched edges as you can see the matching is still valid but its size increased by 1. one thing to note is that a graph contains an augmenting path if and only if the matching is not maximum this means that we can repeatedly improve the matching using augmenting paths until there are none left at which point we know the matching is maximum let's think about
how to find augmenting paths in a tree this is pretty straightforward we'll run a breadth first search or bfs for short from exposed vertices alternating between adding matched and unmatched edges the rest of the algorithm repeatedly improves the matching using augmenting paths and terminates when there aren't any remaining to better understand how this all works it will be best to see an example initially every vertex is exposed since the matching is empty the algorithm then picks one exposed vertex at random and runs the bfs [Music] here it successfully finds an augmenting path so it uses
it to improve the matching and repeat let's fast forward a bit until some larger augmenting path is found [Music] here is a longer path that the algorithm finds that neatly showcases the alternating edges [Music] finally once no augmenting path is found the algorithm terminates although trees are a large family of graphs we'd like our algorithm to work on all of them so let's look at a graph our algorithm will not work on imagine we already found some matching that isn't yet maximum and would like to improve it running the algorithm here wouldn't work since the
augmenting path is longer than the shortest path and is therefore not found the problem here is this part of the graph it consists of an odd cycle with alternating edges called the blossom hence the name of the algorithm and an alternating path ending in an exposed vertex called the stem to fix the problem we'll avoid it when we come from the stem into the blossom we'll do the following first we'll contract the blossom into a single vertex second we'll find an augmenting path in this new graph third we'll improve the matching using this augmenting path
and fourth we'll lift the path back to the original graph here we are relying on the fact that the graph has an augmenting path if and only if the contracted graph has an augmenting path adding this operation to our algorithm will be pretty straightforward each time we add unmatched edges we'll check for blossoms if found will contract the blossom find the augmenting path in this new graph and then lift back the rest of the algorithm hasn't changed at all as you can see it does exactly what i did before so again fast forward a bit
until something interesting happens [Music] here we can see the contraction in action once it finds the blossom it contracts it runs the algorithm again on the smaller graph finds the augmenting path improves the matching and then looks back after this it terminates since there are no more augmenting paths let's compare how fast our algorithm is to a naive solution for clarity let e be the number of edges and v the number of vertices when testing all possible combinations we have to check each subset of edges the number of subsets is 2 to the e each
edge either is in a subset or not so the naive algorithm is exponential as for the blossom algorithm it improves the matching at most v times during which the entire graph is explored taking time e but we could contract up to v times multiplying this together gives us the time complexity e times v squared which is polynomial and exponentially better than the naive solution but if there are only six attendees of your summer camp you can probably do it by hand you
