On the complexity of multi-parameterized cluster editing

DOI10.1016/J.JDA.2017.07.003zbMATH Open1419.68056arXiv1511.09360OpenAlexW2963069757MaRDI QIDQ2407948FDOQ2407948

Authors: Faisal N. Abu-Khzam 

Publication date: 6 October 2017

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

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.

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

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

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)

Cites Work

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

Cited In (16)

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

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)