《Discrete Applied Mathematics》：XALP-completeness of parameterized problems on planar graphs
编辑推荐：
這篇論文研究參數化複雜度理論中的新興複雜度類別XNLP與XALP。作者們探討了多個經典的圖論問題（例如All-or-Nothing Flow, Target Set Selection等）在平面圖上，並以圖的outerplanarity、treewidth及pathwidth等結構性參數化後，其計算複雜度歸屬於XNLP或XALP完備類。研究證明了即使限制在平面圖結構上，這些問題依然保持高複雜度，填補了對這些參數化問題在不同圖類上複雜度分類的知識空缺，並進一步鞏固了XNLP/XALP類別作為多項圖論問題“自然歸屬地”的地位。
在經典計算複雜度理論中，我們可以根據問題的時間或空間需求對其進行分類，例如L ? NL ? P ? NP ? PSPACE = NPSPACE ? EXP這條著名的包含鍊。當我們將視線轉向參數化複雜度時，一個自然問題隨之產生：這些經典類別的參數化版本之間存在怎樣的關係？特別是，作為多項式時間類別P的參數化對應的固定參數可解性（FPT）類別，與非確定性對數空間類別NL的參數化對應XNLP類別之間有何關聯？這個問題最初由Elberfeld等人提出，他們定義了XNLP類別，並指出尋找具有“自然”參數化且對此類別完備的問題是真正的挑戰。過去十年間，這個挑戰取得了顯著進展，許多標準的圖論問題及其推廣被證明是XNLP完備的，使得XNLP成為一系列對所有t都W[t]-困難但不太可能屬於W[P]的問題的“自然歸宿”。
近年來，一個被稱為XALP的類別被引入，它是XNLP的“樹狀變體”。XALP包含那些可以由一個配備了輔助堆疊（stack）的非確定性圖靈機，在f(k)nO(1)時間和g(k) log n空間內解決的問題，其中n是輸入實例的大小，k是參數。直觀地說，XALP對應於以樹寬（treewidth）為參數時的可解性，而XNLP則對應於以路徑寬度（pathwidth）為參數時的可解性。許多以路徑寬度為參數是XNLP完備的問題，在以樹寬為參數時被證明是XALP完備的。
在此背景下，一個重要問題是：當我們將研究對象從一般圖限制到具有更強結構性質的圖類時，例如平面圖，這些問題的複雜度是否會顯著下降？在某些著名案例中，確實存在這種“複雜度下降”現象。例如，以解的大小為參數的支配集問題（Dominating Set），在一般圖上是W[2]-完備的，但在平面圖上則變成固定參數可解的，並且存在線性核。然而，對於那些以圖的結構性寬度（如樹寬）為參數時已經很困難的問題，當我們轉移到平面圖領域時，情況又會如何？是否會因為平面性的限制而變得容易？這正是Hans L. Bodlaender和Krisztina Szilágyi在這篇發表於《Discrete Applied Mathematics》的論文中旨在探索的核心問題。
研究者們特別關注了平面圖的一個關鍵參數——外平面性（outerplanarity）。一個平面圖被稱為k-外平面（k-outerplanar），如果其所有頂點可以劃分為k個“層”，移除最外層（即外平面）的頂點後，得到的圖是(k-1)-外平面的。外平面性是一個研究平面圖問題的天然參數，因為一個外平面性為k的圖，其樹寬至多為3k-1。因此，針對有界樹寬圖的演算法結果可以推廣到有界外平面性的平面圖。著名的Baker分層技術正是利用了這一性質，為許多平面圖上的問題設計出了近似方案。
本文的核心成果在於證明了，對於一系列已經被證明對於樹寬或路徑寬度參數是XALP或XNLP完備的圖論問題，當我們限制在平面圖上並以外平面性為參數時，其計算複雜度並未降低，它們仍然是XALP完備的。這表明，對於這類問題，平面性的限制並不足以帶來複雜度的“下降”，凸顯了XNLP和XALP這兩個複雜度類別的穩健性。
為了開展這項研究，作者們主要運用了參數化複雜度理論中的標準工具：歸約（reduction）。他們通過構造從已知的完備問題（如Binary CSP）到目標問題的參數化對數空間歸約（pl-reduction），來證明目標問題的硬度。這些歸約需要精心設計，以確保在保持問題等價的同時，將參數（例如路徑寬度或外平面性）的增長控制在一個可計算函數內，並且歸約過程本身只需f(k) + log n量級的空間。論文中詳細定義了用於構建具有有界路徑寬度或樹寬圖形的操作序列（如引入頂點、遺忘頂點、添加邊、交換頂點順序和連接操作），並利用這些操作來描述歸約中構造的圖實例。此外，作者們還需要嚴格證明所構造的圖實例確實具有有界的外平面性、樹寬或路徑寬度。
主要研究結果
本文的結果涵蓋了多個經典的圖論與組合優化問題，並將其在不同參數（外平面性、樹寬、路徑寬度）下的完備性結果總結於一張清晰的表格中。以下是部分核心發現的概述：
- •
Binary CSP、List Coloring與Precoloring Extension：論文在3.2節證明了二元約束滿足問題（Binary CSP）、列表著色（List Coloring）和預著色擴展（Precoloring Extension）在平面圖上，以外平面性為參數時是XALP完備的。這強化了先前已知的以樹寬為參數是XALP完備、以路徑寬度為參數是XNLP完備的結果。
- •
Scattered Set：論文在第4節專門討論了分散集問題。結果表明，該問題以路徑寬度為參數時是XNLP完備的，而以樹寬和外平面性為參數時是XALP完備的。這為該問題的參數化複雜度提供了更完整的圖譜。
- •
All-or-Nothing Flow：第5節重點研究了全有或全無流問題。這是一個經典網路流問題的變體，要求每條邊上的流量要麼是零，要麼是其最大容量（即“全有或全無”）。論文證明了即使在平面圖上並以外平面性為參數，該問題也是XALP完備的。
- •
由All-or-Nothing Flow導出的系列問題：論文第6節展示了如何從全有或全無流問題的硬度出發，通過歸約證明一系列其他問題的XALP完備性。這包括：
- •
Target Outdegree Orientation與Min./Max. Outdegree Orientation（目標出度定向與最小/最大出度定向）：在6.2節，通過巧妙的歸約，證明了這些圖定向問題在外平面性參數下是XALP完備的。
- •
Circulating Orientation（循環定向）：在6.3節證明了其XALP完備性。
- •
Capacitated (Red–Blue) Dominating Set與Capacitated Vertex Cover（容量限制的（紅-藍）支配集與容量限制的頂點覆蓋）：在6.4和6.5節，證明了這些帶容量的覆蓋與支配問題在外平面性參數下的XALP完備性。
- •
f-Dominating Set與k-Dominating Set：在6.6節，探討了更一般的支配集變體。
- •
Target Set Selection（目標集選擇）：在6.7節，證明了這個在社交網絡影響傳播中的經典模型，在平面圖上以外平面性為參數時也是XALP完備的。
結論與重要意義
本研究系統性地探討並確立了多個經典圖論問題在平面圖上，以外平面性、樹寬和路徑寬度為參數時的計算複雜度歸屬，絕大部分被證明是XNLP或XALP完備的。這項工作的主要意義體現在以下幾個方面：
首先，它填補了參數化複雜度理論中的一個知識空白。先前的研究已經建立了許多問題在一般圖上以樹寬或路徑寬度為參數時的XALP/XNLP完備性。本文將這些結果成功地“移植”到了平面圖這一具有重要理論和應用價值的圖類上，並以外平面性這一更精細的結構參數進行分析。結果表明，對於這一類問題，從一般圖轉向平面圖並未帶來複雜度的降低，這與某些問題（如以解大小為參數的支配集）的行為形成對比。
其次，這項研究進一步鞏固了XNLP和XALP作為一系列圖論問題“自然家園”的地位。這些問題通常對於W層級（W-hierarchy）中的所有類都是困難的，但又似乎不屬於W[P]類。XNLP和XALP為它們提供了精確的複雜度定位。本文的結果表明，即使施加了平面性這樣的強結構限制，這些問題的內在複雜度（在參數化意義下）依然頑固地存在於這些類別中。
最後，從技術角度看，論文中給出的從Binary CSP等完備問題到各個目標問題的歸約構造具有相當的技巧性和通用性，特別是對於如何在保持外平面性有界的同時編碼計算過程，提供了重要的範例。這些歸約技術本身是參數化複雜度理論中有價值的工具。
總之，Bodlaender和Szilágyi的這項工作深化了我們對平面圖上參數化問題計算複雜度的理解，揭示了XNLP和XALP完備性在相當廣泛的圖類和問題集合中的普遍性，為後續研究這類問題的精確演算法設計或更強的不可能性結果奠定了堅實的基礎。
