Parameterized algorithms

Parameterized algorithms

6.1.1 Parameterized algorithms

Set Cover

parameterized algorithms 6.1.1

$F$ is the family of sets over a universe $U$, $k$ is a positive integer. The task is to check whether there exists a subfamily $F' \subseteq F$ of size $k$ that covers $U$, which means that every element of $U$ belongs to some set of $F'$.

Theorem Given a Set Cover instance $(U,F, k)$, the minimum possible size of a subfamily $F'\subseteq F$ that covers $U$ can be found in time $2^{|U|}(|U|+|F|)^{O(1)}$.

Proof. We define $T[X,j]$ as the minimum possible size of a subset $F'$ $\subseteq$ $\lbrace$ $F_{1},F_{2},...,F_{j}\rbrace$ that covers $X$. If no such subset $F'$ exists, then $T[X,j]=+\infty$. We compute all $2^{|U|}(|F|+1)$ values $T[X,j]$.

• If $j=0$, $T[\emptyset,0]=0$ while $T[X,0]=+\infty$ for $X\neq 0$

• else, let $X \subseteq U$ and $0\lt{j}\leq{|F|}$, we have

  $$T[X,j]=min(T[X,j-1],1+T[X/F_j,j-1])$$

Steiner Tree

parameterized algorithms 6.1.2

Steiner Tree in OIwiki

Let $G$ be an undirected graph on $n$ vertices and $K \subseteq V(G)$ be a set of terminals, A Steiner tree for $K$ in $G$ is a connected subgraph $H$ of $G$ containing $K$, that is, $K \subseteq V(H)$.

The goal of this section is to design a dynamic-programming algorithm for Stenier tree with running time $3^{|K|}n^{O(1)}$, where $n=|V(G)|$.

Lemma For every $D \subseteq K$ of size at least $2$, and every $v \in V(G)\setminus K$, the following holds

where $T[D,v]$ means the minimum possible weight of a Steiner tree for $D \cup \lbrace v \rbrace$ in $G$, $u\in V(G)\setminus K$ and $\emptyset$ $\neq$ $D' \subsetneq D$

7.1 Treewidth

​ 该节是由树形DP的一个经典题目延伸而来。给你一个树，节点有权值，当你选择一个节点后，你获得该点的权值但其相邻节点不能被选，问能获得到的最大权值。

We shall call this problem Weighted Independent Set.

​ 由于树的结构特性，上述问题可以一遍 $dfs$ 跑掉，具体可以点上面的链接查看。

​ 那么，不是树的情况的该怎么解决呢？本节里介绍了网格图的解决方案，更具体一点，是"narrow grids"的子图。

Since the class of grids is not very broad, let us rather focus on subgraphs of grids.

下面给出一些规定，继续往下看的时候如果感到疑惑记得回来查查😵

• $G$：整个图，其为 $k\times N$ 网格图的子图，$k$ 很小（比如, $k=10$），$N$很大（比如, $N=10^{6}$）
• $(i_1, j_1)$ 和 $(i_2, j_2)$ 是相邻的当且仅当$\vert$ $i_1-i_2$ $\vert$ $+$ $\vert$ $j_1-j_2$ $\vert$ $=1$
• $X_j$ 为图 $G$ 的第 $j$ 列，即$X_j=V(G) \cap \lbrace (i,j):1\leq{i}\leq{k}\rbrace$
• $G_j=G[X_1\cup X_2 \cup ... \cup X_j]$
• 对于 $Y\subseteq X_j$, $c[j,Y]$ 为$G_j-Y$里$independent\,set$（即最上面描述的那种点集）可能的最大权值和。

从规定里也能看出来，我们就是要去求$c[j,Y]$了

• 对于$j=1$的情况，暴力枚举：

For every $Y \subseteq X_1$, we iterate through all possible subsets $S\subseteq X_1 \setminus Y$ , and for each of them we check whether it is an independent set.

要计算到所有的$Y$，总共的"check"次数：

上述式子要考虑选取 $Y$（枚举排列组合）和对每一个 $Y$ 的情况枚举找独立集。

• 对于$j\gt {1}$的情况，$dp$去解：

这里$w(S)=\sum_{v\in S}w(v)$，注意$S$是$independent\, set$，$N(S)$为$S$在上一列的里完整网格图对应的点集（其实就是邻居），与$X_{j-1}$取交就获得了所谓上一列里我们需要的$forbidden\, set$，插点原文

Similarly, for $j = 1$, we should iterate through all the possible ways a maximum weight independent set intersects column $X_j$. This intersection should be independent, of course, and moreover if we pick some $v\in X_j \setminus Y$ to the independent set, then this choice forbids choosing its neighbor in the previous column $X_{j-1}$ (providing this neighbor exists).

无论是哪种情况，计算量都在$3^k$· $k^{O(1)}$以内，最后时间复杂度$3^k$ · $k^{O(1)}$·$N$.

7.2 Treewidth

Path decomposition

图 $G$ 的一个路径分解是一个包 $bag$ 的序列$P=(X_1,X_2,...,X_r)$，满足：

$(P1)$ $\bigcup_{i=1}^{r}X_i=V(G)$，即 $G$ 的每个点都至少在一个包里.

$(P2)$ 若边$(u, v)$属于$G$，那么存在一个 bag 同时包含了 $u$ 和 $v$.

$(P3)$ 若 $u \in V(G)$，且$u\in X_i \cap X_k$，$i \leq k$，那么有$u\in X_j$，$i\leq {j}\leq{k}$.

• 路径分解的宽度 $width$： ${max}_{1\leq{i}\leq{r}}$ $\vert$ $X_i$ $\vert$ $-1.$

• 路径分解的路径宽度 $pathwidth$ ，即pw($G$): the minimum possible width of a path decomposition of $G$.

• $(A,B)$是一个$separation$ 当: $A \cup B=V(G)$，且在 $A \setminus B$ 和 $B\setminus A$ 之间没有边相连，这时$A\cap B$就是这个$separation$的$separator$(分隔符)，$\vert$ $A\cap B$ $\vert$称为$order$.

• 对于子集 $A \subseteq V(G)$，边界$border$: $\partial(A)$ 由 $A$ 中拥有在 $V(G)\setminus A$ 里的邻居的点组成.

the set of those vertices of $A$ that have a neighbor in $V(G)\setminus A$

Lemma 1 $(\bigcup_{i=1}^jX_i,\bigcup_{i=j+1}^rX_i)$ is a $separation$ of $G$ with $separator$ $X_j\cap X_{j+1}$

​ 证明可用反证法，可能会用到上面的$(P2)(P3)$.

一个路径分解是 $nice$ 的，如果遵循下面的条件：

• $X_1=X_r=\emptyset$.
• 对于每一个$i\in \lbrace 1,2,...,r-1\rbrace$，要么有一个点$v\notin X_i$且$X_{i+1}=X_i\cup \lbrace v\rbrace$（此时 $X_{i+1}$ 称为$introduce\,\,bag$, $X_{i+1}\,\,introduces\,\,v$），要么有一个点 $w\in X_i$ 且 $X_{i+1}=X_i \setminus \lbrace w\rbrace$（类似的，称为$forget\,\,bag$）.

Let us note that because of $(P3)$, every vertex of $G$ gets introduced and becomes forgotten exactly once in a nice path decomposition, and hence we have that $r$, the total number of bags, is exactly equal to $2\vertV(G)\vert+1$.

Lemma 2 如果 $G$ 存在宽度为 $p$ 的路径分解，那么其也存在一个 $nice$ 的宽度最大为 $p$ 的路径分解。另外，给定 $G$ 的宽度为 $p$ 的路径分解$P=(X_1,X_2,...,X_r)$，可在$O(p^2$·$max(r,\vert$ $V(G)\vert))$内求得 $nice$ 的宽度 $p$ 路径分解

Tree decompositions

树分解是路径分解的一个延伸

图 $G$ 的一个树分解$tree\,\,decomposition$是一个pair $\mathcal T=(T,\lbrace X_t\rbrace_{t\in V(T)})$，其中 $T$ 是一个树，树的每个节点 $t$ 都分配有子点集 $X_t\subseteq V(G)$，称为包 $bag$，遵循下面规则：

$(T1)$ $\bigcup_{t\in V(T)}X_t=V(G)$，即图 $G$ 的每个点都至少在一个包里.

$(T2)$ 对于图 $G$ 的每一条边 $(u,v)$，都存在树 $T$ 的一个节点 $t$ 满足 $X_t$ 同时包含了 $u$ 和 $v$ .

$(T3)$ 对于图 $G$ 的每一个点 $u$，集合 $T_u=\lbrace t\in V(T):u\in X_t\rbrace$，对应的包中包含 $u$ 的节点集合，就得到了 $T$ 的一个连通子树.

​ the set of nodes whose corresponding bags contain $u$, induces a connected subtree of T.

• 树分解的宽度$width$：$max_{t\in V(T)}\vertX_t\vert-1$
• 树分解的树宽度$treewidth$，即tw(G)：is the minimum possible width of a tree decomposition of $G$.

Lemma 3 设 $T$ 是图 $G$ 的一个树分解，$ab$ 是 $T$ 的一条边，那么森林 $T-ab$ 包含了两个相连的部分 $T_a(containing\,\,a)$，$T_b(containing\,\,b)$. 设 $A=\bigcup_{t\in V(T_a)}X_t$，$B=\bigcup_{t\in V(T_b)}X_t$，那么就有 $\partial(A),\partial(B)\subseteq X_a \cap X_b$，同样$(A,B)$就是图 $G$ 以 $X_a \cap X_b$为$separator$的一个$separation$.

一个树分解是 $nice$ 的，如果满足：

• $X_r=\emptyset,X_{\ell}=\emptyset$，其中 $r$ 是树 $T$ 的根，$\ell$ 是树的每一个叶子.
• 任意不是叶子节点的节点都是下面三种类型之一：
  • $\bold{Introduce\,\,node}$: 节点 $t$ 恰好只有一个孩子 $t'$ 且有 $X_t=X_{t'}\cup \lbrace v \rbrace$，$v\notin X_{t'}$此时我们说$v$ is $introduced$ at $t$.
  • $\bold{Forget\,\,node}$: 节点 $t$ 恰好只有一个孩子 $t'$ 且有 $X_t=X_{t'}\setminus \lbrace w \rbrace$，$w\in X_{t'}$，此时我们说$w$ is $forgotten$ at $t$
  • $\bold{Join\,\,node}$: 节点 $t$ 有两个孩子 $t_1,t_2$，且 $X_t=X_{t_1}=X_{t_2}$

Note also that, by property $(T3)$ of a tree decomposition, every vertex of $V(G)$ is forgotten only once, but may be introduced several times.

Lemma 4 如果图 $G$ 允许一个宽度至多为 $k$ 的树分解，那么它也能做到一个宽度至多为 $k$ 的 $nice$ 树分解. 另外，给定图 $G$ 的一个宽度为 $k$ 的树分解 $\mathcal T=(T,\lbrace X_t\rbrace_{t\in V(T)})$，可以在 $O(k^2$·$max(\vertV(T)\vert$,$\vertV(G)\vert))$内求得图 $G$ 的一个宽度为 $k$ 、拥有最多 $O(k\vertV(G)\vert)$个节点的 $nice$ 树分解

7.3.1 WeightedIndependentSet

设 $\mathcal T=(T,\lbrace X_t \rbrace_{t\in V(T)})$ 是 $n$ 节点图 $G$ 的一个树分解，宽度至多为 $k$，对于树上一节点 $t$，$t\neq r$，令 $V_t$为树 $T$ 以 $t$ 为根的子树里的包的并集，包括 $X_t$. 那么根据Lemma 7.3有 $\partial(V_t)\subseteq X_t$.

This exactly formalizes the intuition that the subgraph induced by $V_t$ can communicate with the rest of the graph only via bag $X_t$, which is of small size.

​ 将独立集问题与包 $X_t$ 联系起来：令图 $G$ 的两个独立集 $I_1,I_2$ 满足 $I_1\cap X_t=I_2\cap X_t$，我们把 $I_1,I_2$ 在 $V_t$ 里的点的权值加起来，并假设 w $(I_1\cap V_t)\gt$w$(I_2\cap V_t)$，那么就可以获得一个更好的方案 $I_2'$，通过把 $I_2$ 里的 $I_2 \cap V_t$ 替换成 $I_1\cap V_t$. 由前提 $I_1\cap X_t=I_2\cap X_t$ 以及结论 $\partial(V_t)\subseteq X_t$ 我们可以知道 $I_2'$ 依然是独立集，即我们从 w $(I_1\cap V_t)\gt$w$(I_2\cap V_t)$ 得到了 w$(I_2')$>w$(I_2)$

​ 现在问题有了些许转化. 对于一个 $S\subseteq X_t$，我们试图去找到一个权值最大的拓展集 $\hat{S} \supseteq S$，且有 $\hat{S} \subseteq V_t,\hat{S}\cap X_t=S$，$\hat{S}$ 还是独立集. 根据上一段讨论，我们可以知道$solution$ $I$在 $V_t$ 里的部分是可以安全替换成 $\hat{S}$ 的.

this replacement preserves independence and can only increase the weight. Observe that the number of subproblems is small: for every node $t$, we have only $2^{|X_t|}$ subproblems. Also, we do not need to remember $\hat{S}$ explicitly; remembering its weight will suffice.

​ 对于每个节点 $t$（这里原文是 $node$，原文有提 $node$ 指的是树分解的树上节点）和每个 $S\subseteq X_t$，有如下定义：

​ 如果没有这样的 $\hat{S}$ 存在（即 $S$ 不是独立集），就说 $c[t,S]=-\infty$，$c[r,{\emptyset}]$ 就是整个图 $G$ 的最大独立集（因为 $V_r=V(G)$ 且 $X_r=\emptyset$）.

​ 下面就来计算 $c[,]$

​ 下面都是基于 $nice$ 树分解的.

$\bold{Leaf\,\,node}$: $c[t,\emptyset]=0$

$\bold{Introduce\,\,node}$: $t$ 是一个introdece node，其孩子节点为 $t'$，$X_t=X_{t'}\cup\{v\}$，$S$ 是 $X_t$ 的任意子集. 若 $S$ 不是独立集，有 $c[t,S]=-\infty$；否则，有以下公式：

证明：

​ 先看 $v\notin S$的情况，此时可以判断 the families of $\hat{S}$ 在 $c[t,S]$ 和 $c[t',S]$ 上是一样的（因为有 $\hat{S}\cap X_t=S$ 限制，取不到 $v$ ），显然就有 $c[t,S]=c[t',S]$；

​ 对于 $v\in S$ 的情况，从两个角度去看：假设 $\hat{S}$ 是基于 $c[t,S]$ 最大权值定义上的一个集合，那么就有 $\hat{S}\setminus\{v\}$ 是基于 $c[t',S\setminus\{v\}]$ 上的一个集合，且有 $c[t',S\setminus\{v\}]\ge w(\hat{S}\setminus\{v\})=w(\hat{S})-w(v)=c[t,S]-w(v)$，最后得到：

​ 从另一个角度，设 $\hat{S'}$ 是基于 $c[t',S\setminus \{v\}]$ 最大权值定义的一个集合. 因为 $S$ 是独立的，$v$ 不会有邻居在 $S\setminus\{v\}=\hat{S'}\cap X_{t'}$ 里，再依据 Lemma 7.3 可以得到 $v$ 没有邻居在 $V_{t'}\setminus X_{t'}$（如果有邻居，那么 $v$ 作为边界的一部分是属于 $X_t\cap X_{t'}=X_{t'}$，但是 $X_{t'}$ 不含 $v$），$V_{t'}\setminus X_{t'}$ 是 $\hat{S'}\setminus X_{t'}$ 的超集. 所以 $v$ 没有邻居在 $\hat{S'}\setminus X_{t'}$ 和 $\hat{S'}\cap X_{t'}$ 里，即 $v$ 没有邻居在 $\hat{S'}$ 里， $\hat{S'}\cup\{v\}$ 是一个独立集. 由 $(\hat{S'}\cup\{v\})\cap X_t=S$，有：

​ 由$\le$和$\ge$就得出 $c[t,S]=c[t',S\setminus\{v\}]+w(v)$.

​ 多对照 $c[t,S]$ 的定义和 Lemma 7.3 来看要容易一点.

$\bold{Forget\,\,node}$: $t$ 是一个forget node，其孩子节点为 $t'$，$X_t=X_{t'}\setminus\{v\}$. $S$ 是 $X_t$ 的任意子集. 若 $S$ 不是独立集，有 $c[t,S]=-\infty$；否则有：

证明：

​ 设 $\hat{S}$ 是基于 $c[t,S]$ 最大权值定义上的一个集合. 若 $v\notin \hat{S}$，那么 $\hat{S}$ 就属于 $c[t',S]$ 所要考虑的集合中的一个（可从 $c[t,S]$ 的定义分析），于是就有 $c[t',S]\ge w(\hat{S})=c[t,S]$；若 $v\in \hat{S}$，那么 $\hat{S}$ 就属于 $c[t',S\cup\{v\}]$ 所要考虑的集合中的一个，于是就有 $c[t',S\cup\{v\}]\ge w(\hat{S})=c[t,S]$. 最后得到：

​ 注意到在基于 $c[t',S]$ 的定义下所要考虑到的集合 $\hat{S}$，同样也会在基于 $c[t,S]$ 和 $c[t',S\cup\{v\}]$ 的定义下被考虑，于是就有 $c[t,S]\ge c[t',S]$ 和 $c[t,S]\ge c[t'.S\cup\{v\}]$. 最后我们有：

​ 由$\le$和$\ge$就得出 $c[t,S]=max\{c[t',S],c[t',S\cup\{v\}]\}$.

$\bold{Join\,\,node}$: $t$ 是一个 join node，其两个孩子 $t_1,t_2$ 满足 $X_t=X_{t_1}=X_{t_2}$，$S$ 为 $X_t$ 的任意子集；和往常一样考虑 $S$ 是一个独立集，我们有：

证明：

​ 设 $\hat{S}$ 是基于 $c[t,S]$ 最大权值定义上的一个集合. 令 $\hat{S_1}=\hat{S}\cap V_{t_1}$，$\hat{S_2}=\hat{S}\cap V_{t_2}$. 我们可以看到 $\hat{S_1}$ 是独立的且 $\hat{S_1}\cap X_{t_1}=S$，因此 $\hat{S}$ 也是基于 $c[t_1,S]$ 定义下被考虑的集合，于是就有 $c[t_1,S]\ge w(\hat{S_1})$，同样也能得到 $c[t_2,S]\ge w(\hat{S_2})$. 由于 $\hat{S_1}\cap \hat{S_2}=S$，最后可以得到：

​ 另一方面，设 $\hat{S'_1}$ 是基于 $c[t_1,S]$ 的最大权值定义上的一个集合，$\hat{S'_2}$ 也是类似. 通过Lemma 7.3可以得到在 $V_{t_1}\setminus X_t$ 和 $V_{t_2}\setminus X_t$ 里的节点之间没有边相连（$separator$ 就是 $X_t$ 自己），这表明 $\hat{S'}:=\hat{S'_1}\cup\hat{S'_2}$ 是独立的（ $\hat{S'_1}$ 和 $\hat{S'_2}$ 是独立的，$V_{t_1}\setminus X_t$ 和 $V_{t_2}\setminus X_t$ 里的节点之间没有边相连，$\hat{S'_1}\subseteq V_{t_1}$，$\hat{S'_2}\subseteq V_{t_2}$，那显然两个并起来也是独立了）. 另外我们还有 $\hat{S'}\cap X_t=S$，也就是说 $\hat{S'}$ 是基于 $c[t,S]$ 所要考虑的集合之一，最后就有：

​ 由$\le$和$\ge$就得出 $c[t,S]=c[t_1,S]+c[t_2,S]-w(S)$.

现在稍做总结，算算时间

Recall that we are working on a tree decomposition of width at most $k$, which means that $\vertX_t\vert$ $\le k + 1$ for every node $t$. Thus at node $t$ we compute $2^{|X_t|} \le 2^{k+1}$ values of $c[t, S]$.

Wrapping up, for every node $t$ it takes time $2^k$· $k^{O(1)}$ to compute all the values $c[t, S]$. Since we can assume that the number of nodes of the given tree decompositions is $O(kn)$ (see Lemma 7.4), the total running time of the algorithm is $2^k$·$k^{O(1)}$·$n$.

Theorem 7.5 给定一个有 $n$ 个节点的带权图 $G$，同时给定它的宽度至多为 $k$ 的树分解，那么 $\bold{Weighted\,\,Independent\,\,Set}$问题可以在 $2^k$·$k^{O(1)}$·$n$ 时间内完成.

Corollary 7.6 给定一个有 $n$ 个节点的带权图 $G$，同时给定它的宽度至多为 $k$ 的树分解，那么 $\bold{Vertex\,\,Cover}$问题可以在 $2^k$·$k^{O(1)}$·$n$ 时间内完成.

​ 这些算法的时间复杂度上界会在第$14$章说明是被固定限制了的.

7.3.2 Dominating Set

本节我们试图去找图 $G$ 的最小支配集.

​ 首先对树分解进行些许变化，引入新节点 $introduce\,\,edge\,\,node$，之前的 $introduce\,\,node$ 现在叫 $introduce\,\,vertex\,\,node$.

$\bold{Introduce\,\,edge\,\,node}$: a node $t$, labeled with an edge $uv$ ∈ $E(G)$ such that $u, v$ ∈ $X_t$, and with exactly one child $t'$ such that $X_t = X_{t'}$. We say that edge $uv$ is introduced at $t$.

​ 在整个树分解里，我们要求 $E(G)$ 里的每一条边都恰好被引进（$introduced$）一次. 给定一个 $nice$ 树分解，可通过下面方法去转化成我们需要的. 由 $T(3)$ 可以得到，对于一个 $nice$ 树分解，其中的每一个节点 $v$ 都存在唯一一个 $highest\,\,node$ ，记作 $t(v)$，使得 $v\in X_{t(v)}$；另外有 $X_{t(v)}$ 的父节点是一个 $forget$ 了 $v$ 的 $forget\,\,node$. 对于 $E(G)$ 中的每一个边 $uv$ ，根据 $T(2)$ 可以得到，要么 $t(u)$ 是 $t(v)$ 的祖先，要么反过来. 所以我们可以在 $t(u)$ 和其父节点之间插入一个 $introduce\,\,uv$ 的节点.

Moreover, the obtained tree decomposition still has $O(kn)$ nodes, since a graph of treewidth at most $k$ has at most $kn$ edges

​ 对树分解里的每个节点 $t$ 都定义子图 $G_t$:

​ 对树分解的节点染色 $f:X_t\to \{0,\hat{0},1\}$，详细见下：

• $\bold{Black}$: 代表 $1$，所有的黑色节点都必须被包含在 $G_t$ 的部分解里.
• $\bold{White}$: 代表 $0$，所有的白色节点都不被包含在部分解里，且必须是被其支配的.
• $\bold{Grey}$: 代表 $\hat{0}$，所有的灰色节点都不被包含在部分解里，但不必被其支配.

需要强调的是，我们不会禁止灰色节点被支配，只是不关心它们会不会被支配.

​ $t$ 和 $f$ 的最小兼容集（$minimum\,\,compatible\,\,set$）$D\subseteq V_t$，满足：

• $D\cap X_t=f^{-1}(1)$，$f^{-1}(1)$ 即 $X_t$中的黑色点集合.
• $V_t\setminus f^{-1}(\hat{0})$ 中的每一个节点要么在 $D$ 里，要么是在 $G_t$ 里与 $D$ 中的一点相邻. 即 $D$ 支配 $V_t$ 在 $G_t$ 中的所有点，除了可能的 $X_t$ 里的灰色点.

​ 对于 $X_t$ 的每一个染色方案 $f$，我们用 $c[t,f]$ 来表示 $D$ 的大小. 如果对于 $t$ 和 $f$ 没有最小兼容集存在，就让 $c[t,f]=+\infty$. 注意，$G$ 的最小支配集大小就是 $c[r,\emptyset]$.

​ 对于子集 $X\subseteq V(G)$，考虑一个染色方案 $f:X_t\to \{0,\hat{0},1\}$. 对于节点 $v\in V(G)$ 和一个染色 $\alpha\in\{0,\hat{0},1\}$，我们按照下面去定义一个新的染色方案 $f_{v\to\alpha}:X\cup\{v\}\to\{0,\hat{0},1\}$：

（就是把染色方案 $f$ 里的 $v$ 的颜色换成 $\alpha$）

对于 $X$ 的一个染色方案 $f$，$Y\subseteq X$，用 $f\vert_Y$ 来表示 $f$ 对 $Y$ 的限制.

（就是 $f$ 对 $Y$ 染色的部分）

​ 下面来计算 $c$ 的值：

$\bold{Leaf\,\,node}$: 对于一个 $leaf\,\,node$ $t$，$X_t=\emptyset$，因此 $c[t,\emptyset]=0$

$\bold{Introduce\,\,vertex\,\,node}$: $t$ 是一个 $introduce\,\,node$，其孩子节点为 $t'$，$X_t=X_{t'}\cup\{v\}$ 且 $v\notin X_{t'}$.

​ 解释一下 $f(v)=0$ 的情况，由于该点是 $introduce\,\,node$，还没有没有引进边 $uv$ 到图 $G_t$ 里，因此此时的 $v$ 在图 $G_t$ 里是孤立的，又由于 $f(v)$ 是白色，你没法让 $D$ 同时满足兼容集的两个要求. 所以值为 $+\infty$.