《圖修正問題的參數化算法研究》是依託湖南師範大學，由劉運龍擔任項目負責人的面上項目。
基本介紹
- 中文名：圖修正問題的參數化算法研究
- 項目類別：面上項目
- 項目負責人：劉運龍
- 依託單位：湖南師範大學
項目摘要,結題摘要,
項目摘要
圖修正問題即對給定的圖作最少的修改使之具有某種特定的屬性。大量具體的圖修正問題是NP難的，參數計算是實際處理圖修正難解問題的一種新的有效手段。本項目運用參數計算理論及技術深入系統地研究難解的圖修正問題，其目標是對該類問題設計實際有效的固定參數可解算法。本項目將深入研究多種具體圖修正問題的參數計算複雜性，對固定參數可解問題設計有效的核心化規則和提出高效的固定參數可解算法，對固定參數難解問題從新的角度引入新的參數進而研究其新的結果。在此基礎上，本項目還將深入探究不同圖修正問題參數計算複雜性之間的內在聯繫，揭示同類圖修正問題的參數計算複雜性規律，提煉圖修正問題的通用性核心化方法，拓展圖修正問題的參數化算法設計技術。本項目的研究將為圖修正難解問題的成功套用創立理論基礎和新的實用方法。
結題摘要
在本基金的資助下，課題組對圖修正問題的參數化算法進行了深入系統的研究，並且取得了很大進展。研究內容既包括一系列不同具體問題的算法研究，也包含同類問題算法設計技術的規律探究；既包括以求解為目標的分支算法的研究，也包含以精簡實例為目標的核心化算法的研究；既注重經典圖修正問題的研究，也包含其他相關問題的研究。課題組將一系列不同的圖修正問題分為邊刪除問題、邊添加問題和邊編輯問題三種類型分別進行了深入研究。對於邊刪除問題，我們分別對3-Leaf Power邊刪除問題、Thereshold邊刪除問題和Co-trivially Perfect邊刪除問題進行了研究，並相應地提出了改進的固定參數可解算法。對於邊添加問題，我們主要對Proper Interval 邊添加問題和3-Leaf Power邊添加問題分別進行了研究，並相應地提出了時間複雜度明顯改進的固定參數可解算法。對於邊編輯問題，課題組著重對Cograph 邊編輯問題進行了研究。我們首次證明了該問題的計算複雜性是NP-完全的，解決了一個保持近二十年一直懸而未定的難題。同時我們對該問題首次提出了一個非平凡的固定參數可解算法。在核心化算法研究方面，課題組著重對平面圖上連通支配集問題進行了深入研究。我們提出了一種區域分解擴展技術，在此基礎上得到了該問題的一個大小不超過130k的核，肯定地回答了一個開放性問題。在同類問題算法設計技術的規律性探究方面，課題組著重對分支策略進行了深入研究。特別地，對目標圖類含有多個禁戒導出子圖的邊刪除和邊添加問題，我們首次提出了一種基於不同禁戒導出子圖之間內在結構關係的鏈式分支策略。這一策略是參數計算分支技術中繼基於鄰居擴展策略、目標圖類鬆弛策略之後的又一種新的分支策略，是參數計算技術的一個重要發展。課題組同時還運用圖修正問題參數化算法設計的一些相關技術對帶權的Matching, Packing問題和圖P2-packing 問題進行了研究，並得到了明顯改進的固定參數可解算法。項目的研究成果為一批NP難解的圖修正問題提供了實際有效的新處理途徑，對圖修正問題在實際工程中的套用起到很大的促進作用。同時，研究成果豐富和發展了參數計算理論及技術。
