On the complexity of multi-parameterized cluster editing
From MaRDI portal
Publication:2407948
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
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
Cites work
- 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
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- 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
(24)- Parameterized dynamic cluster editing
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- The Multi-parameterized Cluster Editing Problem
- Tight bounds for parameterized complexity of Cluster Editing
- A PTAS for the Cluster Editing Problem on Planar Graphs
- Generalized graph clustering: recognizing (p,q)-cluster graphs
- Alternative parameterizations for cluster editing
- Fixed-Parameter Tractable Generalizations of Cluster Editing
- Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
- Parameterized Dynamic Cluster Editing
- Cluster Editing in Multi-Layer and Temporal Graphs.
- Graph-Theoretic Concepts in Computer Science
- An improved fixed-parameter algorithm for 2-Club Cluster Edge Deletion
- \((1,1)\)-cluster editing is polynomial-time solvable
- A survey of parameterized algorithms and the complexity of edge modification
- Editing to cliques: a survey of FPT results and recent applications in analyzing large datasets
- A new temporal interpretation of cluster editing
- Fine-grained complexity analysis of some combinatorial data science problems
- Bicluster editing with overlaps: a vertex splitting approach
- A fixed-parameter branching algorithm for chromatic correlation clustering
- Applying a cut-based data reduction rule for weighted cluster editing in polynomial time
- Cluster editing with vertex splitting
- Cluster editing with locally bounded modifications
- Graph clustering problems under the Lens of parameterized local search
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)
