3. 独立集、点覆盖及其相关问题的精确算法和参数算法研究，国家自然科学基金，主持

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

5. 参数算法理论及其应用研究，中央高校基金，主持

6. 图分割问题的参数算法研究，电子科技大学校青年科学基金，主持

肖鸣宇教授又攻下了一个基础性计算难题——改进独立集问题的精确算法，打破了国际著名算法理论大师罗宾逊在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. 工程应用：肖鸣宇教授也会招收工程方向的学生，该部分学生主要由实验室联合培养，从事云计算方面的工程学习和锻炼。学生将进入云计算及相关实验室学习研究，同时将可能获得其他资深老师的指导。