肖鳴宇

肖鳴宇 電子科技大學計算機科學與工程學院教授、博士生導師，協同自主計算實驗室。多個基本NP難問題的最佳參數和精確算法的保持者，在圖的多分割問題上解決了多個公開難題，在參數算法上是國內最為活躍的科研工作者之一。

"在香港中文大學師從圖靈獎獲得者姚期智先生，從事理論計算機方向博士學習三年獲得博士學位。清華大學、京都大學、巴黎第九大學等高校訪問學者。科研方向包括：算法與計算複雜度分析，圖論及圖算法，智慧型算法，最最佳化，參數算法等。

和日本、加拿大、美國、法國、以色列、香港等地許多計算機專家建立了學術合作關係。目前是多個基本NP難問題的最佳參數和精確算法的保持者，在精確算法和參數算法上是國內最為活躍的科研工作者之一。主持國家自然科學基金4項。近五年第一作者發表高水平學術論文50餘篇。

基本介紹

• 中文名：肖鳴宇
• 職業：教授、博導
• 性別：男
• 學歷：博士
• 工作：電子科技大學協同自主計算實驗室

簡介

姓名：肖鳴宇	性別：男	學校：電子科技大學
系別：軟體系	職稱：教授、博士生導師	畢業院校：中南大學
學歷：博士	實驗室：協同自主計算實驗室	電話：
研究方向：算法設計與分析，計算複雜度分析，近似算法，參數算法，圖論及圖算法，計算機輔助幾何設計等

教育背景

2008年，博士，計算機，香港中文大學（The Chinese University of Hong Kong）

2009年6月，2010年7月，訪問學者，京都大學（Kyoto University）

2011年9-11月，訪問學者，巴黎九大（University Paris Dauphine）

科研情況

肖鳴宇在香港中文大學師從圖靈獎獲得者姚期智先生，從事理論計算機方向學習三年獲得博士學位。和日本、加拿大、美國、法國、以色列、香港等地許多計算機專家建立了學術合作關係。目前是多個基本NP難問題的最佳參數和精確算法的保持者，在圖多分割問題上解決了多個公開難題，在參數算法上是國內最為活躍的科研工作者之一。主持國家自然科學基金4項。近四年第一作者發表高水平學術論文近40篇，其中8篇屬於CCF認定的B類及以上刊物，7篇屬於CCF認定C類刊物。

目前主要從事參數算法和精確算法方向研究。在《Algorithmica》等國際頂級算法雜誌和會議上第一作者發表論文20餘篇（具體列表參看DBLP或谷歌主頁）。主持國家自然科學基金青年項目《圖上若干基本NP難問題的算法研究》、國際交流與合作項目《獨立集、點覆蓋及其相關問題的參數算法和精確算法研究》等三項國家級項目。

肖鳴宇老師一直從事算法方向研究工作，他的研究成果之一：為獨立集問題設計了當前最快的精確算法，是近30年來第一次真正打破Robson於1986年給出的運行時間上界，並在亞太地區算法與計算領域最好的會議ISAAC 2013上獲最佳論文提名；2013年獲國家自然科學基金面上資助，發表第一作者論文10篇（其中SCI 5篇，CCF B類4篇），獲校學術新人獎，是計算機學科第一位獲得該資助的青年老師。肖鳴宇老師承擔的課程被評定優秀，同時他還擔任了數理基科班和學院珠峰計畫導師，指導本科生髮表一級學報論文1篇。

主持項目

1.基於“測量治之”方法的算法設計研究，國家自然科學基金，主持

2. 圖上若干基本NP難問題的算法研究，國家自然科學基金，主持

3. 獨立集、點覆蓋及其相關問題的精確算法和參數算法研究，國家自然科學基金，主持

4. Online Optimization for Dynamic Power Management, 國家自然科學基金，中方主持

5. 參數算法理論及其套用研究，中央高校基金，主持

6. 圖分割問題的參數算法研究，電子科技大學校青年科學基金，主持

招生方向

博士招生專業	碩士招生專業
081202計算機軟體與理論	081202計算機軟體與理論
04方向：計算生物學; 06方向：計算智慧型; 08方向：複雜網路分析	02方向：資料庫與數據挖掘; 05方向：計算理論與技術; 10方向：計算生物學

人物介紹

肖鳴宇教授又攻下了一個基礎性計算難題——改進獨立集問題的精確算法，打破了國際著名算法理論大師羅賓遜在1986年創下的紀錄。這個難題已經讓算法理論界頭疼近30年，肖鳴宇從博士畢業到紮根電子科大，一直堅持不懈地潛心研究了整整五年。

這是理論計算領域套用十分廣泛且最為基礎的難計算問題之一。近30年來，圍繞這個獨立集問題精確算法的研究論文不下20篇，但都沒有超越羅賓遜的研究——肖鳴宇卻使“羅賓遜”又往前走了一大步。

2013年底，當肖鳴宇應邀參加在香港舉行的第25屆國際算法與計算大會（ISAAC）時，此文作為重要研究成果，入選大會“最佳論文”候選論文，並受到業內學者的高度關注。

肖鳴宇沒有拿過多少“大項目”，而是一門心思深入到“收效周期很長”的基礎計算理論研究，並樂此不疲。雖然這項研究的更大價值或許要在5年之後才能充分顯現，但他認為，作為基礎與前沿理論的研究者，這已足以讓他感到快慰了。

發現天賦：算法奇才讓人眼前一亮

肖鳴宇本科時就讀於中南大學數學系，做的最多且最有樂趣的事情，就是參加數學建模競賽。當時，他在同學們眼裡是當之無愧的數學建模高手，曾在美國數學建模競賽中連續兩次斬獲一等獎。

從數學到計算機，只有一步之遙，數學建模或算法研究就是這樣一種數學與計算機交叉融合的典型。很多學科都會遇到數學建模或算法研究，肖鳴宇的所有努力可以劃分為兩個步驟：第一是對問題進行最佳化建模，第二是對最佳化模型進行算法設計來求解。

他對算法很感興趣，但一直沒有系統學習過，而是隨著“求解”的需要，東一榔頭、西一棒槌，現學現用。2002年和2005年他在中南大學分別獲得數學學士和碩士學位，並獲得湖南省優秀畢業論文和湖南省優秀畢業生稱號——但這些與算法沒有多少關聯，直到上博士當助教時，為了給香港中文大學的本科生講課，他才系統接觸了算法課程。

以此為標誌，他徹底從數學轉入算法研究，再也沒有變更過方向。算法是計算機領域內十分基礎的理論，他說，“計算機是死的，你得用算法告訴它做什麼、怎么做，因此，計算機的智慧就取決於你的思想！”

其實，肖鳴宇並非從一開始就選擇算法為畢生事業，當他在數學的海洋遨遊時，甚至從未想到自己以後會和算法結下如此深厚的情誼。促使他發生轉變的是一個“中南傳奇”：二十年前，有一位數學天才轉行做了算法研究，並成為算法領域的巨擘。

這個人就是美籍華人學者、當時中南大學的“長江學者”陳建二教授。陳建二多年來主要從事計算機理論及套用技術的研究，在計算複雜性理論、圖理論與算法、計算最佳化理論、網路理論等領域內進行了深入系統的研究，取得了一批具有世界領先水平的理論成果。

一位數學奇才何以轉入算法領域？帶著這個困惑和對自己未來方向的思索，肖鳴宇鼓起勇氣求教陳建二教授。他聽完肖鳴宇的疑問之後，並沒有直接回答，而是隨口出了幾個算法難題；肖鳴宇略加思索，即給出了自己的答案。這讓陳建二頓時對眼前的這個小伙子刮目相看，他認為，肖鳴宇的解決思路與算法領域近十年來的前沿思想十分吻合，甚至有一些思路獨闢蹊徑，有過之而無不及。

於是，陳建二果斷建議肖鳴宇向算法研究轉型，“雖然做數學研究也可以做出傑出的成就，但如果不做算法研究就太可惜了！”在肖鳴宇碩士畢業時，陳建二欣然為他寫了推薦信，薦他到香港中文大學蔡雷震教授麾下學習。不料，蔡雷震憐愛肖鳴宇之才，立即鼎力推薦給了學界泰斗——姚期智院士。

姚期智是世界著名計算機學家、美國科學院院士、美國科學與藝術學院院士、中國科學院外籍院士，2000年“圖靈獎”得主。2004年9月，他辭去美國普林斯頓大學的終身教職，正式加盟清華大學高等研究中心，成為清華的全職教授，並於2005年成為香港中文大學的博文講座教授。

2005年，肖鳴宇在蔡雷震的推薦下，在香港中文大學見到了他的博士生導師姚期智。3年後，他就獲得了哲學博士學位，成為姚期智在香港中文大學培養出的第一位博士，也是2008年香港中文大學計算機系僅有的兩位三年畢業的博士之一。

得遇名師：在算法領域落地生根

第一次與導師見面時，肖鳴宇並沒有立即引起姚期智的特別注意。與如此大師級的學者面對面交談，讓他感覺很緊張。見面之前他已做了充分準備，“以為會問到很高層次的問題，所以準備時和見面回答時，都努力往哲學方面靠，結果適得其反，給姚老師留下了一種誇誇其談的形象！”姚期智的考察很實在、很直接，只說了一句“你把Ramsey定理給我證明一遍”。這次見面，讓肖鳴宇學到了很多，也對導師的求實和嚴謹精神由衷地敬佩。

半年後，姚期智給了第二次見面的機會。經過半年的調整和摸索，肖鳴宇把自己半年來的思考和想法實實在在地做了匯報，讓姚期智十分滿意，他認為肖鳴宇的進步超乎想像。肖鳴宇也從此獲得了更多的見面機會，並有機會聆聽更多的指導。

經過幾次見面交流，姚期智對肖鳴宇在算法方面的靈感和問題意識非常看好。在第三次見面時，他對肖鳴宇的研究方向進行了充分的評估，建議他在“圖算法”和“NP難問題”領域開疆擴土。當時，姚期智主攻“量子計算”，肖鳴宇也曾考慮這個方向，但姚期智卻認為肖鳴宇在“圖算法”和“NP難問題”方面將會取得更大的成就。

此後，肖鳴宇不負所望，在算法領域非常前沿的“圖多最佳化分割問題”研究中取得巨大進展。當時“圖多最佳化分割問題”研究中有多個懸而未決的“公認難題”，肖鳴宇沉浸其中，高度專注，在一周內破解了其中一個難題。當他把最終研究結果報告給“副導師”蔡雷震後，蔡雷震十分重視，但沒有立即給出答覆，而是報告給姚期智。

事後才知道，兩位導師都在獨立地對該研究進行科學嚴謹的驗證。一個月後，肖鳴宇再次見到姚期智，驚訝地發現辦公桌上有100多頁的手寫演算稿紙，對自己研究中的每個步驟都給予了推導和證明——結論是正確的！

以此為開端，肖鳴宇在博士期間獲得了大豐收，不僅成為國內算法理論方向最為活躍的科研者之一，也是多個基本NP難問題最佳參數算法和精確算法的保持者。姚期智、王魯生等教授曾這樣評價肖鳴宇：“他研究的這些問題都十分重要，其中大部分問題被國際頂尖學者廣泛研究。我們相信，他將在這些領域取得更顯著的進展！”

在參數算法基本問題的“Benchmark列表”中，收錄著肖鳴宇的兩項研究結果，是僅有的兩項來自中國的研究結果。他提出的複雜參數方法簡化並改進了很多基本參數算法，被國際同行評價為“有趣並有前景”。

潛心研究：在基礎與前沿領域馳騁

一個又一個公認難題的解決，讓肖鳴宇在學術界聲名鵲起，姚期智也大力推薦這位得意弟子參加相關的國內外高級別學術會議，讓肖鳴宇大開了眼界，同時也在國際學術界獲得了聲譽。

博士畢業後，日本京都大學每年都邀請肖鳴宇赴日本訪問交流，並且每年都派人來中國學習。肖鳴宇加盟電子科大後，京都大學的學者每年都來清水河畔拜訪他。京都大學為肖鳴宇專門留出寬敞的辦公室，並邀請他“任何時候都可以來京都大學辦公”。

“成名”之後，肖鳴宇本來有更多的機會獲取更多的資源做“套用研究”，但是，他一直不肯邁出這一步。導師姚期智也十分希望肖鳴宇堅持做“理論研究”而非“套用研究”，他曾對肖鳴宇說：“我相信你有能力在套用研究中解決一些重大問題，但如果在基礎理論研究中取得突破，將會對學術界和產業界產生更大、更為深遠的影響。”

因此，從博士畢業到現在，肖鳴宇都把自己定位在基礎計算理論研究。“解決大家都解決不了的難題或不願意投身研究的基礎問題，也是一種成功的學術路徑”，他說，“我就是那種專注地解決難題的人！”

肖鳴宇說到做到，從2008年加盟電子科大，他一直致力於基礎研究，沒有接過任何“橫向項目”。“圖多最佳化分割”理論在計算機、積體電路的生產中具有十分廣泛而重要的套用價值，華為等公司多次邀請肖鳴宇做“橫向項目”，助力解決相關技術難題，但肖鳴宇都決然地拒絕了。2009年，他只做成了一件事情，就是成功申請了一項國家自然科學基金——《圖上若干基本NP難問題的算法研究》。

“從理論研究到產業套用有一定的距離，我的精力有限，沒有更多的時間去解決套用領域的問題，所以只能集中力量深入研究基礎理論！”肖鳴宇說，“我相信，只要基礎理論獲得突破，從理論到套用的實現環節肯定會有其他優秀的人才努力完成！”

然而，純粹沉浸在基礎理論研究，對心態和定力是一種極大的考驗。經濟收入、量化考評、職稱晉升等，既是對基礎理論研究者的壓力，也是對他們的極大誘惑。但是，肖鳴宇對此淡然處之，一直選擇在基礎理論領域堅守！

由於“圖算法”和“NP難問題”等領域曲高和寡，國際上相關的學術期刊影響因子較小，論文引用數量不大。而國內的相關研究因起步較晚，氣氛並未廣泛形成，目前大陸僅有清華、北大、上海交大、中南大學等少數幾所高校致力於此。但是，肖鳴宇並不在乎“熱門”還是“冷門”，而是持之以恆，並希望把我國西南地區的這個學科方向撐起來！

近幾年來，肖鳴宇每年都參加許多次各種計算理論方向的重要國際會議，從最開始的“默默無聞”逐步發展為今天的“備受矚目”，肖鳴宇也將“電子科大”推介到了重要的國際學術會議，使其成為國際國內同行最為熟知的內地高校之一。“做大做強計算機基礎與前沿理論，這是我的興趣，也是我的責任！”肖鳴宇說，“做基礎理論研究需要靜心靜氣，在這條路上，我將一如既往、風雨兼程！”

發表論文

Mingyu Xiao:A New Linear Kernel for Undirected Planar Feedback Vertex Set: Smaller and Simpler.AAIM 2014: 288-298

Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Dominating Induced Matching Based on Graph Partition.CoRR abs/1408.6196(2014)

Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3.IEICE Transactions 96-D(3): 408-418 (2013)

Mingyu Xiao,Hiroshi Nagamochi:Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs.Theor. Comput. Sci. 469: 92-104 (2013)

Mingyu Xiao,Takuro Fukunaga,Hiroshi Nagamochi:FPTASs for trimming weighted trees.Theor. Comput. Sci. 469: 105-118 (2013)

Mingyu Xiao,Hiroshi Nagamochi:Parameterized edge dominating set in graphs with degree bounded by 3.Theor. Comput. Sci. 508: 2-15 (2013)

Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New parameterized algorithms for the edge dominating set problem.Theor. Comput. Sci. 511: 147-158 (2013)

Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs.FAW-AAIM 2013: 72-83

Mingyu Xiao,Hiroshi Nagamochi:An Improved Exact Algorithm for Undirected Feedback Vertex Set.COCOA 2013: 153-164

Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Maximum Independent Set.ISAAC 2013: 328-338

Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.TAMC 2013: 96-107

Mingyu Xiao,Hiroshi Nagamochi:Exact Algorithms for Maximum Independent Set.CoRR abs/1312.6260(2013)

Mingyu Xiao,Hiroshi Nagamochi:An FPT algorithm for edge subset feedback edge set.Inf. Process. Lett. 112(1-2): 5-9 (2012)

Mingyu Xiao,Hiroshi Nagamochi:An Improved Exact Algorithm for TSP in Degree-4 Graphs.COCOON 2012: 74-85

Bruno Escoffier,Jérôme Monnot,Vangelis Th. Paschos,Mingyu Xiao:New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.IPEC 2012: 25-36

Mingyu Xiao,Jiong Guo:A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments.MFCS 2012: 825-835

Mingyu Xiao,Hiroshi Nagamochi:A Refined Exact Algorithm for Edge Dominating Set.TAMC 2012: 360-372

Mingyu Xiao,Hiroshi Nagamochi:An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure.CoRR abs/1212.6831(2012)

Mingyu Xiao,Leizhen Cai,Andrew Chi-Chih Yao:Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimumk-Way Cut Problem.Algorithmica 59(4): 510-520 (2011)

Mingyu Xiao,Hiroshi Nagamochi:Parameterized Edge Dominating Set in Cubic Graphs - (Extended Abstract).FAW-AAIM 2011: 100-112

Mingyu Xiao,Hiroshi Nagamochi:Further Improvement on Maximum Independent Set in Degree-4 Graphs.COCOA 2011: 163-178

Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New Parameterized Algorithms for the Edge Dominating Set Problem.MFCS 2011: 604-615

Mingyu Xiao,Ton Kloks,Sheung-Hung Poon:New parameterized algorithms for edge dominating set.CoRR abs/1104.4160(2011)

Mingyu Xiao:Finding minimum 3-way cuts in hypergraphs.Inf. Process. Lett. 110(14-15): 554-558 (2010)

Mingyu Xiao:Simple and Improved Parameterized Algorithms for Multiterminal Cuts.Theory Comput. Syst. 46(4): 723-736 (2010)

Mingyu Xiao:Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs.COCOA (2) 2010: 387-400

Mingyu Xiao:A Note on Vertex Cover in Graphs with Maximum Degree 3.COCOON 2010: 150-159

Mingyu Xiao,Takuro Fukunaga,Hiroshi Nagamochi:FPTAS's for Some Cut Problems in Weighted Trees.FAW 2010: 210-221

Mingyu Xiao:A Simple and Fast Algorithm for Maximum Independent Set in 3-Degree Graphs.WALCOM 2010: 281-292

教學情況

肖鳴宇教授除完成本科教學任務外，每年都會招收多名研究生。對於科研工作出色的學生，將推薦到海外交流或深造。其科研分為基礎科研和工程套用兩部分，具體參照如下：

1.基礎科研：建議想從事基礎算法研究的學生報考，特別是有一定數學分析能力或競賽經歷的同學。此方向的學習將大大加強學生的科研基礎。對於有志將來從事科研工作和出國深造的同學，可以考慮學習此方向。科研內容主要包括：算法分析與設計，最佳化算法，圖論及圖算法等。

該方向主要希望培養未來的大學教授和科研者，當然也包括大公司的高級研發人員。學生學習階段以學習和發表學術論文為主，論文達到一定級別則可推薦海外交流。

2. 工程套用：肖鳴宇教授也會招收工程方向的學生，該部分學生主要由實驗室聯合培養，從事雲計算方面的工程學習和鍛鍊。學生將進入雲計算及相關實驗室學習研究，同時將可能獲得其他資深老師的指導。