图论中参数化复杂度与边支配集问题的研究进展

# 图论中参数化复杂度与边支配集问题的研究进展 ## 1. 参数化复杂度理论的扩展与推广 在参数化复杂度理论的框架下，一些结果可以更简洁、更一般地表述。FPTnu 类在 fpt - 归约下是封闭的，即若\((Q, κ) ≤_{fpt} (Q′, κ′)\)且\((Q′, κ′) ∈ FPTnu\)，则\((Q, κ) ∈ FPTnu\)。对于每个 W[1] - 完全问题\((Q, κ)\)，有\((Q, κ) ∈ FPTnu ⇔ W[1] ⊆ FPTnu\)。 同样，FPT⁺uni 类也在 fpt - 归约下封闭。对于每个 W[1] - 完全问题\((Q, κ)\)，有\((Q, κ) ∈ FPT⁺uni ⇔ W[1] ⊆ FPT⁺uni\)。由此可得推论：对于每个 W[1] - 完全问题\((Q, κ)\)，\((Q, κ) ∈ FPTnu\)意味着\((Q, κ) ∈ FPT⁺uni\)。 对于 t, d ∈ N，加权可满足性问题 p - WSat(Γt,d) 具有自归约性，所以有：若\(p - WSat(Γt,d) ∈ FPTnu\)，则\(p - WSat(Γt,d) ∈ FPT⁺uni\)。进而将上述推论扩展到 W - 层次结构的所有级别：对于每个 W[t] - 完全问题\((Q, κ)\)，\((Q, κ) ∈ FPTnu\)意味着\((Q, κ) ∈ FPT⁺uni\)。 ### 1.1 参数化支配集问题 考虑最突出的 W[2] - 完全问题——参数化支配集问题 p - DS： - **实例**：图\(G\)和\(k ∈ N\)。 - **参数**：\(k\)。 - **问题**：图\(G\)是否有大小为\(k\)的支配集？ 若存在算法\(A\)判定 DS，使得对于 DS 的所有正实例\((G, k)\)，有\(t_A(G, k) ≤ f(k) · ||G||^{o(k)}\)（其中\(f : N → N\)），则存在算法\(B\)判定 DS，使得对于 DS 的所有正实例\((G, k)\)，有\(t_B(G, k) ≤ 2^{o(|V (G)|)}\)。 ### 1.2 复杂度类的包含关系 已知\(DTIME(2^{o_{eff}(n)}) ⊆ DTIME(2^{o(n)}) ⊆ \bigcup_{ε>0}DTIME (2^{ε·n})\)，目前尚不清楚第一个包含关系是否严格，但证明了第二个包含关系是严格的。 问题 Exp - Halt： - **实例**：图灵机\(M\)，\(x ∈ Σ^*\)，以及\(1^m\)（\(m ∈ N\)）。 - **问题**：图灵机\(M\)是否在时间\(2^{⌊m/(|M| + |x|)⌋}\)内接受\(x\)？ 该问题属于\(\bigcup_{ε>0} DTIME (2^{ε·n}) \setminus DTIME(2^{o(n)})\)。 ## 2. 边支配集问题的研究 ### 2.1 边支配集问题概述 图\(G = (V, E)\)中的边支配集是边的子集\(S\)，使得\(E - S\)中的每条边都与\(S\)中的至少一条边相邻。寻找最小规模的边支配集是一个基本且重要的 NP - 难问题，在近似算法和参数化复杂度领域都有广泛研究。 ### 2.2 已有算法结果 - **近似算法**： - 无权图中有简单的 2 - 近似算法，任意最大匹配是边支配集，其大小至多是最小边支配集的两倍。 - 加权边支配集问题，Carr 等人证明了\((2 + \frac{1}{10})\)