Paw图–边删除问题的线性顶点核心化算法  

A linear vertex kernel for the Paw edge covering problem

作　　者：盛子默 肖鸣宇 Zimo SHENG;Mingyu XIAO(School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China)

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《中国科学：信息科学》2024年第7期1604-1619,共16页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:62372095,61972070)资助项目。

摘　　要：图边删除问题中一类重要问题是研究是否可以删除图中不超过k条边之后使得剩余的图不存在某个子图结构H,而子图H为顶点个数不超过4的连通图的情况被研究得最为广泛.本文主要考虑H为Paw图(三角形其中一个顶点再邻接一条边)的情况,称为Paw图–边删除问题,并为该问题设计了一个32k个顶点的问题核.这是该问题的第1个线性顶点大小的问题核.文中主要的技术是结合两个新的皇冠分解的变体来分析图的结构从而对图进行简化.One important class of problems in graph theory involves investigating whether it is possible to delete at most k edges from a graph in such a way that the remaining graph does not contain a certain subgraph structure H.The case where the subgraph H is a connected graph with at most 4 vertices has been widely studied.In this paper,we specifically consider the case where H is a Paw graph(a triangle with one vertex incident to an additional edge).The corresponding problem is called the Paw edge covering problem(also known as the{Paw,Diamond,K4}-free edge deletion problem).In this paper,by using two new variants of crown decompositions,we show that the Paw edge covering problem has a kernel of 32k vertices,which is the first linear-size vertex kernel for this problem.

关 键 词：图算法 核心化算法 H-边删除问题 Paw图–边删除问题 皇冠分解技术 

分 类 号：O157.5[理学—数学]