The Perfect Matching: Part 3
The Graph Connection: Covers and Matching
Geometry
A linear optimization problem is open to geometric interpretation. In general, the decision space gets modeled as a convex polyhedron endowed with an interior (body or the bulk) and a hull (exoskeleton). In particular, the Assignment Problem (AP) gets modeled as variables stitched together (their linear combination) by coefficients whose sum equals unity. Every coefficient is positive and less than unity. That restricts the hull’s shape and defines its boundary.
- Searching for optimal solutions requires focusing on the hull’s surface. Garrett Birkhoff famously pointed out that the “extrema” lie at the vertices of the hull. They are nothing but permutation matrices. Moreover, the hull’s edges are their linear combination.
Expressed in this way, it almost sounds trivial that extremal points should lie at some intersection of a hull’s jagged edges. That begs the following questions:
- Which vertices have the optimal solutions?
- What is the path of quickest descent from an arbitrary point on its surface to an optimal vertex?
These questions suggest a desperate situation of being blindfolded. That, somehow, we are forced to stumble our way through the darkness of the convex hull to an extreme (optimal) point. Unfortunately, that’s true in the following sense. Our conscious minds didn’t evolve to grapple with convexity in higher dimensions. We need reliable shortcuts that make our quest less gnarly. And yet, ironically our conscious mind is an excellent general purpose pattern finder — convexity, permutations and finding patterns (algorithms) using geometry emerged from the minds of mathematicians. Graph Theory is one such technique. It rescues us from an otherwise explosive situation of finding the right permutations by finding patterns (also known as proving theorems in Graph Theory).
The Graph Connection
Let’s recap where we are in the story. An Assignment Problem led us to convex polytopes. Those, in turn, led us to permutation matrices. Now we want to introduce graphs in the mix. The uninitiated amongst us may wonder where all this is heading. Aren’t we making it more complicated than it ought to be? Perhaps. But if we pause and consider Complexity, the problem still appears intractable with n-factorial permutations to check. We still haven’t reduced it to arrive at the convex hull’s charmed vert-ex (-ices) we are after.
Sometimes in mathematics, unexpected connections emerge from seemingly unrelated quarters. They take us down blind alleyways that don’t necessarily make sense at first but end up getting us to our destination quicker. By clever reasoning and serendipitous convergences such as these, the tapestry of human knowledge gets enriched.
We must introduce the two Hungarian mathematicians, viz., Dénes Kőnig and Jenő Egerváry before introducing their ideas. They were graph theorists before there was the organized study of Graph Theory! Their life trajectories bear an uncanny resemblance — in both their body of work languishing in relative mathematical obscurity for decades and the tumultuous social circumstances resulting in their tragic fate of death by suicide. Their work was a remarkable half-century ahead of its time. They left a set of trailblazing mathematical ideas in their wake. An illustrious lineage of Hungarian mathematicians, the likes of John von Neumann, Pál Erdős, Tibor Gallai, Péter Lax, László Lovász, and Endre Szemerédi followed that took Algebra and Combinatorics in new directions and to new heights. Graph Theory is indispensable in modern social media/networking algorithms, the optimization problems underpinning machine learning, and in general, the thriving field of Operations Research.
Bipartite Graphs
Let’s return to our example illustration of tasks and bidders and how to match them optimally.
- Tasks: {A, B, C, D} | Contractors (Bidders): {I, II, III, IV}
It doesn’t make much sense to match a bidder to other bidders or a task to other tasks. The assignment problem makes it necessary to split them into two disjoint, independent but interconnected partitions (bi-partition). The weighted edges are shown connecting a bidder (vertex) to tasks (vertices in the other partition). They denote costs, completion times or qualification levels as the case might be. That is a Bipartite Graph. For those interested, this earlier post has the illustrative example we continue to discuss here.
Q: Why cast the problem as a bipartite graph?
A: To get simplifying insights into reducing its complexity.
The contributions of Kőnig and Egerváry on Bipartite Graphs shed light on how one can reduce its complexity. Kőnig published an entire treatise in 1935— Theorie der Endlichen und Unendlichen Graphen: kombinatorische Topologie der Streckenkomplexe which laid Graphs in a comprehensive mathematical foundation. Of particular interest is a theorem named after him. Before we get there, we need to introduce the ideas of Duality, Cover, and Matching.
Duality
The idea of duality can be understood using an anecdote. Given a fixed quantity of an arbitrary (scarce or limited) resource, its distribution gets constrained by the number of individuals vying for that resource. It’s characterized as zero-sum and conveys the sense that it doesn’t lend itself to egalitarian or open-ended distribution schemes. Instead, one gets compelled to rob Peter to pay Paul in divvying the lot.
Max/Min are Two Sides of a Zero-Sum Coin
An assignment optimizes some utility — the cost budget in our case. Because we primarily set out to minimize the cost budget (primal problem), we get a set of bidders satisfying it. On the flip side, were we to embark on optimizing for the bidders (the dual problem), we would end up minimizing the cost budget. In essence, maximum and minimum are two sides of the same zero-sum-coin. An interesting pattern emerges in that the dual problem converges to an identical optimal solution as the primal problem.
Cover/Matching
Kőnig’s Theorem on Bipartite Graphs bears his name because he proved it in 1916. It’s indispensable in solving the Assignment Problem. To unpack its gist, we need introduce two terms that quantitatively describe a graph. One is a view of the graph from an arbitrary vertex (or node) — its Cover. The other is a point of view from an edge — its Matching.
A cover used as verb means to “span or extend” as in cover an area or distance. A vertex cover is its reach in “covering” the graph with its tentacles — the edges emanating from it.
A vertex cover is a set of vertices that has one endpoint of every edge in a graph. For G = Vertices(U,V); Edges(E), each of its vertices U = {I, II, III, IV} and V = {A, B, C, D} have a certain reach — in other vertices they are connected to.
- Node IV covers four edges (a, e, f, g) highlighted in blue. All the rest, similarly have equal coverage. In general, any vertex can have a different reach insofar as it covering more (or less) than others in an arbitrary graph.
Matching quantifies connections from an edge’s perspective. An edge matches/pairs vertices. That signifies some relationship between them. If there is none, they remain unconnected. Vertices share an edge — there are twice as many vertices as there are edges. Unless its direction matters, it doesn’t make sense to double-count an edge. A matching is a set of edges with no common vertices — no two edges share a vertex.
Of all possible ways to cover edges (using vertices) a minimum vertex cover does so using the fewest number of vertices. They have at least one endpoint of every edge in the graph. The cardinality of the set is four, i.e., the set has four elements (shown on the graph to the left):
- Min Vertex Cover, Vʹ = {I:(c,i,k,q), II:(d,l,m,n), III:(b,h,j,p), IV:(a,e,f,g)}
Of all possible ways to match vertices, a maximum matching does so with the most number of edges such that no two edges share common vertices (shown as bold blue lines on the graph to the right). It’s cardinality is also four.
- Max Matching, Eʹ = {a:(B,IV), h:(D,III), n:(C,II), q:(A,I)}
It’s no coincidence that their cardinality should be equal. For any vertex, at most one edge can belong in a matching — which means the cardinality of matching (⎮E⎮) cannot exceed the cardinality of a cover (⎮V⎮) — it can at most be equal to that of a cover.
- ⎮E⎮ ≤ ⎮V⎮ for bipartite graphs
- ⎮Eʹ⎮ = ⎮Vʹ⎮ is the situation for a perfect match
The maximum cardinality of a matching is equal to the minimum cardinality of a vertex cover — Dénes Kőnig, 1916
This is the statement of Kőnig’s theorem for bipartite graphs. We notice a recurring theme here — the maximum (of matching) and minimum (of vertex cover) going hand-in-hand. Kőnig’s theorem opens up a possibility of starting with some arbitrary matching ⎮E⎮ and augment its cardinality (with an algorithm) until it can no longer exceed a limit ⎮Eʹ⎮. When that cardinality is reached, we have converged to a minimum vertex cover (⎮Vʹ⎮) and then it’s a signal for us to stop the optimization process. We have arrived at a vertex of the convex hull.
The Weighted Case
Egerváry extended this theorem to weighted bipartite graphs in 1931. The weights indicate the strength of the connecting edges. In our example, they could be the bid (dollar-figure quoted) for the completion of a particular task.
Given a matrix of weights (of the purported assignment problem) he imagined a covering system — a set of horizontal and vertical lines crossing its rows and columns. Any given row (or column) can be contained by the lines with some multiplicity. As lines crisscross multiple times, an optimization algorithm must prune them until a minimal cover is reached. In the end, a that covering will yield a maximal set of matching pairs (bidders to tasks with none overlapping).
The proof he outlined to show that a minimal covering system yields a maximal matching has (if one squints hard) the telltale signature of a computer algorithm. Before introducing the algorithm, we must introduce the man who, in 1955 (long before digital computers) composed a coherent algorithm by squinting hard. That man was Harold W. Kuhn. It took him a considerable amount of work and imagination to:
- assemble the significant pieces of knowledge about Bipartite Graphs (from the body of work by Kőnig, Egerváry)
- make the connection between The Assignment Problem and the extreme points on convex hull representing permutations (from the body of work by Birkhoff, von Neumann)
- come up with a creative solution (a shortcut, if you will, that doesn’t require imagining a convex hull in all its glory in higher dimensions).
The Hungarian Algorithm: A Preview
A solution that is a series of converging steps (operations), that even though our minds cannot visualize the path of steepest descent, signifies just that, but only in working with a matrix to arrive at the hull’s vertex. What it amounts to geometrically is choosing which direction to turn (a covering step) and subsequently to move in the chosen direction (the reduction step) so that we don’t have to feel our way through all n-factorial permutations blindfolded.
This is the seemingly mindless but reliable shortcut we wished for earlier. This is the shortcut I used a couple of decades ago in my undergraduate days without the aid of a computer. But once we see the insights afforded by these theorems, it’s a telling testament to the geometry of optimization. It gives us a shortcut — a map of the convex hull with its steepest pathways to take us to the optimal vertex.
He named the algorithm The Hungarian Method in honor of the two great Hungarian mathematicians. That will be discussed in the next installment in the fourth and final part in this series.
If you enjoy reading my posts and made this this far, please show your appreciation by clapping. Consider supporting by way of subscription and following. Thank you!
© Dr. VK. All rights reserved, 2022
References
- A geometrical interpretation of the Hungarian Method — Joachim Schmid, 1978
- Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication — Silvano Martello, 2010
This is the continuation the following series of posts:
