A golden ratio parameterized algorithm for Cluster Editing

AbstractThe 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 O(1.76k+m+n) to O(1.62k+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