Faster Parameterized Algorithm for Cluster Vertex Deletion
- PDF / 807,879 Bytes
- 21 Pages / 439.642 x 666.49 pts Page_size
- 27 Downloads / 206 Views
Faster Parameterized Algorithm for Cluster Vertex Deletion Dekel Tsur1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In the CLUSTER VERTEX DELETION problem the input is a graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results in a graph in which every connected component is a clique. We give an algorithm for CLUSTER VERTEX DELETION whose running time is O ∗ (1.811k ). Keywords Graph algorithms · Parameterized complexity
1 Introduction Clustering is a central optimization problem with applications in numerous fields (e.g., [1, 2]). In the clustering problem the input is a set of elements and similarity values for all pairs of elements. The goal is to partition the elements into disjoint sets, called clusters, such that the similarity values between elements in the same cluster are “large” and the similarity values between elements from different clusters are “small”. One approach for clustering is building a similarity graph whose vertices correspond to elements and there is an edge between two vertices if and only if the similarity of their corresponding elements exceeds some threshold. Ideally, the resulting graph G would be a cluster graph, that is, every connected component of G is a clique (i.e., a complete graph). In practice, G is only close to being a cluster graph. Therefore, the clustering problem can be modeled by the problem of modifying the graph G into a cluster graph using a minimum number of modifications to the graph. There are several ways to define the set of allowed modifications. In the CLUSTER
Dekel Tsur
[email protected] 1
Ben-Gurion University of the Negev, Beer-Sheva, Israel
Theory of Computing Systems
EDITING problem the allowed modifications are edge deletions and edge additions, and in the CLUSTER DELETION problem the allowed modifications are edge deletions. In the CLUSTER VERTEX DELETION problem, the allowed modifications are vertex deletions. Formally, the input to the CLUSTER VERTEX DELETION problem is an undirected graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results in a cluster graph. Note that a graph G is a cluster graph if and only if G does not contain an induced path of size 3 (i.e., an induced path with 3 vertices). As CLUSTER VERTEX DELETION is equivalent to the problem of finding whether there is a set of vertices of size at most k that hits every induced path of size 3 in G, the problem can be solved in O ∗ (3k ) time [4] (where O ∗ (f (k)) = O(f (k) · nO(1) )). A faster O ∗ (2.26k )-time algorithm for this problem was given by Gramm et al. [10]. The next improvements on the parameterized complexity of this problem came from results on the more general 3-HITTING SET problem [7, 15]. The currently fastest parameterized algorithm for 3-HITTING SET runs in O ∗ (2.076k ) time [15], and therefore CLUSTER VERTEX DELETION
Data Loading...
