On the complexity of multi-parameterized cluster editing

DOI10.1016/J.JDA.2017.07.003MaRDI QIDQ2407948zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam

Publication date 6 October 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.09360

zbMATH Keywords

fixed-parameter tractabilitykernelizationcluster editingmulti-parameterization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The Cluster Editing problem seeks a transformation of a given undirected graph into a disjoint union of cliques via a minimum number of edge additions or deletions. A multi-parameterized version of the problem is studied, featuring a number of input parameters that bound the amount of both edge-additions and deletions per single vertex, as well as the size of a clique-cluster. We show that the problem remains NP-hard even when only one edge can be deleted and at most two edges can be added per vertex. However, the new formulation allows us to solve Cluster Editing (exactly) in polynomial time when the number of edge-edit operations per vertex is smaller than half the minimum cluster size. In other words, Correlation Clustering can be solved efficiently when the number of false positives/negatives per single data element is expected to be small compared to the minimum cluster size. As a byproduct, we obtain a kernelization algorithm that delivers linear-size kernels when the two edge-edit bounds are small constants.

Recommendations

• The Multi-parameterized Cluster Editing Problem
• Alternative parameterizations for cluster editing
• Cluster editing with locally bounded modifications
• A \(2k\) kernel for the cluster editing problem
• A More Effective Linear Kernelization for Cluster Editing

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• A golden ratio parameterized algorithm for cluster editing
• A more effective linear kernelization for cluster editing
• Cluster editing with locally bounded modifications
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Clustering with local restrictions
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Exact algorithms for cluster editing: Evaluation and experiments
• Fixed-parameter enumerability of cluster editing and related problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• Generalized graph clustering: recognizing \((p,q)\)-cluster graphs
• Going weighted: parameterized algorithms for cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• NP-hard problems in hierarchical-tree clustering
• Parameterized algorithms
• Parametrized complexity theory.
• Sufficient conditions for edit-optimal clusters
• The Multi-parameterized Cluster Editing Problem
• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT

Cited in

(18)

• Fixed-Parameter Tractable Generalizations of Cluster Editing
• Parameterized Dynamic Cluster Editing
• A new temporal interpretation of cluster editing
• A PTAS for the Cluster Editing Problem on Planar Graphs
• Alternative parameterizations for cluster editing
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• Tight bounds for parameterized complexity of Cluster Editing
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• The Multi-parameterized Cluster Editing Problem
• Editing to cliques: a survey of FPT results and recent applications in analyzing large datasets
• \((1,1)\)-cluster editing is polynomial-time solvable
• Generalized graph clustering: recognizing \((p,q)\)-cluster graphs
• An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
• Graph-Theoretic Concepts in Computer Science
• A survey of parameterized algorithms and the complexity of edge modification
• Parameterized dynamic cluster editing
• Fine-grained complexity analysis of some combinatorial data science problems
• Cluster editing with locally bounded modifications

This page was built for publication: On the complexity of multi-parameterized cluster editing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2407948)