7.2. Maximal Matching

As a warm-up exercise, this section discusses the maximal matching problem. Given a graph \(G = (V, E)\), the problem is to find a matching \(M \subseteq E\) such that there is no matching \(M'\) that satisfies \(M \subset M' \subseteq E\). As an example, the blue matching \(M\) in Figure 7.2 is maximal because every edge not in \(M\) shares an endpoint with an edge in \(M\) and therefore cannot be added to \(M\) while keeping \(M\) a matching. \(M\) is not a maximum matching because both matchings in Figure 7.3 are bigger.

The algorithm to compute a maximal matching is extremely simple: We start by setting \(M = \emptyset\). Then we inspect every edge \(e \in E\) in turn. When inspecting \(e\), we add \(e\) to \(M\) if and only if \(e\)'s endpoints are unmatched at this time.

This algorithm can clearly be implemented in \(O(n + m)\) time using an adjacency list representation of the graph, which allows us to enumerate the vertices and edges of \(G\) in linear time and find the endpoints of each edge in constant time: First, we mark every vertex as unmatched; this takes \(O(n)\) time. Then we inspect every edge \(e \in E\). For each edge \((x, y)\), we check whether both \(x\) and \(y\) are unmatched. If so, we add \((x,y)\) to \(M\) and mark \(x\) and \(y\) as matched. This takes constant time per edge, \(O(m)\) time in total.

Lemma 7.2: A maximal matching of a graph \(G\) can be computed in \(O(n + m)\) time.

Proof: We already argued that the above algorithm takes \(O(n + m)\) time. To see that its output is a matching, assume the contrary. Then there exist two edges \(e\) and \(f\) in \(M\) that share an endpoint \(x\). If w.l.o.g. \(e\) is added to \(M\) before \(f\), then \(x\) is marked as matched after adding \(e\) to \(M\). Thus, when inspecting \(f\), \(x\) is matched, and we do not add \(f\) to \(M\), a contradiction.

To see that the computed matching \(M\) is maximal, assume that there exists an edge \((x,y) \in E\) such that \(M \cup \{(x,y)\}\) is also a matching. Then both \(x\) and \(y\) are unmatched at the end of the algorithm and thus also when the algorithm inspects the edge \((x,y)\). Therefore, we would have added \((x,y)\) to \(M\), a contradiction. ▨

A related problem is the independent set problem.

An independent set in a graph \(G = (V,E)\) is a subset \(I \subseteq V\) such that no two vertices in \(I\) are adjacent. See Figure 7.5.

Figure 7.5: A maximal but not maximum independent set (blue) and a maximum independent set (red). Both sets are vertex covers. The blue set is a minimum vertex cover, the red one is not.

Again, we can distinguish between a maximal independent set, which has no independent proper superset, and a maximum independent set, which is an independent set of maximum cardinality.

Exercise 7.4: Show that a maximal independent set of an arbitrary graph can be computed in \(O(n + m)\) time. (Hint: The algorithm is very similar to the maximal matching algorithm above.)

The maximum-cardinality variants of matching and independent set, on the other hand, are of very different difficulty. While the focus of this chapter is to demonstrate that a wide range of matching problems can be solved in polynomial time, finding a maximum independent set is NP-hard and in fact W[1]-hard, that is, unlikely to be fixed-parameter tractable. We will discuss fast exponential-time algorithms for finding a maximum independent set in Chapters 16 and 17.

Matchings are closely related to another classical NP-hard problem, the vertex cover problem, which is to find a minimum-size subset \(C\) of \(G\)'s vertices such that every edge of \(G\) has at least one endpoint in \(C\) (see Figure 7.5). Based on this connection, the matching algorithms discussed in this chapter will be used in fixed-parameter algorithms for the vertex cover problem.