樹寬（treewidth）

許多在一般圖上 NP 困難的問題，在樹上卻變得容易，因為樹沒有糾纏的環——你可以從葉子往根掃，邊走邊合併子答案來解它（那就是樹形動態規劃）。真實的圖不是樹，但有些「幾乎」是樹——它們只有少數幾個小而局部的糾結。樹寬是一個單一的數字，恰好衡量一個圖離「是樹」有多遠：真正的樹是 0 或 1，近乎樹狀的圖很小，密集互連的圖很大。樹寬越小，樹式的攻法就越管用。

精確的定義使用「樹分解（tree decomposition）」：你用一組重疊的頂點「袋（bag）」覆蓋圖，把它們排成樹形，遵守兩條規則——圖的每條邊，其兩端點都同時出現在某個袋裡；而對每個頂點，含有它的所有袋形成一棵連通的子樹。一個分解的寬度是（其最大袋的大小）減 1，而樹寬是所有合法分解中最小的寬度。直覺上，每個袋是一個「分隔器」——一個小瓶頸，圖的其餘部分透過它溝通。因為袋很小（大小最多為樹寬 + 1），你就能在分解樹上跑動態規劃：把袋從葉子處理到根，在每個袋記住「那少數幾個頂點可能表現的每一種方式」的部分答案。這給出執行時間為 f(樹寬) * n 的演算法——所以即便對 NP 困難的性質，有界樹寬的圖也能在線性時間內解出。

樹寬之所以重要，是因為它是整個參數化複雜度中最強大的參數之一：把它限制住，一大本原本困難的問題（獨立集、支配集、著色、漢米頓路徑，以及由 Courcelle 定理、任何能用某種邏輯表達的性質）都變得可解。它捕捉了為何問題在串並聯圖、結構化程式碼的控制流圖、許多真實網路上是容易的。誠實的提醒：動態規劃的成本通常隨樹寬「指數」成長（每袋常約 2^樹寬 或更糟），所以這招只在樹寬小時才划算——而許多自然的圖（大網格、稠密圖、擴張圖）樹寬很大，毫無收穫；精確計算樹寬本身是 NP 困難的，不過有好的近似與針對它的 FPT 演算法。