Cluster deletion and clique partitioning in graphs with bounded clique number
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915512243453952 |
|---|---|
| author | Galesi, Nicola Huynh, Tony Ranjbar, Fariba |
| author_facet | Galesi, Nicola Huynh, Tony Ranjbar, Fariba |
| contents | The Cluster Deletion problem takes a graph $G$ as input and asks for a minimum size set of edges $X$ such that $G-X$ is the disjoint union of complete graphs. An equivalent formulation is the Clique Partition problem, which asks to find a partition of $V(G)$ into cliques such that the number of edges in the cliques is maximized.
We begin by giving a much simpler proof of a theorem of Gao, Hare, and Nastos that Cluster Deletion is efficiently solvable on the class of cographs. We then investigate Cluster Deletion and Clique Partition on permutation graphs, which are a superclass of cographs. Our findings suggest that Cluster Deletion may be NP-hard on permutation graphs.
Finally, we prove that for graphs with clique number at most $c$, there is a $\frac{2\binom{c}{2}}{\binom{c}{2}+1}$-approximation algorithm for Clique Partition. This is the first polynomial time algorithm which achieves an approximation ratio better than 2 for graphs with bounded clique number. More generally, our algorithm runs in polynomial time on any graph class for which Maximum Clique can be computed in polynomial time. We also provide a class of examples which shows that our approximation ratio is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_00922 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cluster deletion and clique partitioning in graphs with bounded clique number Galesi, Nicola Huynh, Tony Ranjbar, Fariba Data Structures and Algorithms Discrete Mathematics Combinatorics 05C85, 05C69, 90C27 G.2.2; F.2.0 The Cluster Deletion problem takes a graph $G$ as input and asks for a minimum size set of edges $X$ such that $G-X$ is the disjoint union of complete graphs. An equivalent formulation is the Clique Partition problem, which asks to find a partition of $V(G)$ into cliques such that the number of edges in the cliques is maximized. We begin by giving a much simpler proof of a theorem of Gao, Hare, and Nastos that Cluster Deletion is efficiently solvable on the class of cographs. We then investigate Cluster Deletion and Clique Partition on permutation graphs, which are a superclass of cographs. Our findings suggest that Cluster Deletion may be NP-hard on permutation graphs. Finally, we prove that for graphs with clique number at most $c$, there is a $\frac{2\binom{c}{2}}{\binom{c}{2}+1}$-approximation algorithm for Clique Partition. This is the first polynomial time algorithm which achieves an approximation ratio better than 2 for graphs with bounded clique number. More generally, our algorithm runs in polynomial time on any graph class for which Maximum Clique can be computed in polynomial time. We also provide a class of examples which shows that our approximation ratio is best possible. |
| title | Cluster deletion and clique partitioning in graphs with bounded clique number |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics 05C85, 05C69, 90C27 G.2.2; F.2.0 |
| url | https://arxiv.org/abs/2505.00922 |