15.3. Crown Reduction

Given a graph \(G = (V,E)\), a crown is an ordered pair \((I, H)\) of disjoint subsets of \(V\) that is surprisingly useful for constructing linear-size kernels for a range of graph problems. We first define the properties that \((I, H)\) must satisfy to be a crown and show how to find a crown in a bipartite graph efficiently. Then we show how to use crowns to construct a kernel of size at most \(3k\) for the vertex cover problem and a kernel of size at most \(2k\) for the maximum satisfiability problem. Note that this is a marked improvement over the vertex cover kernel obtainable using simple reduction rules, which had quadratic size.

A crown in a graph \(G = (V,E)\) is a pair \((I, H)\) of disjoint subsets of \(V\) that satisfy the following properties:

• Every neighbour of every vertex in \(I\) belongs to \(H\). As a consequence, \(I\) is an independent set.
• The bipartite graph \(G[I, H] = (I, H, \{ (u, w) \in E \mid u \in I, w \in H \})\) has a matching of size \(|H|\).

This is illustrated in Figure 15.3.

Figure 15.3: Coming soon!

To get a glimpse of why crowns may be useful, consider the degree-\(1\) reduction in the vertex cover kernelization discussed in Section 15.2.1: If \(u\) is a degree-\(1\) vertex and \(v\) is its only neighbour, then \((\{u\}, \{v\})\) is a crown! For this particular type of crown, we argued that there always exists a minimum vertex cover that includes \(v\) but not \(u\). The crown reduction kernelization for vertex cover in Section 15.3.1 extends this reasoning to arbitrary crowns and shows that there always exists a vertex cover that includes all vertices in \(H\) and none of the vertices in \(I\).

Lemma 15.11: If \(G = (U, W, E)\) is a bipartite graph, then either \(G\) has a crown \((I, H)\) with \(I \subseteq U\) and \(H \subseteq W\) or a matching \(M\) that matches every vertex in \(U\). Such a crown \((I, H)\) or matching \(M\) can be found in \(O\bigl(\sqrt{n}m\bigr)\) time.

Proof: Let \(M\) be a maximum matching of \(G\). If \(M\) matches every vertex in \(U\), it is the desired matching. Otherwise, let \(\emptyset \subset U' \subseteq U\) be the set of all vertices in \(U\) not matched by \(M\). Let \(Z\) be the set of all vertices reachable from \(U'\) via alternating paths with respect to \(M\). Then we prove that \((I,H)\) is a crown, where \(I = U \cap Z\) and \(H = W \cap Z\). We need to verify that the pair \((I, H)\) satisfies the two properties of a crown.

First we prove that the graph \(G[I, H] = (I, H, \{ (u, w) \in E \mid u \in I, w \in H \})\) has a matching of size \(|H|\). Observe that every vertex \(w \in H\) is reachable from a vertex \(u' \in U'\) via an alternating path \(P\) of odd length. Since \(u'\) is unmatched, \(w\) must be matched; otherwise, \(P\) would be an augmenting path for \(M\) and \(M\) would not be a maximum matching. This proves that every vertex \(w \in H\) is matched. Since \(P\) has odd length and starts at an unmatched vertex \(u' \in U\), its last edge is unmatched and the path obtained by appending the edge \((u, w) \in M\) incident to \(w\) to \(P\) is an alternating path from \(u'\) to \(u\), that is, \(u \in I\). This shows that the edge \((u, w) \in M\) incident to each vertex \(w \in H\) is in \(G[I,H]\), that is, \(G[I,H]\) has a matching of size \(|H|\).

To prove that every neighbour of any vertex in \(I\) belongs to \(H\), observe that since \(G\) is bipartite and \(I \subseteq U\), every neighbour of any vertex \(u \in I\) belongs to \(W\). We need to show that these neighbours belong to \(H = W \cap Z\), that is, we need to show that these neighbours are reachable from vertices in \(U'\) via alternating paths.

Every vertex \(u \in I\) is reachable from some vertex \(u' \in U'\) via an alternating path \(P\) of even length. In particular, since \(P\) starts with an unmatched edge, its last edge is matched. Thus, appending any unmatched edge \((u, w)\) incident to \(u\) to \(P\) produces an alternating path from \(u'\) to \(w\), that is, \(w \in Z\). This shows that every neighbour \(w\) of \(u\) such that the edge \((u,w)\) is unmatched belongs to \(H\). If \(u\) has an incident edge \((u, w) \in M\), then \(u \in I \setminus U'\), so \(P\) contains at least two edges. Since the last edge in \(P\) is matched and is incident to \(u\), the last edge in \(P\) is \((u, w)\) and the subpath of \(P\) from \(u'\) to \(w\) is an alternating path from \(u'\) to \(w\). Thus, \(u\)'s mate, if it exists, also belongs to \(H\). Therefore, \(H\) contains all neighbours of \(u\).

As for the cost of constructing the matching \(M\) or crown \((I, H)\), observe that, by Theorem 7.13, a maximum matching \(M\) of a bipartite graph \(G\) can be computed in \(O\bigl(\sqrt{n}m\bigr)\) time. Testing whether it matches every vertex in \(U\) takes \(O(n)\) time. If it does not, then the vertex sets \(I\) and \(H\) can be found in \(O(n + m)\) time using the algorithm from Lemma 7.10 for computing an alternating forest in a bipartite graph. ▨