Fast branching algorithm for Cluster Vertex Deletion

2013/06/17 by Boral, Anudhyan, Cygan, Marek, Kociumaka, Tomasz +1 · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1306.3877

Abstract

In the family of clustering problems, we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hueffner et al. [Theory Comput. Syst. 2010] initiated the parameterized study of Cluster Vertex Deletion, where the allowed modification is vertex deletion, and presented an elegant O(2^k * k⁹ + n * m)-time fixed-parameter algorithm, parameterized by the solution size. In our work, we pick up this line of research and present an O(1.9102^k * (n + m))-time branching algorithm.

Cited by

• Finding b-colorings Using Feedback Edges
• Shift Bribery over Social Networks

Related

• Faster parameterized algorithm for Cluster Vertex Deletion
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
• Cluster deletion revisited
• A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
• Cluster Editing with Vertex Splitting