报告题目：Complexity Dichotomies for Maximum Weighted Digraph Partition Problem

报告专家：Gregory Gutin 伦敦大学皇家霍洛威学院 教授

报告时间：2024年9月13日  9:30—11:00

报告地点：南教1-120

报告摘要：We'll discuss complexity dichotomies (P vs NP) proved for a recently introduced problem Maximum Weighted Digraph Partition (MWDP), which generalizes Maximum Weight Directed Cut and a number of other optimization problems on directed and undirected graphs, see [1,2,3]. The dichotomies have applications in graph theory, game theory and economics. While the original proofs were purely graph-theoretical, now we can prove most of them using dichotomies for the Valued Constraint Satisfaction Problem. Joint work with A. Deligkas, E. Eiben, G. Gutin, P.R. Neary, G. Osipov, M. Wahlstrom and A. Yeo.

[1] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity of Efficient Outcomes in Binary-Action Polymatrix Games with Implications for Coordination Problems, Proc. IJCAI 2023, 2023.

[2] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem, arXiv:2307.01109.

[3] A. Deligkas, E. Eiben, G. Gutin, P.R. Neary and A. Yeo, Some coordination problems are harder than others, arXiv:2311.03195.

专家简介：Gregory Gutin，伦敦大学皇家霍洛威学院教授，欧洲科学院院士，亚太人工智能学会会士。1993年博士毕业于以色列特拉维夫大学，师从 Noga Alon教授。1996年，他被国际组合学与应用研究所授予Kirkman奖章。自2000年9月1日起，Gregory一直担任伦敦大学皇家霍洛威学院计算机科学系计算机科学教授。他于2014-2018年获得英国皇家学会沃尔夫森研究优秀奖，并于2017年入选欧洲科学院，2021年入选亚太人工智能协会(AAIA)。2015年、2016年、2021年和2022年在ACM信息安全访问控制研讨会上获得最佳论文奖。2019年，他被授予Amity全球学术优秀奖，2022年被授予AAIA杰出贡献奖。

Gutin的主要研究兴趣包括图和组合学、参数化、多项式、精确和近似算法以及组合优化。出版了两版专著(翻译成中文)，编辑了两本书。他在期刊和会议上发表或接受发表了250多篇论文。他的论文被引用超过11900次。

报告题目：Graph operations and a unified method for kinds of Tur\'an-type problems on paths, cycles and matchings

报告专家：艾江东 南开大学 副教授

报告时间：2024年9月13日  11:00—12:30

报告地点：南教1-120

报告摘要：We develop a method that provides a unified approach for solving some Tur\'an-type and generalized Tur\'an-type problems, degree power problems, and extremal spectra problems (mainly under spectral radius conditions and signless Laplacian spectral radius conditions) on paths, cycles, and matchings. Our results generalize classical results on cycles and matchings due to Kopylov and Erd\H{o}s-Gallai, respectively, and provide a positive resolution to an open problem originally proposed by Nikiforov. We improve and extend the spectral extremal results on paths due to Nikiforov, and due to Nikiforov and Yuan. We also offer a comprehensive solution to a connected version of a problem on the degree power sum of a graph containing no $P_k$, a topic initially studied by Caro and Yuster.

专家简介：艾江东，南开大学数学科学学院，副教授，博士生导师。博士毕业于英国伦敦大学皇家霍洛威学院。研究兴趣是图论及组合优化，主要是对有向图理论和代数图论的研究，包括有向图结构的分析和刻画、一般图结构的谱极值条件等等。发表论文十余篇，研究成果发表在SIAM J. Discrete Math, J. Graph Theory 等杂志。