学术讲座【Exact Algorithms on the Matching Cut Problem】
时间：2019年11月06日 (星期三) 15:00 ~ 17:00
地点：旗山校区理工南楼616报告厅
主讲：National Dong Hwa University，Professor Sheng-Lung Peng
主办：福建省网络安全与密码技术重点实验室
参加对象：网络安全方向老师及研究生
报告人简介：Sheng-Lung Peng is a Professor of the Department of Computer Science and Information Engineering at National Dong Hwa University, Hualien, Taiwan. He received the BS degree in Mathematics from National Tsing Hua University, and the MS and PhD degrees in Computer Science from the National Chung Cheng University and National Tsing Hua University, Taiwan, respectively. He is an honorary Professor of Beijing Information Science and Technology University of China and a visiting Professor of Ningxia Institute of Science and Technology of China. He serves the regional director of the ICPC Contest Council for Taiwan region, a director of Institute of Information and Computing Machinery, of Information Service Association of Chinese Colleges and of Taiwan Association of Cloud Computing. He is also a supervisor of Chinese Information Literacy Association, of Association of Algorithms and Computation Theory, and of Interlibrary Cooperation Association in Taiwan. His research interests are in designing and analyzing algorithms for Bioinformatics, Combinatorics, Data Mining, and Networks. Dr. Peng has edited several special issues at journals, such as Soft Computing, Journal of Real-Time Image Processing, Journal of Internet Technology, Journal of Computers, MDPI Algorithms, and so on. He published over 100 international conferences and journal papers
报告摘要：In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is NP -complete on graphs with minimum degree two.
In this talk, we present some state-of-art works for the matching cut problem on graphs. In particular, we show our recent result that, for any given constant e > 0, Matching Cut is NP-complete in the class of n-vertex (bipartite) graphs with minimum degree δ > n1−ϵ. We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree δ ≥ 3 in time O∗(λn), where λ is the positive root of the polynomial xδ+1−xδ−1. This is a very fast exact exponential time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is O∗(1.0099n) on graphs with minimum degree δ ≥ 469. Complementing our hardness results, we show that, for any fixed constant 1 < c < 4, Matching Cut is solvable in polynomial time for graphs with very large minimum degree δ≥1/c n.