“Matchmaker”: Edmonds’ Algorithm for Maximum Weighted Matching

Intro

I was recently invited by the academic team “DN” (the name, surprisingly, has no inappropriate connotation) to compete in Mentor High School’s second CTF iteration, MHSCTF 2023. Although the competition ran for 15 days, we maxed out their 11 challenges in just under 16 hours (ignoring solve resets) and managed to take first place. This writeup was part of the verification process, which came with prize-receiving — enjoy!

Matchmaker

Solvers

flocto ,

enscribe

Author

0xmmalik

Graph Theory Fundamentals

This challenge is a classic example of a concept called “maximum weight matching,” which is fundamental in graph theory and discrete mathematics. Although there is a relatively high prerequisite knowledge floor for understanding these concepts, I’ll explain them as best as I can.

Firstly, let’s define a graph. A graph is a set of vertices (or nodes), which are connected by edges. Not to be confused with the Cartesian coordinate system, graphs are represented by the ordered pair $G = (V,\ E)$ in which $V$ is a set of vertices and $E$ is a set of edges:

Graph

A set of edges $E$ is defined as:

E \subset \{(x, y)\ |\ (x, y) \in V^2 \textrm{ and } x \neq y\}

By this definition, $x$ and $y$ are the vertices that are connected to the edge $e$ , called the endpoints. It can also be said that $e$ is incident to $x$ and $y$ .

We can create a matching $M \subseteq E$ within the graph $G$ , in which $M$ is a collection of edges such that every vertex $v$ of $V$ is incident to at most one edge of $M$ (meaning two edges cannot share the same vertex). When the highest possible cardinality (number of matches) of $G$ is reached, the matching is considered maximum, and any vertex $v$ not incident to any edge in $M$ is considered exposed.

Formally, a matching $M$ is said to be maximum if for any other matching $M'$ , $|M| \geq |M'|$ . In other words, $M$ is the largest matching possible.

For example, the following is a maximum matching performed on the graph above:

Matching

Since there is an exposed vertex in this graph (and because the size of $V$ is odd), $G$ is not considered perfect. A perfect maximum matching occurs when the size of $V$ is even (or $|V|/2 = |E|$ ) and there are no exposed vertices.

Now, let’s put weights into consideration (i.e. the students’ ratings). With a weighted graph $G = (V,\ E,\ w)$ , we can attribute a function $w$ that assigns a weight $w(e)$ to each edge $e \in E$ (defining $w : E \rightarrow \mathbb{N}$ ):

Weights

The total weight of a matching $M$ , written as $w(M)$ , can be defined as:

w(M) = \sum_{e \in M}w(e) \\\\

Solving for $w(M)$ in the example graph above:

w(M) = w((1, 2)) + w((3, 4)) + w((5, 6)) + w((8, 9)) \\\\ w(M) = 5 + 2 + 9 + 6 = 22

Our goal is to maximize $w(M)$ — it is definitely not maximized above, since $W(M)$ is not at its highest possible value. We will be tackling it with a combination of two different concepts: Edmonds’ blossom algorithm, and the primal-dual method. Although the blossom algorithm is typically meant for maximum cardinality matching (maximizing the size of $M$ itself, and running in $\mathcal{O}(|E||V|^2)$ time), utilizing it as a subroutine alongside the primal-dual method of linear programming creates a maximum weight matching (and running in $\mathcal{O}(|V|^3)$ time).

Firstly, let’s get started with how it works.

The Blossom Algorithm

The core idea behind the blossom algorithm itself involves two concepts: augmenting paths and blossoms (alongside blossom contraction).

Augmenting Paths

Given a graph $G = (V,\ E)$ , a path $P$ in $G$ can be considered an alternating path if edges in the path are alternatively in $M$ and not in $M$ . Augmenting paths are a type of alternating, odd-length path that starts and ends with two exposed vertices:

Augmenting Paths

As we can see, $P$ is considered an augmenting path because it ends with two exposed vertices. Augmenting paths are special in that they can augment (“to improve”, as per the name) the size of $M$ by one edge. To do so, simply swap the edges in $P$ that are in $M$ with the edges that are not in $M$ :

Augmented Path

A matching augmentation along an augmenting path $P$ is a process by which $M$ is replaced by $M'$ , defined as such:

M' = M \oplus P = (M \setminus P) \cup (P \setminus M)

This implies that $|M \oplus P| = |M| + 1$ .

The reason why augmenting paths are so fundamental to the blossom algorithm is that it directly computes a maximum matching — we can reiterate the process of finding augmenting paths until no more are available in $G$ . This is described well with Berge’s Theorem:

Theorem: A matching $M$ in a graph $G$ is maximum if and only if there is no $M$ -augmenting path in $G$ .

Here is high-level pseudocode which describes this recursive iteration:

procedure find_maximum_matching(G, M)
    P = find_augmenting_path(G, M)
    if  P == [] then
        return M
    else
        MP = augment_matching(M, P)
        return find_maximum_matching(G, MP)
    end if
end procedure

Note: Under the context of the above pseudocode, find_augmenting_path(G, M) will always start at an exposed vertex, running a breadth-first search to find an augmenting path.

Therefore, the blossom algorithm will always terminate with a maximum matching.

Blossoms (and Blossom Contraction)

The second concept that we need to understand are blossoms. Given a graph $G$ and a matching $M$ , a blossom $B$ is a “cycle” within $G$ which consists of $2k + 1$ edges, of which exactly $k$ belong to $M$ (a blossom with two matches would have $2(2) + 1 = 5$ edges).

Let’s say the algorithm created matchings in a graph with a blossom — although it isn’t the maximum matching possible, we cannot augment it any further because the technically available augmenting path is longer than the shortest available path, therefore terminating subotimally:

Blossom

This is where blossom contraction comes in. The idea is to contract the blossom $B$ into a single “super-vertex” $v_B$ , and to treat it as a single vertex in the graph:

Blossom Contraction

From there, we can find valid augmenting paths to augment $M$ :

Augmented Blossom

Finally, we can expand the blossom $B$ back into its original form, to reveal the maximum matching:

Expanded Blossom

Theorem: If $G'$ a the graph formed after contraction of a blossom $B$ in $G$ , then $G$ has an augmenting path if and only if $G'$ has an augmenting path.
(This is called the Blossoms Theorem, or the Main Theorem of Botany)

With the fundamental concepts of this beautiful algorithm covered, the only thing we need to wrap our heads around is how to adopt this with weighted graphs. I’ll be referencing Galil’s Efficient Algorithms for Finding Maximum Matching in Graphs for this section.

Primal-Dual Method

So… the primal-dual method. I’ve been personally studying this topic (alongside linear programming in general, from which this method is derived from) for the past couple days after I solved the challenge, and let’s just say that I absolutely have no clue what is going on:

$Scary Math$

I’ll just sweep it under the rug right now, since we’ll simply be “borrowing” an implementation of the above algorithm to solve this challenge. Let me know if you are knowledgable in this area and would like to contribute to this section!

”Borrowing” an Implementation

Yes, the blossom algorithm is the most elegant thing I’ve ever seen. No, I am absolutely never going to implement it from scratch. I’m not even going to try. Yes, it’s super fun to visualize and understand the concepts, but could you even imagine trying to implement this in code, and deal with “neighbors” and “forests” and “visited nodes?” I can’t.

Currently, we have tried two implementations which work for this challenge in Python3.9: van Rantwijk’s, and the NetworkX Python library. Both run in $\mathcal{O}(n^3)$ time, which is still reasonable for our range of $50 < N < 100$ , $N \bmod 2 = 0$ . Duan and Pettie overview an approximate method for maximum weight matching, which runs in linear time.

We’ll begin by parsing the input.

Parsing Input

Let’s start with a quick recap of what the netcat server gave us. We have $N$ lines, with $N$ representing the amount of students in the classroom (in addition to being an even amount). Each line will contain $N - 1$ integers $w$ representing the rating that student has for the individual at that index (accommodating for the skipped index representing themselves).

We can pass the input into a variable data with pwntools’s recvuntilS method, which will receive data until it sees the specified string. We’ll use b'> ' as the string to stop at, since that’s the prompt the server gives us.

Once we have the data, let’s convert it into something we can work with — we’ll make a 2x2 matrix so we can access both the student and their rating of another. We should also insert a 0 at the index which the student skipped themselves so the matchings don’t get screwed up:

matchmaker.py

from pwn import remote
 
def parse_input(data):
    # [:-1] Removes the trailing '> '
    data = data.splitlines()[:-1]
    data = [x.split() for x in data]
    table = [[int(x) for x in row] for row in data]
    # Insert 0 at the index which the student skipped themselves
    for i in range(len(data)):
        table[i].insert(i, 0)
    return table
 
p = remote('0.cloud.chals.io', [PORT])
data = parse_input(p.recvuntilS(b'> '))
print(data)

Parsing Input

Let’s do some premature optimization and type hinting because I’m a nerd:

matchmaker.py

from pwn import remote
 
def parse_input(data: str) -> list[list[int]]:
    data = [list(map(int, x.split())) for x in data.splitlines()[:-1]]
    [data[i].insert(i, 0) for i in range(len(data))]
    return data
 
def main() -> None:
    p = remote('0.cloud.chals.io', [PORT])
    data = parse_input(p.recvuntilS(b'> '))
    print(data)
 
if __name__ == '__main__':
    main()

Type Hinting

Testing the script:

$ python3 matchmaker.py
[+] Opening connection to 0.cloud.chals.io on port [PORT]: Done
[[0, 39, 79, 40, 92, 6, 36, 10, 23, 53, 22, 1, 95, 23, 28, 53, 12, 19, 21, 89, 91, 17, 1, 45, 9, 37, 97, 68, 40, 96, 69, 17, 50, 98, 79, 33, 44, 18, 38, 31, 33, 84, 94, 64, 11, 64, 24, 82, 25, 0, 72, 99, 51, 58, 85, 60, 81, 68, 68, 93, 73, 51, 84, 56, 19, 48, 5, 69, 38, 55, 74, 81, 41, 0, 64, 42, 1, 60, 47, 89, 64, 26, 96, 10], [3, 0, 8, 70, 90, 46, 65, 81, 94, 86, 22, 56, 48, 66, 0, 13, 73, 61, 71, 86, 25, 98, 40, 58, 79, 84, 80, 99, 17, 75, 60, 74, 39, 18, 77, 4, 63, 96, 29, 68, 54, 44, 2, 48, 59, 34, 24, 18, 95, 13, 3, 53, 40, 70, 28, 60, 13, 59, 72, 74, 47, 30, 94, 48, 82, 61, 58, 41, 84, 88, 67, 64, 8, 0, 97, 22, 86, 2, 93, 4, 55, 53, 15, 70],

Nice. Let’s move on to the actual algorithm.

Maximum Weight Matching

This solve utilizes the NetworkX library’s algorithms.matching.max_weight_matching function, which takes a NetworkX Graph class as input (the equivalent of $G$ ) and returns a set of tuples (e.g. {(29, 14), (48, 21), (0, 39), (23, 19), ...}) representing the endpoints of the edges in $M$ .

We’ll import networkx.algorithms.matching as matching for our blossom algorithm wrapper, and networkx as nx for our Graph class. In terms of weight, we need to convert the students’ ratings into “biweights” (e.g. $w(0, 1) + w(1, 0)$ ) because the ratings they have for each other aren’t necessarily symmetric:

Biweight

Each “biweight” now represents the total score of the match, which was mentioned in the author’s notes. We’ll be able to pass this into the max_weight_matching() function as the weight parameter.

To test the algorithm, we’ll use the following dummy input (note that inverse repetition is allowed):

Input: [[0, 0, 100, 0], [0, 100, 0, 0], [0, 100, 0, 0], [100, 0, 0, 0]]
Expected Output: [(0, 3), (1, 2), (2, 1), (3, 0)]

In theory, the following script should pair the zeroth student with the third student, and the first student with the second:

matchmaker.py

from pwn import remote
import networkx as nx
import networkx.algorithms.matching as matching
 
def parse_input(data: str) -> list[list[int]]:
    data = [list(map(int, x.split())) for x in data.splitlines()[:-1]]
    [data[i].insert(i, 0) for i in range(len(data))]
    return data
 
def main() -> None:
    p = remote('0.cloud.chals.io', [PORT])
    data = parse_input(p.recvuntilS(b'> '))
    data = [[0, 0, 100, 0], [0, 100, 0, 0], [0, 100, 0, 0], [100, 0, 0, 0]]
    G: nx.Graph = nx.Graph([(i, j, {'weight': data[i][j] + data[j][i]}) for i in range(len(data)) for j in range(len(data[i])) if i != j])
    M: set[tuple] = matching.max_weight_matching(G, maxcardinality=True)
    M_S: list[tuple] = sorted(list(M) + [(b, a) for a, b in M])
    print(data)
    print(M_S)
 
if __name__ == '__main__':
    main()

Maximum Weight Matching (test case)

Testing the script:

$ python3 matchmaker.py
[(0, 3), (1, 2), (2, 1), (3, 0)]

The script works locally! Let’s alter it to include the three iterations (alongside the correct formatting, e.g. 0,3;1,2;2,1;3,0;4,5;5,4) so that it can work with the remote server:

matchmaker.py

from pwn import remote
import networkx as nx
import networkx.algorithms.matching as matching
 
def parse_input(data: str) -> list[list[int]]:
    data = [list(map(int, x.split())) for x in data.splitlines()[:-1]]
    [data[i].insert(i, 0) for i in range(len(data))]
    return data
 
def main() -> None:
    p = remote('0.cloud.chals.io', [PORT])
    for _ in range(3):
        data = [[0, 0, 100, 0], [0, 100, 0, 0], [0, 100, 0, 0], [100, 0, 0, 0]]
        data = parse_input(p.recvuntilS(b'> '))
        G: nx.Graph = nx.Graph([(i, j, {'weight': data[i][j] + data[j][i]}) for i in range(len(data)) for j in range(len(data[i])) if i != j])
        M: set[tuple] = matching.max_weight_matching(G, maxcardinality=True)
        M_S: list[tuple] = sorted(list(M) + [(b, a) for a, b in M])
        result: str = ';'.join([f'{a},{b}' for a, b in M_S])
        print(data)
        p.sendline(result.encode())
 
    p.interactive()
 
if __name__ == '__main__':
    main()

Final Script

Running the script:

$ python3 matchmaker.py
[+] Opening connection to 0.cloud.chals.io on port [PORT]: Done
[*] Switching to interactive mode
Congratulations! Here's your valentine: valentine{l0V3_i5_1n_7he_4ir}
[*] Got EOF while reading in interactive

We’ve successfully performed a maximum weight matching utilizing the blossom algorithm and the primal-dual method!

Afterword

Wow, this challenge was definitely a rabbit hole. Even though the author never actually intended for us to go this deep into the math behind it (and for me to skip out on my Calculus classes to learn graph theory and discrete math), I really don’t like ignoring concepts (or in this case, a wrapper function) simply because their prerequisite knowledge floors are either too high or too intimidating. Obviously I was a lost sheep when I was initially researching the blossom algorithm (as this is my first algo challenge, ever), but I just love the feeling when you tear through all the layers abstractions and finally get to the juicy, low-level bits.

I’m glad that our team was able to get first blood one this one, and I’m glad this beautiful algorithm was the first one I’ve learned. I hope you enjoyed this writeup, and I hope you learned something new!

“Matchmaker”: Edmonds’ Algorithm for Maximum Weighted Matching

Table of Contents

Intro

Matchmaker

Graph Theory Fundamentals

The Blossom Algorithm

Augmenting Paths

Blossoms (and Blossom Contraction)

Primal-Dual Method

”Borrowing” an Implementation

Parsing Input

Maximum Weight Matching

Afterword

References