## 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

I’ve just had the most brilliant idea 😮 I want to write a program that takes all the students and how much they like each other to pair them up so I can maximize the total love in the classroom! Of course, when I say “I,” I really mean… “you” 😉

Notes: **[SEE BELOW]**

`nc 0.cloud.chals.io [PORT]`

**Warning**: Discrete math, graph theory, and combinatorial optimization ahead! If you’re unfamiliar with the mathematical symbols used in this writeup, reference this dropdown:

**Complicated Math Symbols**

- $\sum$ - Summation
- $\in$ - Element of
- $\notin$ - Not an element of
- $\subset$ - Proper subset of
- $\subseteq$ - Subset of
- $\emptyset$ - Empty set
- $\forall$ - For all
- $\exists$ - There exists
- $\nexists$ - There does not exist
- $\in$ - Element of
- $\notin$ - Not an element of
- $\ni$ - Contains as member
- $\not\ni$ - Does not contain as member
- $\setminus$ - Set minus (drop)
- $\oplus$ - Direct sum
- $\cup$ - Union
- $\cap$ - Intersection
- $x'$ - Prime

**First blood!** Here are the notes the author provided alongside the challenge description, abridged for brevity:

- The connection times out after 60 seconds, and there will be 3 iterations.
- The input will be given in $N$ lines, where $N$ represents the number of students. The first line represents the zeroth student, the second line represents the first student, and so on ($50 < N < 100$, $N \bmod 2 = 0$).
- Each line of input contains $N - 1$ integers $R$ (ranged $0 < R < 100$, inclusive); $R$ represents a student’s rating of another student at that index, repeated for everybody but themselves.

I’ve cut the notes provided in half to make it a bit more digestable. Before we continue, let’s see some sample input from the server for context:

We can do a bit of analysis on what we’ve received so far.

The first line, `86 60 67...`

, can be translated into:

- Student 0 -> Student 1 = 86
- Student 0 -> Student 2 = 60
- Student 0 -> Student 3 = 67

Let’s do the same thing for the second line, `76 0 74...`

:

- Student 1 -> Student 0 = 76
- Student 1 -> Student 2 = 0
- Student 1 -> Student 3 = 74

Notice how the student will always skip their own index, which aligns with the author’s notes detailing how the integers “represent the students ratings of everybody but themselves.” Let’s continue with the rest of the notes:

- Determine the pairings that maximize the students’ ratings for each other
**Example**: If Student 1 -> Student 7 = 98 and Student 7 -> Student 1 = 87, and Students 1 and 7 are paired, the*score*of this pairing would be $98 + 87 = 185$- The output should list all maximized pairs (including duplicates; order of the pairs does not matter)
**Example**: If Student 0 -> Student 3, Student 1 -> Student 2, and Student 4 -> Student 5, the desired output is:`0,3;1,2;2,1;3,0;4,5;5,4`

- The connection will close if the output is incorrect, and reiterate if correct

Let’s crack on with the actual algorithm which will be used for solving this!

### 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:

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:

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}$):

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:

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$:

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

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:

**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:

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:

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

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

**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:

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:

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

Testing the script:

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:

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):

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

Testing the script:

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:

Running the script:

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!

### References

- Anstee (UBC): “MATH 523: Primal-Dual Maximum Weight Matching Algorithm” (2012)
- Bader (TUM): “Fundamental Algorithms, Chapter 9: Weighted Graphs (2011)
- Blossom Algorithm (Brilliant)
- Blossom Algorithm (Wikipedia)
- Chakrabarti (Dartmouth): “Maximum Matching” (2005)
- Duan, Pettie: “Linear-Time Approximation for Maximum Weight Matching” (2014)
- Galil: “Efficient Algorithms for Finding Maximum Matching in Graphs” (1986)
- Goemans (MIT): “1. Lecture notes on bipartite matching” (2009)
- Goemans (MIT): “2. Lecture notes on non-bipartite matching” (2015)
- Karp (UC Berkeley): “Edmonds’s Non-Bipartite Matching Algorithm” (2006)”
- Monogon: “Blossom Algorithm for General Matching in O(n^3)” (2021)
- NetworkX Documentation
- Radcliffe (CMU): “Math 301: Matchings in Graphs”
- Shoemaker, Vare: “Edmonds’ Blossom Algorithm” (2016)
- Sláma: “The Blossom algorithm” (2021)
- Stein (Columbia): “Handouts - Matchings” (2016)
- Vazirani (UC Berkeley): “Lecture 3: Maximum Weighted Matchings”
- van Rantwijk: “Maximum Weighted Matching” (2008)