We use cookies to improve your experience with our site.

团图删除和强三元闭包问题的2k点核

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

  • 摘要:
    研究背景 团图删除和强三元闭包是两个重要的NP完全问题,由于它们在社交网络分析、机器学习、计算生物学等领域的应用而受到很多关注。一方面,这两个问题有很多相似之处;另一方面,它们之间也存在着微妙的差异。在某些情况下,强三元闭包的解和团图删除的解有着很大的区别。最近,Gruttemeier和Komusiewicz从参数算法的角度研究了这两个问题,他们证明了强三元闭包存在4k大小的点核。此外,他们还指出,十多年前对团图编辑问题的一项研究暗示了团图删除问题也存在4k大小的点核。
    目的 我们的研究目的是从参数算法角度研究团图删除和强三元闭包问题。更具体地说,我们研究这两个问题的核化算法。
    方法 在处理强三元闭包时,我们将关键团及其邻居节点视为一个整体,而不是将它们分开进行分析,这使我们能够更有效地界定相关节点的数量。此外,在分析强三元闭包的核的大小时,我们引入了边不相交诱导路径的概念,这使我们能够以更简洁的方式获得强三元闭包问题中标记为弱的边数的下界。有趣的是,类似概念和结论对团图删除问题也成立。
    结果 我们证明了团图删除和强三元闭包问题都存在2k大小的点核。这是目前关于这两个问题最好的结果。
    结论 我们的结果表明,将关键团及其邻居节点作为一个整体考虑,可以更有效地界定相关节点的数量,这种方法也可以用于其他问题。此外,我们的分析进一步揭示了团图删除和强三元闭包之间的联系。

     

    Abstract: Cluster deletion and strong triadic closure are two important NP-complete problems that have received significant 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 between 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 problems. 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. Furthermore, our analysis provides additional insights into the relationship between cluster deletion and strong triadic closure.

     

/

返回文章
返回