17.2.3. The Algorithm

We are now ready to present our algorithm for finding an element in \(\mathcal{M}_G(F)\). In recursive calls the algorithm makes, some vertex in \(F\) may be marked as active. Initially, there are no active vertices and there is never more than one active vertex. The algorithm tries each of the following rules in turn and uses the first one that applies:

1. If \(G\) has multiple connected components \(G_1, \ldots, G_k\), then let \(F_i = F \cap V(G_i)\) for all \(1 \le i \le k\). Then recursively find an element \(F_i^* \in \mathcal{M}_{G_i}(F_i)\) for all \(1 \le i \le k\) and return \(F^* = F_1^* \cup \cdots \cup F_k^*\). If there is an active vertex \(t \in F\), then it remains active in the recursive call to compute \(F_i^*\) where \(t \in F_i\).

2. If \(F\) is not an independent set, then let \(T\) be a maximal subset of \(F\) such that \(G[T]\) is connected. Let \(G' = G|_{T \rightarrow v_T}\) and \(F' = F \setminus T \cup \{v_T\}\). If there is an active vertex \(t\) and \(t \in T\), then mark \(v_T\) as active. Now recursively compute an element \(F^* \in \mathcal{M}_{G'}(F')\) and return \(F^* \setminus \{v_T\} \cup T\).

3. If \(F = V\) or no vertex in \(G\) has degree greater than \(1\), then return \(V\).

4. If \(F = \emptyset\), then choose a vertex \(v\) of degree at least \(2\) and make two recursive calls to compute two sets \(F_1^* \in \mathcal{M}_G(F \cup \{v\})\) and \(F_2^* \in \mathcal{M}_{G - v}(F)\). Return the larger of \(F_1^*\) and \(F_2^*\).

5. If there is no active vertex in \(F\), then mark an arbitrary vertex \(t\) in \(F\) as active. Otherwise, let \(t\) be the current active vertex. Now apply one of the following three rules.

6. If there is a vertex \(v \in N(t)\) such that \(|\tilde N_t(v)| \le 1\), then make one recursive call to compute an element \(F^* \in \mathcal{M}_G(F \cup \{v\})\) and return it.

7. If there is a vertex \(v \in N(t)\) such that \(|\tilde N_t(v)| \ge 3\), then make two recursive calls to compute two sets \(F_1^* \in \mathcal{M}_G(F \cup \{v\})\) and \(F_2^* \in \mathcal{M}_{G - v}(F)\) and return the larger of \(F_1^*\) and \(F_2^*\).

8. If none of the previous two cases applies, then every vertex \(v \in N(t)\) satisfies \(|\tilde N_t(v)| = 2\). Choose an arbitrary such vertex \(v \in N(t)\) and let \(\tilde N_t(v) = \{w_1, w_2\}\). Make one recursive call to compute an element \(F_1^* \in \mathcal{M}_G(F \cup \{v\})\). If \(G[F \cup \{w_1, w_2\}]\) contains a cycle, then return \(F_1^*\). If \(G[F \cup \{w_1, w_2\}]\) is acyclic, then make an additional recursive call to compute an element \(F_2^* \in M_{G - v}(F \cup \{w_1, w_2\})\) and return the larger of \(F_1^*\) and \(F_2^*\).