FPT Algorithms for Finding Near-Cliques in c-Closed Graphs
FPT Algorithms for Finding Near-Cliques in c-Closed Graphs
复制标题
DOI：
10.4230/lipics.itcs.2022.17
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Balaram Behera;Edin Husi'c;Shweta Jain;Tim Roughgarden;C. Seshadhri
中科院分区：
文献类型：
--
作者：
Balaram Behera;Edin Husi'c;Shweta Jain;Tim Roughgarden;C. Seshadhri
寻找大的团或团缺少一些边缘是一个基本的算法任务，在现实世界的图的研究，在社区检测，模式识别和聚类的应用。从最近的社会网络分析的实证工作中，已经出现了一些有效的基于回溯的算法来解决这些问题。鉴于集团计数的NP-困难的变种，这些结果提出了一个挑战，超越最坏情况下分析这些问题。受现实世界图的三元闭包的启发，Fox等人（SICOMP 2020）引入了$c$-闭图的概念，并证明了最大团计数是关于$c$的固定参数易处理的。在实践中，由于数据中的噪声，人们希望实际上发现“近团”，其可以被表征为具有稀疏子图的团。在这项工作中，我们证明了许多不同种类的最大近团可以列举在多项式时间（FPT在$C$）的$C$-闭图。我们研究了各种既定的概念，这样的子结构，包括$k$丛，有界退化和有界树宽图的补充。有趣的是，我们的算法遵循相对简单的回溯程序，类似于实践中所做的。我们的研究结果强调了$c$-闭图类的社会网络分析的理论理解的意义。
Finding large cliques or cliques missing a few edges is a fundamental algorithmic task in the study of real-world graphs, with applications in community detection, pattern recognition, and clustering. A number of effective backtracking-based heuristics for these problems have emerged from recent empirical work in social network analysis. Given the NP-hardness of variants of clique counting, these results raise a challenge for beyond worst-case analysis of these problems. Inspired by the triadic closure of real-world graphs, Fox et al. (SICOMP 2020) introduced the notion of $c$-closed graphs and proved that maximal clique enumeration is fixed-parameter tractable with respect to $c$. In practice, due to noise in data, one wishes to actually discover"near-cliques", which can be characterized as cliques with a sparse subgraph removed. In this work, we prove that many different kinds of maximal near-cliques can be enumerated in polynomial time (and FPT in $c$) for $c$-closed graphs. We study various established notions of such substructures, including $k$-plexes, complements of bounded-degeneracy and bounded-treewidth graphs. Interestingly, our algorithms follow relatively simple backtracking procedures, analogous to what is done in practice. Our results underscore the significance of the $c$-closed graph class for theoretical understanding of social network analysis.