上海
t-一致超圖性的固定參數可解性
Fixed-Parameter Tractability of t-Uniform Hypergraphicality
https://arxiv.org/pdf/2606.08523
摘要
我們在度序列的壓縮表示下研究 t t-一致超圖性（ t t-uniform hypergraphicality）問題。輸入不再顯式列出所有頂點的度，而是由數對
我們的方法根據超邊相對于度類的類型對其進行分解，從而產生一個有界維度的譜（spectrum）表示。利用平衡鉸鏈翻轉（balancing hinge-flips），我們證明了每個可行的譜都可以轉換為規定度序列的一個實現。這導出了一個包含
個變量的整數規劃可行性公式。應用 Lenstra 定理得出了一個運行時間為
的 FPT 算法，其中 L L 表示壓縮輸入的編碼長度。
關鍵詞： 超圖性，度序列，一致超圖，固定參數可解性，整數規劃，壓縮表示
1 引言
度序列的刻畫是組合學的經典課題之一。在簡單圖的情形下，Erd?s–Gallai 定理 [1] 和 Havel–Hakimi 算法 [2, 3] 給出了可圖度序列的完整刻畫和高效識別算法。相比之下，一致超圖的類似問題則要困難得多。
這些易處理性結果都基于全局限制度的范圍。已有研究表明，在無限制設置下，較寬的度范圍已經會導致 NP 困難 [7]。這引發了一個問題：是否可以從較弱形式的正則性中恢復易處理性。
本文采取了這樣一種方法。我們不控制全局度范圍，而是利用由相等度的重數（multiplicities）產生的正則性。事實上，即使整體度序列高度非正則，每個度類本身也是正則的。
因此，即使度序列高度非正則，只要不同度的數量很少，它們仍然可能擁有實質性的內部結構。
這一觀察自然引出了以不同度的數量 k k 結合均勻性參數 t t 進行的參數化。我們的主要結果表明，這種壓縮的度表示產生了固定參數可解性（fixed-parameter tractability）。重要的是，這種可解性機制與之前已知的有界范圍區間（bounded-range regimes）有著根本的不同。特別是，我們的算法適用于那些整體度范圍可能遠大于 [7] 中確定的易處理區間的實例。當然，無限制的寬范圍實例仍然是 NP 難的 [5, 7]。然而，我們的結果表明，只要不同度的數量是有界的，僅憑大的度范圍并不排除可解性。
受此視角驅動，我們在度序列的壓縮表示下研究 t t-超圖性問題的參數化復雜度。我們不單獨列出所有度，而是將相等的度歸為一組。因此，輸入由數對
將此公式與經典的固定維度整數規劃算法相結合，得出了我們的主要定理： t t-超圖性在以為參數時是固定參數可解的。
我們的結果表明，盡管超圖性在一般情況下是 NP 難的，但當度結構被充分壓縮時，會顯現出實質性的算法可解性。
2 預備知識
我們 FPT 算法（注：原文誤寫為 FTP）的關鍵工具是鉸鏈翻轉（hinge-flip）操作。鉸鏈翻轉操作最早被用于近似積和式（permanent）[8]。幾篇最近的論文 [9–11] 在簡單圖上考慮了鉸鏈翻轉操作，文獻 [5, 7, 12] 也在 t t-一致超圖上對其進行了研究。
3 固定參數可解算法
首先，我們注意到 t t-一致超圖可以按如下方式進行無歧義的分解。設 V V 被劃分為度類
原文鏈接：https://arxiv.org/pdf/2606.08523
特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
