Journal
JOURNAL OF DISCRETE ALGORITHMS
Volume 16, Issue -, Pages 79-89Publisher
ELSEVIER
DOI: 10.1016/j.jda.2012.04.005
Keywords
Cluster editing; Parameterized algorithm; FPT; Search tree algorithm; Computational complexity
Categories
Ask authors/readers for more resources
The Cluster Editing problem asks to transform a graph by at most k edge modifications into a disjoint union of cliques. The problem is NP-complete, but several parameterized algorithms are known. We present a novel search tree algorithm for the problem, which improves running time from 0(1.76(k) + m + n) to 0(1.62(k) + m + n) for m edges and n vertices. In detail, we can show that we can always branch with branching vector (2, 1) or better, resulting in the golden ratio as the base of the search tree size. Our algorithm uses a well-known transformation to the integer-weighted counterpart of the problem. To achieve our result, we combine three techniques: First, we show that zero-edges in the graph enforce structural features that allow us to branch more efficiently. This is achieved by keeping track of the parity of merged vertices. Second, by repeatedly branching we can isolate vertices, releasing cost. Third, we use a known characterization of graphs with few conflicts. We then show that Integer-Weighted Cluster Editing remains NP-hard for graphs that have a particularly simple structure: namely, a clique minus the edges of a triangle. (C) 2012 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available