2k-Vertex Kernels for Cluster Deletion and Strong Triadic Closure  

作　　者：高文宇 高航 Wen-Yu Gao;Hang Gao(School of Information,Guangdong University of Finance and Economics,Guangzhou 510320,China;Department of Computer Science,Rutgers University,Piscataway 08854,U.S.A.)

机构地区：[1]School of Information,Guangdong University of Finance and Economics,Guangzhou 510320,China [2]Department of Computer Science,Rutgers University,Piscataway 08854,U.S.A.

出　　处：《Journal of Computer Science & Technology》2023年第6期1431-1439,共9页计算机科学技术学报（英文版）

摘　　要：Cluster deletion and strong triadic closure are two important NP-complete problems that have received sig-nificant attention due to their applications in various areas,including social networks and data analysis.Although cluster deletion and strong triadic closure are closely linked by induced paths on three vertices,there are subtle differences be-tween them.In some cases,the solutions of strong triadic closure and cluster deletion are quite different.In this paper,we study the parameterized algorithms for these two problems.More specifically,we focus on the kernels of these two prob-lems.Instead of separating the critical clique and its neighbors for analysis,we consider them as a whole,which allows us to more effectively bound the number of related vertices.In addition,in analyzing the kernel of strong triadic closure,we introduce the concept of edge-disjoint induced path on three vertices,which enables us to obtain the lower bound of weak edge number in a more concise way.Our analysis demonstrates that cluster deletion and strong triadic closure both admit 2k-vertex kernels.These results represent improvements over previously best-known kernels for both problems.Further-more,our analysis provides additional insights into the relationship between cluster deletion and strong triadic closure.

关 键 词：cluster deletion strong triadic closure KERNELIZATION parameterized complexity social network 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]