.png){kind=icon}
.png){kind=icon}
Return
When can Cluster Deletion with bounded weights be solved efficiently?
.png){kind=icon}
OA
AI
DOI：10.1016/j.dam.2025.12.028.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In the NP-hard WEIGHTED CLUSTER DELETION problem, the input is an undirected graph G = (V, E) and an edge-weight function omega : E -> N, and the task is to partition the vertex set V into cliques so that the total weight of edges in the cliques is maximized. Recently, it has been shown that WEIGHTED CLUSTER DELETION is NP-hard on some graph classes where CLUSTER DELETION, the special case where every edge has unit weight, can be solved in polynomial time. We study the influence of the value t of the largest edge weight assigned by omega on the problem complexity for such graph classes. Our main results are that WEIGHTED CLUSTER DELETION is fixed-parameter tractable with respect to t on graph classes whose graphs consist of well-separated clusters that are connected by a sparse periphery. Concrete examples for such classes are split graphs and graphs that are close to cluster graphs. We complement our results by strengthening previous hardness results for WEIGHTED CLUSTER DELETION. For example, we show that WEIGHTED CLUSTER DELETION is NP-hard on restricted subclasses of cographs even when every edge has weight 1 or 2. (c) 2025 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Graph clustering
Split graphs
Cographs
Parameterized complexity
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
D
IF:
1.1
Papers:
336
Citations:
7.7K