Title: NP-Complete Problems and Special Bipartite Graphs

Speaker: Tian Liu (Peking University)

Time: 15:30-17:00, 8th April 2014

Venue: Lecture Room (334), 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Abstract:

NP完全問題是計算機科學理論的核心概念之一，對于理論研究和實際應用都有重要意義。大量的NP完全問題中有很多有實際應用但目前還缺乏多項式時間算法的計算問題，如最小頂點反饋集、最小聯通支配集、最小獨立支配集、哈密頓回路與通路等。這幾個重要的計算問題在一般二部圖上是NP完全的，在凸二部圖上有多項式時間算法。二部圖是重要的圖類，不僅可用來為實際問題建模，還可獲得在一般圖上難以獲得的結論，其內部包含豐富的結構，可定義各種特殊的二部圖，如凸二部圖、環凸二部圖、樹凸二部圖、弦二部圖等。近年來，報告人和合作者許可教授以及學生們把凸二部圖擴充到樹凸二部圖，并對相關的樹施加不同限制，分別得到星凸二部圖、三岔凸二部圖等，在這些特殊的二部圖上研究上述NP完全問題的算法和復雜度，確定對哪些圖類有多項式時間算法及對哪些圖類是NP完全的。下一步，將對這些特殊的圖類開展組合刻畫、隨機圖、近似算法、參數算法、指數算法等方面的研究，目的是理解這些特殊二部圖的數學結構對上述有重要應用的NP完全問題的算法設計的影響，為實際應用打下堅實的理論基礎。本報告將從NP完全問題的基礎知識講起，回顧各種對付NP完全性的方法和理論成果，重點介紹報告人和合作者過去幾年在特殊二部圖上取得的結果，并展望未來幾年可能的研究方向和研究問題。

Biography:

劉田，北京大學信息學院計算機系軟件研究所副教授，北京大學高可信軟件技術教育部重點實驗室成員，中國計算機學會理論計算機科學專委會委員，主要研究方向為算法分析與計算復雜度，近年來與北航許可教授合作，在隨機約束滿足問題的結構特征和算法分析、NP完全問題難解性的刻畫和處理等方面取得成果。曾在美國IEEE計算復雜度理論年會、歐洲Theoretical　Computer Science、Journal of Combinatorial Optimization 和 Minds and Machines等期刊上發表論文，在國際人工智能大會（IJCAI）的約束滿足、可滿足性和搜索（CSP/SAT/Search）分會上口頭報告論文，擔任過 TAMC、FAW、AAIM、COCOON 等國際會議的程序委員會委員或分會主席。