《參數複雜性在算法圖論上的一些套用》是依託上海交通大學，由陳翌佳擔任項目負責人的面上項目。
基本介紹
- 中文名：參數複雜性在算法圖論上的一些套用
- 項目類別：面上項目
- 項目負責人：陳翌佳
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
參數複雜性是算法複雜性理論的一個較新的分支。相對於經典理論，它主要處理二維計算問題，即問題的輸入中有一部分較小的參數。參數複雜性理論的核心是固定參數算法，它允許算法的運行時間超過多項式，只要非多項式時間的行為是被局限在小參數上的。由於許多NP難的算法圖論問題都是二維問題，即問題實例中包含較小的參數，因此固定參數算法為解決這些困難的計算問題提供了一個新的手段。近些年來，結構圖論的重大突破和邏輯方法的廣泛套用也使得固定參數算法和複雜性有了長足的發展。基於已有的工作我們的研究將集中於以下幾個方面：1.通過發展有向圖的結構理論和對應的邏輯理論，研究有向圖上模型驗證問題的參數複雜性和固定參數算法。2.子圖同構問題的複雜性，嘗試給出其完備的可解性刻畫。同時研究其各變種的複雜性。3.各種圖論問題的核心算法及其複雜性下界，以及其一般的邏輯刻畫。
結題摘要
參數複雜性是算法複雜性理論的一個較新的分支。相對於經典理論，它主要處理二維計算問題，即問題的輸入中有一部分較小的參數。參數複雜性理論的核心是固定參數算法，它允許算法的運行時間超過多項式，只要非多項式時間的行為是被局限在小參數上的。由於許多NP難的算法圖論問題都是二維問題，因此固定參數算法為解決這些困難的計算問題提供了一個新的手段。本項目主要研究參數算法在圖論問題上的套用及其相關的複雜性理論。經過三年的工作，我們在以下一些方面取得重要結果：1. 我們給出了k-邊導出子圖問題的參數算法，解決了蔡雷震於2004年提出的一個公開問題。我們的算法使用了許多深刻的數學工具，包括數論、組合和邏輯。2. 我們研究了團問題的參數可近似性。在著名的指數時間複雜性假設(ETH)下，我們證明了參數團問題不存在一類特定的參數近似算法。3. 作為相應的複雜性理論，我們發現了一個有限模型論、參數複雜性和證明複雜性間的一個令人吃驚的聯繫。
