When can cluster deletion with bounded weights be solved efficiently?

DOI10.1016/J.DAM.2025.12.028MaRDI QIDQ6854636zbMATH OpenFDO

Authors Jaroslav Garvardt, Christian Komusiewicz, Nils Morawietz

Publication date 24 February 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.12.028

zbMATH Keywords

cographsgraph clusteringparameterized complexitysplit graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A completeness theory for polynomial (Turing) kernelization
• A more effective linear kernelization for cluster editing
• A more relaxed model for graph-based data clustering: s-plex cluster editing
• A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to \(P_4\)-sparse graphs
• A single-exponential time 2-approximation algorithm for treewidth
• Algorithms for unipolar and generalized split graphs
• Applying modular decomposition to parameterized cluster editing problems
• Bounding the running time of algorithms for scheduling and packing problems
• Cluster deletion on interval graphs and split related graphs
• Cluster deletion revisited
• Cluster editing
• Cluster editing with locally bounded modifications
• Cluster editing: kernelization based on edge cuts
• Cluster graph modification problems
• Complexity of the cluster deletion problem on subclasses of chordal graphs
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Even faster parameterized cluster deletion and cluster editing
• Faster parameterized algorithm for cluster vertex deletion
• Fundamentals of parameterized complexity
• Geometric versions of the three-dimensional assignment problem under general norms
• Going weighted: parameterized algorithms for cluster editing
• Graph clustering problems under the Lens of parameterized local search
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Kernelization lower bounds through colors and IDs
• Kernelization of packing problems
• On the complexity of k-SAT
• On the relation of strong triadic closure and cluster deletion
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Parameterized algorithms
• Parameterized aspects of strong subgraph closure
• Structural parameterization of cluster deletion
• The cluster deletion problem for cographs

This page was built for publication: When can cluster deletion with bounded weights be solved efficiently?

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