Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion
Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion
复制标题
DOI：
10.1007/s00453-011-9492-7
复制
发表时间：
2009-09
期刊：
影响因子：
1.1
通讯作者：
René van Bevern;Hannes Moser;R. Niedermeier
中科院分区：
文献类型：
--
作者：
René van Bevern;Hannes Moser;R. Niedermeier
我们介绍 s-Plex 簇顶点删除问题。与聚类顶点删除问题一样，它是 NP 难题，并且由基于图的数据聚类驱动。聚类顶点删除中的任务是从图中删除顶点，使其连接的组件成为派系，而 s-Plex 聚类顶点删除中的任务是从图中删除顶点，使其连接的组件成为 s-plex。 s-plex 是其中每个顶点与最多 s-1 个其他顶点不相邻的图；派系是 1-plex。与簇顶点删除相反，s-Plex 簇顶点删除允许平衡顶点删除的数量与所得簇的大小和密度，这些簇是 s-plex，而不是派系。这项工作的重点是为 s-Plex 集群顶点删除开发可证明高效且有效的数据缩减规则。就固定参数算法而言，这些产生了所谓的问题内核。类似的问题 s-Plex 编辑，其任务是插入或删除边，以便图的连接组件成为 s-plex，也已根据固定参数算法进行了研究。使用允许的图修改次数作为参数，我们预计 s-Plex 簇顶点删除的典型参数值将显着低于 s-Plex 编辑的参数值，因为一个顶点删除可能会导致大量边删除。这为 s-Plex 簇顶点删除提供了更快的固定参数算法的前景。
We introduce the s-Plex Cluster Vertex Deletion problem. Like the Cluster Vertex Deletion problem, it is NP-hard and motivated by graph-based data clustering. While the task in Cluster Vertex Deletion is to delete vertices from a graph so that its connected components become cliques, the task in s-Plex Cluster Vertex Deletion is to delete vertices from a graph so that its connected components become s-plexes. An s-plex is a graph in which every vertex is nonadjacent to at most s-1 other vertices; a clique is an 1-plex. In contrast to Cluster Vertex Deletion, s-Plex Cluster Vertex Deletion allows to balance the number of vertex deletions against the sizes and the density of the resulting clusters, which are s-plexes instead of cliques. The focus of this work is the development of provably efficient and effective data reduction rules for s-Plex Cluster Vertex Deletion. In terms of fixed-parameter algorithmics, these yield a so-called problem kernel. A similar problem, s-Plex Editing, where the task is the insertion or the deletion of edges so that the connected components of a graph become s-plexes, has also been studied in terms of fixed-parameter algorithmics. Using the number of allowed graph modifications as parameter, we expect typical parameter values for s-Plex Cluster Vertex Deletion to be significantly lower than for s-Plex Editing, because one vertex deletion can lead to a high number of edge deletions. This holds out the prospect for faster fixed-parameter algorithms for s-Plex Cluster Vertex Deletion.