一些有趣的困难问题快一点点的算法
1
给定一张一般图，求解其所有最小点覆盖；特别地，给定阈值 $k$，如果最小点覆盖大小超过 $k$，则直接报告 -1。
考虑直接爆搜，对于一个点，如果没选它，那么它的所有邻点都必须被选。（选一个点的时候，我们直接删掉这个点以及与之相邻的所有边。）我们自然希望每次删掉的点尽可能多，至少在递归的一侧如此。
因此我们每次讨论度数最大的点是否删去。特别地，如果所有点度数 $\le 2$，那么全图只剩下若干链和环，这是好处理的，特判掉。
因此，总递归轮数为 $T(n)=T(n-3)+T(n-1)$，解递推式得到最终复杂度为 $O(1.466^k \text{poly}(n,m))$，常数较小。
或许特判更多小度数情况可以得到更好的复杂度。