参数复杂性

设判定性问题为语言 , 对于一个实例 , 我们说 是 的一个 YES-instance, 如果 , 否则称 是 的一个 NO-instance.

一个参数化问题是 , 称实例 由 参数化.

FPT

如果可以在 的时间内判定 是 的 YES-instance 还是 NO-instance, 就称 是固定参数可计算的 (Fix Parameter Tractable, FPT), 相关的算法称为 FPT 算法, 其中 是一个仅与 有关的可计算函数. 类是所有 FPT 的参数化问题的集合. 定义 类是所有可以在 时间内判定的参数化问题的集合.

如果要表明参数化问题的"固定参数不可计算"以及其程度, 在 和 之间还要有其他的语言类存在, 事实上有如下式子存在： 其中最重要的是 类. 通过 -hard 的问题向 的参数化规约可以来表明 .

参数化问题 向参数化问题 的参数化规约是一个函数 , 满足 , 其中 是 的实例且 是 的实例, 且满足 是 的 YES-instance 是 的YES-instance, 是在 时间内可计算的, 其中 是某个可计算函数, 以及 , 是某个可计算函数.

另一种表明参数化问题 的难解性 () 的方式是对于某个常数 , 是 -hard 的, 此时称 是 para-NP-hard.

核

对于参数化问题 , 当且仅当存在可计算函数 , 多项式 , 不确定型 RAM 程序

• 至多 步
• 至多使用 个寄存器
• ... > 看不懂.

松弛团的一些结果

The Clique-Core Gap is Too Small

-DC: -DEFECTIVE CLIQUE

-P: -PLEX

-C: -CLUB

在标准参数复杂性的假设下, 参数 不能用来给 -DC, -P, -C 这些问题设计 FPT 算法, 其中 是所谓的 Clique-Core Gap, 是 degeneracy, 是最大松弛团的大小, 事实上, 有下面更具体的结果:

• DENSE SUBGRPAH 关于参数 是 -hard 的.
• -DEFECTIVE CLIQUE 关于参数 是 -complete 的; 关于参数 和 都是 para-NP-hard 的.
• -PLEX 关于参数 是 -hard 的.
• -CLUB 关于参数 是 para-NP-hard 的.

首先对任意图 都有 .

1. 是 -dense subgraph 当且仅当 是 -defective clique.

2. DENSE SUBGRAPH 关于参数 (解的大小), , 都是 -hard 的, 即使有下面三个条件:

   • 至多是
   • 每个解都是连通的
   • .

3. -DC 关于参数 是 -hard 的, 即使满足下面三个条件:

   • 至多是
   • 每个解都是连通的

4. -DC 在 的图上是 NP-hard 的.

   可以注意到 的图是森林.

5. -DC 关于参数 是 contained in 的.

Intractability of the Clique-Core Gap for -DC, -P, and -C

-C 关于参数 是 para-NP-hard 的, -P 和 -DC 关于参数 都是 -hard 的.

在后面会考察更大的 gap parameter , 用来给松弛团设计 FPT 算法.

Studying a Larger Gap

首先是结论:

• -C 关于参数 是 FPT 的
• -P 和 -DC 关于参数 是 FPT 的.
• 对于 -P, 通过研究它的对偶问题 BOUNDED-DEGREE VERTEX DELETION 可以判断关于参数 存在问题核
• -DC 不存在关于参数 的问题核

PARTIAL VERTRX COVER (PVC): 实例 是一个 YES-instance 当且仅当 包含一个 -partial vertex cover , 等价表述还有:

• 覆盖了至少 条边
• 至多有 条边没有被 给覆盖

所以 存在一个大小为 的 -dc 当且仅当 存在一个大小为 的 -pvc, 所以:

• 是 -DC 的 YES-instance 是 PVC 的 YES-instance.
• 上面这个推论表明了 PVC 关于参数 与 -DC 关于参数 是互为对偶问题.
• PVC 关于参数 具有大小为 的 buss-like kernel (视 为常数), 也具有大小为 的 kernel (视 为常数)

已有的结果 (4.1) 先跳过.

Basic FPT-Results for PVC

PVC 已有的结果是:

• 有一个 的算法
• 有一个 的算法 (本部分内容), 通过在点集上做分支

Observation 4.2 若 满足 , 则每一个 的 -pvc 都包含 中至少一条边的一个端点.

通过这一推论, 很容易得到一个 的算法判定大小至多为 的 -pvc 是否存在.

PCV 的两个 kernel (与参数 相关)

kernel

Reduction Rule 4.2.1 实例 , 对于度数为 0 的点, 直接删掉. (Safe and 线性时间穷尽应用), 也就是返回

Reduction Rule 4.2.2 如果存在 满足 , 那么就返回 . 这是因为如果有点的度数至少为 , 那么每一个大小至多为 的 -pvc 都包含 . (仍然是 safe 且在线性时间穷尽应用, 证明先掠过)

设实例 无法应用上述两个 reduction, 若 , 则 是一个平凡的 NO-instance. 这就表明了PVC 具有一个大小至多为 的核, 且该核可以在线性时间内计算出.

Linear Kernel

PVC 具有一个严格小于 的核, 该核可以在 时间内计算出.

定义 (\uplus) 表示 .

图 的 Minimum Vertex Cover 的整数规划如下形式:

将其松弛为线性规划:

定理1 线性规划 存在一个最优解 .

定理2 对于 , 将其取值为 对应的点集分别记作 , 则

• .
• 存在最小点覆盖 , 且 .

定理3 VC 有一个大小至多为 的核, 可以在 的时间内计算出来.

Expansion Lemma