跳轉到

9.2 參數化複雜度與固定參數可解#

概念說明#

傳統複雜度只用「輸入長度 n」度量難度，但許多 NP-hard 問題的困難其實集中在某個小參數上。參數化複雜度（Parameterized Complexity）把輸入視為 (x, k)：x 是實例、k 是參數（解的大小、樹寬、違約數……）。若存在演算法時間 f(k)·n^O(1)——指數只炸在 k 上、對 n 仍是多項式——則稱問題是固定參數可解（FPT, Fixed-Parameter Tractable）。

這與偽多項式完全不同：頂點覆蓋是 FPT 的（f(k) = 1.2738^k），而目前的漢米爾頓迴路、集團問題則被認為不是。參數化複雜度還建立了自己的難度理論：W[1]-hardness，扮演類似 NP-hardness 的角色——若集團問題是 FPT，則 W[1] = FPT，學界普遍認為不成立。

兩大關鍵技術：

  1. 有界搜尋樹（Bounded Search Tree）：頂點覆蓋的 k 參數版——任取一條邊 (u, v)，覆蓋必含 u 或 v，分兩支遞迴、k 減一。搜尋樹深度 ≤ k、分支因子 2，共 O(2^k) 個節點，每節點 O(n + m)。
  2. 核心化（Kernelization）：多項式時間的預處理規則，把實例縮到大小只依賴 k 的「核心」。頂點覆蓋有 2k 頂點的核（Buss 氏核：刪除度數 0 的點；度數 > k 的點必須入解；若剩餘邊數 > k² 則 NO）。

FPT 的威力在實務上極大：許多真實世界的 NP-hard 實例，其解大小或結構參數遠小於 n，此時 FPT 演算法比通用近似/啟發式快得多，是生物資訊（樹寬參數）與網路分析（社群大小參數）的標配工具。

演算法步驟（頂點覆蓋 k-FPT）#

  1. 核心化：移除孤立點；把度數 > k 的頂點直接放入解 C 並 k ← k − 1；若 k < 0 回報 NO；若剩餘邊數 > k² 回報 NO。
  2. 有界搜尋樹：任取一條邊 (u, v)。
  3. 分支一：把 u 加入 C，從圖中刪除 u 及其鄰邊，k ← k − 1，遞迴。
  4. 分支二：把 v 加入 C，同理遞迴。
  5. 若所有邊被刪光（圖無邊），回報 C 為可行解；k 用盡仍剩邊則該分支失敗。

Python 程式碼範例#

def vertex_cover_fpt(edges, k):
    """頂點覆蓋：核心化 + 有界搜尋樹，O(1.27^k * poly(n))"""
    def solve(e, k, cover):
        if not e:                        # 無邊：成功
            return cover
        if k == 0:                       # 預算用盡
            return None
        # 核心化：度數 > k 的頂點必選
        from collections import Counter
        deg = Counter()
        for u, v in e:
            deg[u] += 1; deg[v] += 1
        hot = max(deg, key=deg.get)
        if deg[hot] > k:
            ne = [ed for ed in e if hot not in ed]
            return solve(ne, k - 1, cover | {hot})
        u, v = e[0]
        # 分支：選 u
        r = solve([ed for ed in e if u not in ed],
                  k - 1, cover | {u})
        if r:
            return r
        # 分支：選 v
        return solve([ed for ed in e if v not in ed],
                     k - 1, cover | {v})

    # Buss 核心：邊數 > k^2 則無解
    if len(edges) > k * k:
        return None
    return solve(edges, k, set())

def clique_brute(edges, k):
    """k-集團暴力：O(n^k)，用來對比 W[1]-hard 的代價"""
    from itertools import combinations
    es = set(frozenset(e) for e in edges)
    for S in combinations(edges and
            sorted({x for e in edges for x in e}), k):
        if all(frozenset((a, b)) in es
               for a, b in combinations(S, 2)):
            return S
    return None

edges = [(0,1),(1,2),(2,3),(3,4),(4,0),(0,2),(2,4)]
print(vertex_cover_fpt(edges, k=2))      # 大小 2 的覆蓋
print(vertex_cover_fpt(edges, k=3))
print(clique_brute(edges, 3))

複雜度分析#

  • 有界搜尋樹：樹高 ≤ k、分支因子 2 ⟹ O(2^k·(n + m))；加入「度數 > k 必選」後可分析為 O(1.2738^k·poly(n))（已知最好界之一）。
  • 核心：Buss 核大小 O(k²)；更強的 LP 核可到 2k 頂點。核心化是 FPT 演算法的「壓縮前處理」。
  • 對照組：集團問題的最佳已知演算法是 O(n^(0.79k)) 量級——k 出現在 n 的指數裡，k = 20、n = 1000 就不可行；這正是 W[1]-hard 的實務寫照。
  • 樹寬參數：許多問題在樹寬 tw 的圖上可用 O(c^tw·n) 動態規劃解決，真實路網、電路的 tw 往往很小。

練習#

  1. 實測 vertex_cover_fpt 在 k = 5~15 隨機圖上的執行時間，繪出時間隨 k 的成長曲線，驗證「指數只在 k 上」。
  2. 證明 Buss 核的正確性：(a) 度數 > k 的頂點必在任何大小 ≤ k 的覆蓋中；(b) 若每點度數 ≤ k 且仍有 > k² 條邊，則覆蓋大小必 > k。
  3. 實作「k-集團的有界搜尋樹」為什麼行不通（提示：分支後 k 的語意），說明集團與頂點覆蓋在參數化世界中的地位差異。