CSCI3160 Regular 10：顶点覆盖与随机最大割
原件：题目（本地课件）；官方答案（本地课件） p.1–2。 定位：比较可证明的二倍近似、树上的精确 DP，以及缺少保证的最大度贪心。
Problem 1：二倍近似界能达到（答案 p.1）
在完全二部图 K(n,n) 中，课堂算法每次选一条剩余边，将两个端点都纳入覆盖，再删掉与它们相连的边。左右各剩 n−1 个顶点，仍形成完全二部图。如此选 n 次，最终选取全部 2n 个顶点。
最优值为 n：取整个左侧就能覆盖全部边，给出上界；另一方面有 n 条两两不共端点的匹配边，任何覆盖都必须为每条选至少一个不同顶点，给出下界 n。因此比值正好 2，不可能对这套算法普遍证明小于 2 的保证。
自取 n=3，图有 9 条边，算法返回 6 点，最优只取一侧 3 点。这里不是证明“所有顶点覆盖算法都不能更好”，只是这个算法的紧例。
Problem 2：树上的最优顶点覆盖（答案 p.1）
任选根，定义 Y(u) 为覆盖 u 子树所有边且必须选 u 的最少顶点数，N(u) 为必须不选 u 的最少数。对叶子，Y=1、N=0；对内部节点：
若选 u，边 u–v 已被覆盖，孩子可选可不选，取便宜者；若不选 u，边 u–v 只能靠选 v 覆盖，所以每个孩子强制选。子树彼此没有跨边，因此可以独立相加，不会遗漏覆盖约束。
后序遍历求值，根取 min(Y,N)。恢复时若父节点未选，当前必须选；若父节点已选，按当前两个状态的最小者决定，再递归孩子。不要只输出最小数量而遗漏题目要求的顶点集合。
自取三点路径 a–b–c，以 a 为根：c 的 (Y,N)=(1,0)；b 为 (1,1)；a 为 (2,1)，最优选 b，一个顶点覆盖两条边。每条父子边只参与常数次加法与恢复，时间和空间 O(n)。孤立单顶点最优为空集。
补充：树 DP 的两个值不是两棵不同子树。 Y(u)、N(u)都覆盖同一批“u以下的边”，区别只是u是否已选。父亲到u的边不属于u子树内部，所以N(u)可以为0而不代表那条父边已覆盖；父状态负责决定是否必须用u覆盖它。这样每条约束只在连接父子时处理一次。
自测：星形树中心r、三个叶子，两个根状态各是多少？
每个叶子(Y,N)=(1,0)。中心若选，Y(r)=1+0+0+0=1；中心不选，N(r)=1+1+1=3。最优取中心。若错误地让不选中心时孩子仍取min，就会得到0，相当于漏掉了所有三条中心—叶边。
Problem 3：最大度贪心可以超过二倍（答案 p.1–2）
官方构造：左侧 16 点 u₁,…,u₁₆；对 i=2,…,16，右侧建 floor(16/i) 个顶点，每个连一块互不重叠的 i 个连续左点。各层块只在本层不交，不同层可以重叠。右点总数为 34，左点 16 个当然构成一个覆盖，所以 OPT≤16。
考虑平局时优先选右侧的合法执行。从最高层 16 向下处理。在所有大于 i 的层已删之后，一个左点在每层 2,…,i 至多连一个右点，所以其剩余度至多 i−1；第 i 层尚未选的右点度仍为 i，因为只删除此前选过右点的边，并不删左顶点及其其他边。因此只要第 i 层还在，最大度点必来自该层，或在之前的过渡阶段可按同样最大度顺序选右点。
更直接按降层归纳：第 16 层右点度 16，左点至多 15；删完后第 15 层度 15，左点至多 14；依此下去，所有右点被选。每层内部其他右点边互不相关，选一个不降低同层其他右点的度。算法共选 34 点，故
只需证明 OPT≤16 就足以得到下界比值，不必额外证明 OPT恰好16；不要把容易给出的可行覆盖自动称为已证明最优。这里层内最大值严格压过左侧，不依赖左右平局。
Problem 4：随机二分给最大割一半保证（答案 p.2）
对每个顶点独立抛公平硬币，正面放 S，反面放另一侧。官方写成“对 S 中每点抛硬币”，但 S 初始为空，按字面不会执行；应当遍历 V。
对一条边 u–v，四种等概率配置中，恰有两种端点异侧，所以该边入割概率 1/2。令 Xₑ 是它是否入割的指示量，则
最后一步用任何割最多包含全图 m 条边。不同边的指示量不必独立，期望线性仍成立；真正使用独立的是一条边两个端点的硬币。
自取三角形：最优割为 2；随机割以 1/4 概率为 0（全在同侧），以 3/4 概率为 2，期望为 1.5=m/2，满足≥OPT/2=1。这也说明保证是期望，不是每次结果都好。赋值 O(n)，若需输出割边再扫描 O(m)，总 O(n+m)。
来源与证据
官方答案 p.1–2；最大度构造的 34 个右点及执行过程已程序核验。本文不据练习推断考试范围。