betaFeedback

WorksComputer Science

Cluster deletion in cographs, permutation graphs, and graphs with bounded clique number

Abstract

The Cluster Deletion problem asks for a minimum-size edge set whose deletion turns a graph into a disjoint union of complete graphs. Equivalently, the Clique Partition problem asks for a partition of the vertex set into cliques that maximizes the number of edges within the parts. We give a simpler proof of a result of Gao, Hare, and Nastos (Discete Mathematics, 2013), that Cluster Deletion is polynomial-time solvable on cographs. In addition, we show that the natural linear programming formulation of Clique Partition is exact on cographs. We then show that Cluster Deletion is NP-complete on permutation graphs, which are a superclass of cographs. This answers an open question of Konstantinidis and Papadopoulos (Algorithmica, 2021). We also exhibit a permutation graph on nine vertices for which the linear programming formulation is not exact. Finally, for graphs with clique number at most cc, we give a polynomial-time 2(c2)/((c2)+1)2\binom{c}{2}/(\binom{c}{2}+1)-approximation algorithm for Clique Partition. More generally, the algorithm runs in polynomial time on every graph class for which a maximum clique can be found in polynomial time. For each fixed c≥3c\geq 3, we also construct infinitely many examples attaining the stated approximation ratio. The same examples show that, for Cluster Deletion , the algorithm is a 22-approximation and no better, for every fixed c≥3c \geq 3.

Introduction

Graph clustering is a fundamental problem in graph theory with numerous real-world applications, including the identification of functionally related genes in computational biology [5], community detection in social networks [14], image segmentation [33], and machine learning [3, 26]. The goal is to partition the vertices into clusters with many edges within clusters and few edges between clusters. Since a complete graph is the densest possible graph, this motivates the following approach.

Cluster Deletion:

Input: A graph GG.

Output: A minimum size set of edges X⊆E(G)X \subseteq E(G) such that G−XG-X is a disjoint union of complete graphs.

A disjoint union of complete graphs is also called a cluster graph. Given a graph GG as input, the CLUSTER DELETION problem is equivalent to maximizing the number of edges in a spanning subgraph HH of GG which is a cluster graph. We call the equivalent ‘complementary’ version the CLIQUE PARTITION problem.

Clique Partition:

Input: A graph GG.

Output: A partition (X1,…,Xs)(X_1,\ldots,X_s) of V(G)V(G) such that each XiX_i is a clique of GG and ∑i=1s∣E(Xi)∣\sum_{i=1}^{s}|E(X_i)| is maximum.

Whenever we speak of NP-completeness, we refer to the natural decision versions of these problems. Since CLUSTER DELETION has a solution of size at most kk if and only if CLIQUE PARTITION has a solution of size at least ∣E(G)∣−k|E(G)| - k, the two decision problems are equivalent, and both are clearly in NP.

Previous work. Shamir et al. [32] proved that CLUSTER DELETION is NP-hard for general graphs. Despite its computational difficulty, the problem has been extensively explored within the realms of parameterized complexity [4, 7, 9, 16, 19, 22], approximation algorithms [2, 8, 10, 30, 35, 36], and restricted graph classes.

For instance, CLUSTER DELETION is polynomial time solvable on cographs [16], split graphs [6, 25], (proper) interval graphs [6, 25], P4P_4- and paw-free graphs [21] and graphs with maximum degree at most three [24]. On the other hand, NP-hardness persists on C4C_4-free graphs with maximum degree four [24], planar graphs [17], chordal graphs [6], C5C_5-free graphs and (2K2,3K1)(2K_2, 3K_1)-free graphs [16].

Dessmark et al. [10] introduced a simple greedy strategy (which we call GREEDY) of repeatedly choosing maximum cliques, and proved that GREEDY is a 2-approximation for both CLUSTER DELETION and CLIQUE PARTITION. However, GREEDY does not necessarily run in polynomial time, since it requires MAX CLIQUE as a subroutine. Gao et al. [16] proved that GREEDY optimally solves CLIQUE PARTITION (and hence also CLUSTER DELETION) on cographs in polynomial time.

Interestingly, the weighted version of CLUSTER DELETION often exhibits greater computational hardness even on instances where the unweighted version is tractable. For instance, while unweighted CLUSTER DELETION is tractable on split graphs and cographs, the weighted version remains NP-hard on these classes [6]. There are also other popular generalizations of CLUSTER DELETION, including correlation clustering [3, 32], where one is allowed to delete or add edges. In this work, we focus on the unweighted variant of CLUSTER DELETION.

From the perspective of approximation algorithms, there have been a series of results for CLUSTER DELETION with progressively improved guarantees. The first approximation algorithm for CLUSTER DELETION achieved an approximation ratio of 4 using a linear programming (LP) relaxation [8]. Recent work of Balmaseda et al. [2] refined the analysis of two earlier algorithms, improving the approximation ratio from 4 to 3. The state of the art is the 2-approximation of Veldt et al. [36]. However, the LP-based approaches are computationally expensive due to the large number of constraints involved. To address this, recent work has introduced faster algorithms by leveraging alternative LP formulations such as Strong Triadic Closure (STC) labeling [34], resulting in practical 4-approximations [35]. Veldt [35] also proposed the first combinatorial algorithm, MatchFlipPivot, which achieves similar approximation guarantees at significantly reduced runtime.

The approximation status of the vertex version of CLUSTER DELETION, in which vertices rather than edges are deleted, was settled by Aprile et al. [1]. They gave a 2-approximation algorithm, which is best possible assuming the Unique Games Conjecture.

Our contributions. We begin by giving a much simpler proof of correctness of the main result from [16].

Theorem 1.1 ([16]). For every cograph GG, GREEDY outputs an optimal clique partition of GG.

The proof in [16] uses a quite subtle induction, which requires carefully extending a given clique partition while controlling the number of parts of the clique partition. We instead use the well-known fact that every cograph is either the disjoint union of two smaller cographs or the join of two smaller cographs. This gives a very clean inductive proof of Theorem 1.1. We also note that Theorem 4 from [16] is a direct consequence of the majorization inequality (Karamata’s inequality [27]). Our method also proves that the natural linear programming formulation is exact on cographs. To be precise, let C(G)\mathcal{C}(G) be the family of all nonempty cliques of GG, and consider

max⁡∑K∈C(G)(∣K∣2)xKsubject to∑K∈C(G)v∈KxK=1(v∈V(G)),xK≥0(K∈C(G)).(1)\begin{aligned} \max\quad& \sum_{K \in\mathcal{C}(G)} \binom{|K|}{2} x_K \\ \text{subject to}\quad& \sum_{\substack{K \in\mathcal{C}(G) \\ v \in K}} x_K = 1 \qquad(v \in V(G)), \\ & x_K \ge0 \qquad(K \in\mathcal{C}(G)). \tag*{(1)} \end{aligned}

Theorem 1.2. For every cograph GG, (LP) has an optimal solution in which every variable is in {0,1}\{0,1\}.

We next analyze CLIQUE PARTITION and CLUSTER DELETION on permutation graphs, which are a superclass of cographs. We prove that both problems are NP-complete on permutation graphs.

Theorem 1.3. CLUSTER DELETION and CLIQUE PARTITION are NPNP-complete on permutation graphs.

Theorem 1.3 settles an open question of Konstantinidis and Papadopoulos [25], and suggests that cographs are at the boundary of tractability and intractability for CLUSTER DELETION. The proof is a polynomial reduction from the OPTIMUM COST CHROMATIC PARTITION problem, which Jansen [23] proved to be NPNP-complete on permutation graphs. Since permutation graphs are exactly the graphs that are both comparability and cocomparability graphs, Theorem 1.3 also implies that CLUSTER DELETION is NPNP-complete on comparability graphs and on cocomparability graphs (Corollary 5.7).

Theorem 1.3 also has consequences for the linear program (LP). Although (LP) has exponentially many variables, it can be solved in polynomial time on permutation graphs via the ellipsoid method, so Theorem 1.3 implies that Theorem 1.2 does not extend to permutation graphs unless P=NP\mathsf{P} = \mathsf{NP}. In fact, we give an explicit permutation graph on nine vertices for which (LP) is not exact (Proposition 4.6).

Finally, we introduce another variant of GREEDY. For a graph GG, we let ω(G)\omega(G) and ω′(G)\omega^{\prime}(G) be the number of vertices and edges, respectively, in a maximum clique of GG. The main idea is very simple: if ω(G)≤2\omega(G) \le2, then a maximum clique partition is just a maximum matching, and hence can be found in polynomial-time via Edmonds’ matching algorithm [12]. Therefore, we propose the following modification of GREEDY. We run GREEDY as long as ω(G)≥3\omega(G) \ge3. Once ω(G)≤2\omega(G) \le2, we instead use Edmonds’ matching algorithm on the remaining graph and add the maximum matching to the clique partition. We call this algorithm GREEDY EDMONDS. We prove that for every graph GG, GREEDY EDMONDS is a 2ω′(G)ω′(G)+1\frac{2\omega^{\prime}(G)}{\omega^{\prime}(G)+1}-approximation algorithm for CLIQUE PARTITION.

Theorem 1.4. For every graph GG, GREEDY EDMONDS returns a clique partition X\mathcal{X} such that

OPT≤2ω′(G)ω′(G)+1∣E(X)∣,\mathop{\mathrm{OPT}} \le\frac{2\omega^{\prime}(G)}{\omega^{\prime}(G)+1} \lvert E(\mathcal{X}) \rvert,

where OPT\mathop{\mathrm{OPT}} is the number of edges in an optimal clique partition of GG.

Although optimal solutions to CLIQUE PARTITION correspond to optimal solutions to CLUSTER DELETION, it is not necessarily true that an α\alpha-approximate solution to CLIQUE PARTITION corresponds to an α\alpha-approximate solution to CLUSTER DELETION. Indeed, for general nn-vertex graphs, Dessmark et al. [10] proved that there is no polynomial time n1−O(1(log⁡n)γ)n^{1-O\left(\frac{1}{(\log n)^\gamma}\right)}-approximation algorithm for CLIQUE PARTITION (for some constant γ\gamma), unless NP⊆ZPTIME(2(log⁡n)O(1))\mathsf{NP} \subseteq\mathsf{ZPTIME}\left(2^{(\log n)^{O(1)}}\right). On the other hand, as already mentioned, there are constant factor approximations for CLUSTER DELETION.

Note that GREEDY EDMONDS runs in polynomial time on any graph class for which a maximum clique can be found in polynomial time. Examples of such graph classes include graphs of bounded treewidth, perfect graphs (which include interval graphs and chordal graphs), distance-hereditary graphs, and graphs with bounded clique number. To our knowledge, for graphs of bounded clique number, GREEDY EDMONDS is the first polynomial-time algorithm that achieves an approximation ratio better than 2 for CLIQUE PARTITION. For general graphs GG, the best approximation algorithm for CLIQUE PARTITION is the ω(G)\omega(G)-approximation algorithm from [10].

In view of Theorem 1.3, it is natural to ask for approximation algorithms for CLIQUE PARTITION on permutation graphs. Since maximum cliques and maximum matchings can be computed efficiently in permutation graphs, Theorem 1.4 yields the following corollary.

Corollary 1.5. Given an nn-vertex permutation graph GG, GREEDY EDMONDS returns in O(n2log⁡n)O(n^{2}\log n) time a clique partition X\mathcal{X} such that

OPT≤2ω′(G)ω′(G)+1∣E(X)∣,\mathop{\mathrm{OPT}} \le\frac{2\omega^{\prime}(G)}{\omega^{\prime}(G)+1} \lvert E(\mathcal{X}) \rvert,

where OPT\mathop{\mathrm{OPT}} is the number of edges in an optimal clique partition of GG.

Proof. Let GG be an nn-vertex permutation graph. A permutation representation of GG can be found in O(n+∣E(G)∣)O(n+\lvert E(G)\rvert) time [28]. Since a maximum clique in a permutation graph can be found in O(nlog⁡n)O(n\log n) time from such a representation [15], the greedy portion of GREEDY EDMONDS can be made to run in O(n2log⁡n)O(n^{2}\log n) time. Finally, Rhee and Liang [31] proved that a maximum matching of an nn-vertex permutation graph can be found in O(nlog⁡log⁡n)O(n\log\log n)-time. Thus, the total running time is O(n2log⁡n)O(n^{2}\log n).

Finally, we show that the approximation ratio in Theorem 1.4 is best possible for GREEDY EDMONDS, for every fixed value of the clique number, and that the same examples show that for CLUSTER DELETION the approximation ratio of GREEDY EDMONDS is exactly 2.

Theorem 1.6. For each fixed ℓ≥3\ell\ge3, there are infinitely many graphs GG with ω(G)=ℓ\omega(G) = \ell and clique partitions X\mathcal{X} that can be output by GREEDY EDMONDS such that

OPT⁡=2(ℓ2)(ℓ2)+1∣E(X)∣and∣E(X‾)∣=2OPT⁡CD,\operatorname{OPT} = \frac{2\binom{\ell}{2}}{\binom{\ell}{2}+1}\lvert E(\mathcal{X})\rvert\qquad\text{and} \qquad\lvert E(\overline{\mathcal{X}})\rvert= 2\operatorname{OPT}_{\mathrm{CD}},

where OPT⁡\operatorname{OPT} is the maximum number of edges in a clique partition of GG and OPT⁡CD=∣E(G)∣−OPT⁡\operatorname{OPT}_{\mathrm{CD}} = \lvert E(G)\rvert- \operatorname{OPT} is the minimum number of edges whose deletion turns GG into a cluster graph.

Preliminaries

All graphs in this paper are assumed to be simple and undirected. We use standard graph theoretical notation and terminology (see [11]). For example, we say that a graph GG is HH-free, if it does not contain HH as an induced subgraph. Note that GG is a cluster graph if and only if GG is P3P_3-free, where P3P_3 is a 3-vertex path. A graph GG is a cograph if it is P4P_4-free. The complement of a graph GG is denoted by G‾\overline{G}. The disjoint union of two graphs G1G_1 and G2G_2 is denoted by G1⊔G2G_1 \sqcup G_2, and the join G1∨G2G_1 \vee G_2 is the graph obtained from G1⊔G2G_1 \sqcup G_2 by adding all edges between V(G1)V(G_1) and V(G2)V(G_2).

A clique in a graph GG is a set of pairwise adjacent vertices of GG, and a stable set is a set of pairwise nonadjacent vertices. Thus, the stable sets of GG are exactly the cliques of G‾\overline{G}. A clique partition of GG is a partition of V(G)V(G) into cliques of GG. If X\mathcal{X} is a clique partition of GG, we let E(X)E(\mathcal{X}) and E(X‾)E(\overline{\mathcal{X}}) denote the set of edges of GG contained (respectively, not contained) in the cliques of X\mathcal{X}.

For each n∈Nn \in\mathbb{N}, we let [n]:={1,…,n}[n] := \{1,\ldots,n\} and SnS_n denote the set of all permutations of [n][n]. We write a permutation as a word π=[π1,…,πn]\pi= [\pi_1,\ldots,\pi_n], and write pos⁡π(v)\operatorname{pos}_{\pi}(v) for the position of the value vv in this word. The permutation graph associated with π\pi, denoted by GπG_{\pi}, has vertex set [n][n] and edge set

E(Gπ):={{u,v}:u<v and pos⁡π(u)>pos⁡π(v)}.E(G_{\pi}) := \bigl\{\{u,v\} : u < v \text{ and } \operatorname{pos}_{\pi}(u) > \operatorname{pos}_{\pi}(v)\bigr\}.

Equivalently, if i<ji < j and πi>πj\pi_i > \pi_j, then {πi,πj}\{\pi_i,\pi_j\} is an edge. Thus, cliques of GπG_{\pi} are precisely the decreasing subsequences of the word π\pi, and stable sets of GπG_{\pi} are precisely the increasing subsequences of π\pi. In particular, if πR:=[πn,…,π1]\pi^{R} := [\pi_n,\ldots,\pi_1] is the reverse of π\pi, then GπR=Gπ‾G_{\pi^{R}} = \overline{G_{\pi}}, so the class of permutation graphs is closed under complementation. A graph is a permutation graph if and only if it is isomorphic to GπG_{\pi} for some permutation π\pi. Given a permutation graph, such a permutation can be found in linear time [28]. Permutation graphs were originally introduced by [13] and [29]. A comprehensive overview of their structural and algorithmic properties is provided in [18].

Let α≥1\alpha\ge1. An α\alpha-approximation algorithm is an algorithm which returns a solution which is within a multiplicative factor of α\alpha to an optimal solution.

A Greedy Algorithm

In this section we review the algorithm for CLIQUE PARTITION introduced by Dessmark et al. [10]. The algorithm requires MAX CLIQUE as a subroutine, and therefore does not run in polynomial time for general graphs. However, in every graph class for which MAX CLIQUE can be computed in polynomial time, the algorithm runs in polynomial time. We call the algorithm GREEDY, since it proceeds greedily. The description of GREEDY is as follows. Let GG be a graph and XX a maximum clique of GG. GREEDY adds XX to the clique partition and then recurses on G−XG-X.

Dessmark et al. [10] proved that GREEDY is a 2-approximation algorithm for both CLUSTER DELETION and CLIQUE PARTITION.

Theorem 3.1. For every graph GG, GREEDY returns a clique partition X\mathcal{X} such that $2\lvert E(\mathcal{X})\rvert \ge \operatorname{OPT},whereOPTisthenumberofedgesinanoptimalcliquepartitionof, where OPT is the number of edges in an optimal clique partition ofG.

Theorem 3.2. For every graph GG, GREEDY returns a clique partition X\mathcal{X} such that ∣E(X‾)∣≤2OPT⁡\lvert E(\overline{\mathcal{X}})\rvert\le2\operatorname{OPT}, where OPT is the number of edges in an optimal solution to CLUSTER DELETION, and E(X‾)E(\overline{\mathcal{X}}) are the edges in GG which are not contained in a clique of X\mathcal{X}.

For completeness, we include proofs of both Theorem 3.1 and Theorem 3.2 in Appendix A.

Input: A graph GG. Output: A clique partition X\mathcal{X} of GG.

  1. Set X=∅\mathcal{X} = \varnothing.

  2. While V(G)≠∅V(G) \ne\varnothing: choose a maximum clique XX of GG; set X←X∪{X}\mathcal{X} \leftarrow\mathcal{X} \cup\{X\} and G←G−XG \leftarrow G-X.

  3. Return X\mathcal{X}.

Algorithm 1: GREEDY

Cluster deletion in cographs

In this section, we give a simpler proof that GREEDY computes an optimal clique partition in cographs, which was first proved in [16]. We require the following well-known property of cographs.

Lemma 4.1. Every cograph GG with at least two vertices has a partition (A,B)(A,B) of V(G)V(G) such that either G=G[A]⊔G[B]G = G[A] \sqcup G[B] or G=G[A]∨G[B]G = G[A] \vee G[B].

For a clique partition P\mathcal{P}, let p1≥p2≥⋯p_1 \ge p_2 \ge\cdots be its clique sizes in nonincreasing order, padded by zeros. We say that P\mathcal{P} majorizes a clique partition Q\mathcal{Q}, whose padded size sequence is q1≥q2≥⋯q_1 \ge q_2 \ge\cdots, if

∑i=1jpi≥∑i=1jqifor every j≥1.\sum_{i=1}^{j} p_i \ge\sum_{i=1}^{j} q_i \qquad\text{for every } j \ge1.

Lemma 4.2. If P\mathcal{P} majorizes Q\mathcal{Q}, then ∣E(P)∣≥∣E(Q)∣|E(\mathcal{P})| \ge|E(\mathcal{Q})|.

Proof. Both size sequences have the same sum, namely ∣V(G)∣|V(G)|. The function x↦(x2)x \mapsto\binom{x}{2} is convex on the nonnegative reals, so the majorization inequality (equivalently, Karamata’s inequality [27]) gives

∣E(P)∣=∑i(pi2)≥∑i(qi2)=∣E(Q)∣.|E(\mathcal{P})| = \sum_i \binom{p_i}{2} \ge\sum_i \binom{q_i}{2} = |E(\mathcal{Q})|.

We prove the following statement, which is stronger than optimality.

Theorem 4.3. Let GG be a cograph. Every clique partition of GG output by GREEDY majorizes every clique partition of GG.

Proof. We proceed by induction on ∣V(G)∣|V(G)|. The claim is immediate when ∣V(G)∣≤1|V(G)| \le1. Let X\mathcal{X} be a partition output by GREEDY, and let Y\mathcal{Y} be any clique partition of GG. By Lemma 4.1, there is a nontrivial partition (A,B)(A,B) of V(G)V(G) such that G=G[A]⊔G[B]G = G[A] \sqcup G[B] or G=G[A]∨G[B]G = G[A] \vee G[B].

First suppose that G=G[A]⊔G[B]G = G[A] \sqcup G[B]. Every clique lies wholly in AA or wholly in BB. Moreover, the restriction of the greedy run to each side is clearly a greedy run on that side. Thus, the size sequence of X\mathcal{X} is the nonincreasing merge of greedy size sequences pAp^A and pBp^B for G[A]G[A] and G[B]G[B]. Likewise, the size sequence of Y\mathcal{Y} is the nonincreasing merge of size sequences qAq^A and qBq^B for clique partitions of the two sides. By induction, pAp^A majorizes qAq^A and pBp^B majorizes qBq^B. For each j≥1j \ge1,

∑i=1j∣Yi∣=max⁡r+s=j(∑i=1rqiA+∑i=1sqiB)≤max⁡r+s=j(∑i=1rpiA+∑i=1spiB)=∑i=1j∣Xi∣,\begin{aligned} \sum_{i=1}^{j} |Y_i| = \max_{r+s=j} \left(\sum_{i=1}^{r} q_i^A + \sum_{i=1}^{s} q_i^B\right) \\ &\le\max_{r+s=j} \left(\sum_{i=1}^{r} p_i^A + \sum_{i=1}^{s} p_i^B\right) = \sum_{i=1}^{j} |X_i|, \end{aligned}

where the parts of X\mathcal{X} and Y\mathcal{Y} are ordered by nonincreasing size. Now suppose that G=G[A]∨G[B]G = G[A] \vee G[B]. A maximum clique in every induced subgraph of this join is the union of a maximum clique on each nonempty side. Consequently, there are greedy size sequences pA=(piA)p^A = (p_i^A) and pB=(piB)p^B = (p_i^B) for the two sides, padded by zeros, such that the greedy size sequence for GG is

pi=piA+piB(i≥1).p_i = p_i^A + p_i^B \qquad(i \ge1).

Both component sequences are nonincreasing, so (pi)(p_i) is also nonincreasing. Order the parts Y1,Y2,…Y_1,Y_2,\ldots of Y\mathcal{Y} by nonincreasing size, and put ai=∣Yi∩A∣a_i = |Y_i \cap A| and bi=∣Yi∩B∣b_i = |Y_i \cap B|. The nonempty intersections form clique partitions of G[A]G[A] and G[B]G[B]. If a↓a^\downarrow and b↓b^\downarrow denote the two intersection-size sequences in nonincreasing order, induction gives, for every jj,

∑i=1j∣Yi∣=∑i=1j(ai+bi)≤∑i=1jai↓+∑i=1jbi↓≤∑i=1j(piA+piB)=∑i=1jpi.\begin{aligned} \sum_{i=1}^{j} |Y_i| = \sum_{i=1}^{j}(a_i+b_i) \\ &\le\sum_{i=1}^{j} a_i^\downarrow+ \sum_{i=1}^{j} b_i^\downarrow\\ &\le\sum_{i=1}^{j}(p_i^A+p_i^B) = \sum_{i=1}^{j}p_i. \end{aligned}

Thus, X\mathcal{X} majorizes Y\mathcal{Y} in both cases.

Combining Lemma 4.2 and Theorem 4.3 proves Theorem 1.1.

Remark 4.4. Since the majorization inequality holds for every convex function, Theorem 4.3 gives more than Theorem 1.1. Let ff be a function on the nonnegative integers with f(0)=0f(0)=0 and with f(x+1)−f(x)f(x+1)-f(x) nondecreasing in xx. Extending ff piecewise linearly to [0,∞)[0,\infty) gives a convex function, so Karamata’s inequality applies to integer sequences. Then, for every cograph GG, every clique partition X\mathcal{X} output by GREEDY maximizes ∑X∈Xf(∣X∣)\sum_{X\in\mathcal{X}} f(|X|) over all clique partitions of GG. Taking f(x)=(x2)f(x)=\binom{x}{2} recovers Theorem 1.1. Taking f(x)=−1f(x)=-1 for all x≥1x\ge1 shows that GREEDY also uses the minimum possible number of cliques. That is, it also computes the clique cover number of a cograph.

A clique-partition linear program

The preceding majorization argument actually shows that the natural linear programming relaxation of CLIQUE PARTITION is exact on cographs. Recall that C(G)\mathcal{C}(G) is the family of all nonempty cliques of GG, and that (LP) asks to maximize ∑K∈C(G)(∣K∣2)xK\sum_{K\in\mathcal{C}(G)}\binom{|K|}{2}x_K subject to xK≥0x_K\ge0 and ∑K∋vxK=1\sum_{K\ni v}x_K=1 for every v∈V(G)v\in V(G). If the vertex constraints are instead written as inequalities, their slack can be assigned to singleton cliques without changing the objective. The incidence vector of every clique partition is a feasible solution of (LP), so the optimal value of (LP) is always at least the maximum number of edges in a clique partition of GG. We say that (LP) is exact for GG if equality holds.

The feasible region of (LP) is not integral, even for cographs. Indeed, if G=K3G=K_3 with vertex set {1,2,3}\{1,2,3\}, then

x{1,2}=x{1,3}=x{2,3}=12x_{\{1,2\}}=x_{\{1,3\}}=x_{\{2,3\}}=\frac{1}{2}

and all other variables zero give a fractional feasible solution. The three positive columns form the matrix

(110101011),\begin{pmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1 \end{pmatrix},

whose determinant is −2-2. Thus, this solution is a basic feasible solution. However, we will show that (LP) always has an optimal solution that is {0,1}\{0,1\}-valued when GG is a cograph.

To prove this statement, we extend majorization to fractional clique partitions. A weighted size profile is a finite family

Q={(qα,λα):α∈I},qα≥0,λα≥0.Q=\{(q_\alpha,\lambda_\alpha):\alpha\in I\},\qquad q_\alpha\ge0,\quad\lambda_\alpha\ge0.

Let q↓:[0,∞)→R≥0q^{\downarrow} : [0,\infty) \to\mathbb{R}_{\ge0} be the decreasing step function in which the value qαq_{\alpha} occupies an interval of length λα\lambda_{\alpha}, padded by zeros, and define

LQ(t):=∫0tq↓(s) ds.L_{\mathcal{Q}}(t) := \int_{0}^{t} q^{\downarrow}(s)\,\mathrm{d}s.

Equivalently, LQ(t)L_{\mathcal{Q}}(t) is the maximum total size obtainable by taking total weight tt from Q\mathcal{Q}, allowing a fractional amount of an entry.

Every feasible solution xx of (LP) has the weighted size profile

Qx:={(∣K∣,xK):K∈C(G)}.\mathcal{Q}_{x} := \{(|K|,x_{K}) : K \in\mathcal{C}(G)\}.

The covering constraints imply

∑K∈C(G)∣K∣xK=∑v∈V(G)∑K∈C(G)v∈KxK=∣V(G)∣.(2)\sum_{K\in\mathcal{C}(G)} |K|x_{K} = \sum_{v\in V(G)}\sum_{\substack{K\in\mathcal{C}(G)\\v\in K}}x_{K} = |V(G)|. \tag*{(2)}

Lemma 4.5. Let GG be a cograph, let P\mathcal{P} be a clique partition output by GREEDY, and let p1≥p2≥⋯p_{1} \ge p_{2} \ge\cdots be its clique sizes, padded by zeros. For every feasible solution xx of (LP) and every t≥0t \ge0,

LQx(t)≤∫0tp↓(s) ds,L_{\mathcal{Q}_{x}}(t) \le\int_{0}^{t} p^{\downarrow}(s)\,\mathrm{d}s,

where p↓p^{\downarrow} is the step function that takes the value pip_{i} on the interval [i−1,i)[i-1,i).

Proof. We proceed by induction on ∣V(G)∣|V(G)|. The claim is immediate when ∣V(G)∣≤1|V(G)| \le1. Choose a nontrivial cograph decomposition (A,B)(A,B) as in Lemma 4.1.

First suppose that G=G[A]∪˙G[B]G = G[A] \mathbin{\dot\cup} G[B]. Every clique is contained in one side, so Qx\mathcal{Q}_{x} is the union of feasible fractional profiles QA\mathcal{Q}_{A} and QB\mathcal{Q}_{B} for the two sides. The restriction of the greedy run to each side is a greedy run; denote its profiles by pAp^{A} and pBp^{B}. By induction, for every t≥0t \ge0,

LQx(t)=max⁡r,s≥0r+s=t(LQA(r)+LQB(s))≤max⁡r,s≥0r+s=t(LpA(r)+LpB(s))=Lp(t),\begin{aligned} L_{\mathcal{Q}_{x}}(t) &= \max_{\substack{r,s\ge0\\r+s=t}}\left(L_{\mathcal{Q}_{A}}(r)+L_{\mathcal{Q}_{B}}(s)\right)\\ &\le\max_{\substack{r,s\ge0\\r+s=t}}\left(L_{p^{A}}(r)+L_{p^{B}}(s)\right) = L_{p}(t), \end{aligned}

where pp is the nonincreasing merge of pAp^{A} and pBp^{B}.

Now suppose that G=G[A]∨G[B]G = G[A] \vee G[B]. For every clique KK of GG, put KA=K∩AK_{A}=K\cap A and KB=K∩BK_{B}=K\cap B. Using weight xKx_{K} on the entries ∣KA∣|K_{A}| and ∣KB∣|K_{B}| gives feasible fractional profiles QA\mathcal{Q}_{A} and QB\mathcal{Q}_{B} on the two sides; zero entries may simply be retained. For any choice of total weight tt, the contribution of the entries ∣KA∣+∣KB∣|K_{A}|+|K_{B}| is at most the sum of the tt largest entries from the two component profiles. Hence,

LQx(t)≤LQA(t)+LQB(t).L_{\mathcal{Q}_{x}}(t) \le L_{\mathcal{Q}_{A}}(t)+L_{\mathcal{Q}_{B}}(t).

There are greedy profiles pAp^{A} and pBp^{B}, padded by zeros, such that the greedy profile of the join satisfies

pi=piA+piB(i≥1).p_{i}=p_{i}^{A}+p_{i}^{B}\qquad(i\ge1).

Since both component profiles are nonincreasing, induction gives

LQx(t)≤LpA(t)+LpB(t)=Lp(t).L_{\mathcal{Q}_{x}}(t) \le L_{p^{A}}(t)+L_{p^{B}}(t)=L_{p}(t).

This completes the induction.

We are now ready to prove Theorem 1.2.

Proof of Theorem 1.2. Let xx be any feasible solution, and let P\mathcal{P} be a clique partition output by GREEDY, with size sequence p1≥p2≥⋯p_1 \ge p_2 \ge\cdots. By Equation (2) and Lemma 4.5, the profile pp majorizes the weighted profile QxQ_x, and both profiles have total size ∣V(G)∣|V(G)|. The weighted form of Karamata’s inequality (see [27]), applied to the convex function f(z)=(z2)f(z)=\binom{z}{2}, therefore gives

∑K∈C(G)xK(∣K∣2)≤∑i(pi2)=∣E(P)∣.\sum_{K\in\mathcal{C}(G)}x_K\binom{|K|}{2}\le\sum_i\binom{p_i}{2}=|E(\mathcal{P})|.

The incidence vector of P\mathcal{P} is a feasible integral solution of (LP). It is therefore at least as good as every fractional solution, and hence is optimal.

We conclude this section by showing that Theorem 1.2 does not extend to permutation graphs. We used Claude Fable 5.1 to find this example, and to verify by exhaustive computer search that it is the smallest such example.

Proposition 4.6. Let π=[5,9,8,7,3,6,2,1,4]\pi=[5,9,8,7,3,6,2,1,4] and let G=GπG=G_\pi be the corresponding permutation graph, depicted in Figure 1. Then the optimal value of (LP) for GG is 33/233/2, whereas every clique partition of GG has at most 16 edges.

The permutation graph $G$

Figure 1. The permutation graph GG of [5,9,8,7,3,6,2,1,4][5,9,8,7,3,6,2,1,4], for which (LP) is not exact.

Proof. Recall that the cliques of G=GπG=G_\pi are the decreasing subsequences of π\pi. One checks directly that the maximal cliques of GG are

{1,2,3,7,8,9},{1,2,6,7,8,9},{1,2,3,5},{4,6,7,8,9},{4,5},\{1,2,3,7,8,9\},\quad\{1,2,6,7,8,9\},\quad\{1,2,3,5\},\quad\{4,6,7,8,9\},\quad\{4,5\},

and that GG has 28 edges. Equivalently, GG is obtained from the complete graph on {1,2,3,6,7,8,9}\{1,2,3,6,7,8,9\} by deleting the edge {3,6}\{3,6\} and adding two vertices 4 and 5, where 5 is adjacent to 1, 2, 3, 4 and 4 is adjacent to 5, 6, 7, 8, 9. In particular, ω(G)=6\omega(G)=6, and the only 6-cliques are the first two sets above.

Assign xK=1/2x_K=1/2 to each of the five cliques

{1,2,3,7,8,9},{1,2,6,7,8,9},{3,5},{4,5},{4,6},\{1,2,3,7,8,9\},\quad\{1,2,6,7,8,9\},\quad\{3,5\},\quad\{4,5\},\quad\{4,6\},

and xK=0x_K=0 to all other cliques. Every vertex is covered exactly once, so xx is feasible for (LP), and its objective value is 12(15+15+1+1+1)=33/2\frac{1}{2}(15+15+1+1+1)=33/2. On the other hand, the dual of (LP) asks to minimize ∑v∈V(G)yv\sum_{v\in V(G)}y_v subject to

∑v∈Kyv≥(∣K∣2)\sum_{v\in K}y_v\ge\binom{|K|}{2}

for every K∈C(G)K\in\mathcal{C}(G). The vector yy with

y1=3,y2=2,y3=y4=y5=y6=12,y7=92,y8=2,y9=3y_1=3,\quad y_2=2,\quad y_3=y_4=y_5=y_6=\frac{1}{2},\quad y_7=\frac{9}{2},\quad y_8=2,\quad y_9=3

is dual feasible. Indeed, every clique of GG is contained in one of the five maximal cliques QQ listed above, so it suffices to check that for each such QQ and each k≤∣Q∣k\le|Q|, the sum of the kk smallest values yvy_v (v∈Qv\in Q) is at least (k2)\binom{k}{2}. For Q={1,2,3,7,8,9}Q=\{1,2,3,7,8,9\} and Q={1,2,6,7,8,9}Q=\{1,2,6,7,8,9\}, the values yvy_v in nondecreasing order are $1/2,2,2,3,3,9/2$, with partial sums 1/2,5/2,9/2,15/2,21/2,151/2,5/2,9/2,15/2,21/2,15; for Q={4,6,7,8,9}Q=\{4,6,7,8,9\} they are 1/2,1/2,2,3,9/21/2,1/2,2,3,9/2, with partial sums 1/2,1,3,6,21/21/2,1,3,6,21/2; for $Q={1,2,3,5} they are 12,12,2,3\frac{1}{2}, \frac{1}{2}, 2, 3, with partial sums 12,1,3,6\frac{1}{2}, 1, 3, 6; and for Q={4,5}Q=\{4,5\} the partial sums are 12,1\frac{1}{2},1. In each case the kk-th partial sum is at least (k2)\binom{k}{2}. Since ∑vyv=33/2\sum_v y_v=33/2, linear programming duality shows that the optimal value of (LP) is exactly 33/233/2.

Finally, let X\mathcal{X} be a clique partition of GG with part sizes s1≥s2≥⋯s_1\ge s_2\ge\cdots. Since ∑jsj=9\sum_j s_j=9 and s1≤6s_1\le6, a direct enumeration of the partitions of 9 into parts of size at most 6 shows that ∑j(sj2)≥17\sum_j\binom{s_j}{2}\ge17 forces (s1,s2)=(6,3)(s_1,s_2)=(6,3), that is, X\mathcal{X} consists of a 6-clique and a disjoint triangle. However, V(G)∖{1,2,3,7,8,9}={4,5,6}V(G)\setminus\{1,2,3,7,8,9\}=\{4,5,6\} and V(G)∖{1,2,6,7,8,9}={3,4,5}V(G)\setminus\{1,2,6,7,8,9\}=\{3,4,5\} are not cliques. Hence ∣E(X)∣≤16|E(\mathcal{X})|\le16, and the clique partition {{1,2,3,7,8,9},{4,6},{5}}\{\{1,2,3,7,8,9\},\{4,6\},\{5\}\} shows that this bound is attained.

By Theorem 1.3 below, the failure of exactness on permutation graphs is not an accident. The dual of (LP) can be solved in polynomial time on permutation graphs as follows. Since the cliques of GπG_\pi of size qq are the decreasing subsequences of π\pi of length qq, a minimum yy-weight clique of each size q∈[n]q\in[n] can be found by dynamic programming, which yields a polynomial-time separation oracle. Thus, (LP) can be solved in polynomial time via the ellipsoid method [20]. Consequently, if (LP) were exact for all permutation graphs, then the optimal value of CLIQUE PARTITION on permutation graphs could be computed in polynomial time, which by Theorem 1.3 is impossible unless P=NP\mathsf{P}=\mathsf{NP}.

Cluster deletion in permutation graphs is NP-complete

In this section, we prove Theorem 1.3, which resolves an open problem of Konstantinidis and Papadopoulos [25]. As explained in the introduction, the decision versions of CLIQUE PARTITION and CLUSTER DELETION are equivalent and belong to NP\mathsf{NP}, so it suffices to show that CLIQUE PARTITION is NP-hard on permutation graphs.

We give a polynomial reduction from the OPTIMUM COST CHROMATIC PARTITION (OCCP) problem.

OPTIMUM COST CHROMATIC PARTITION:

Input: A graph HH with nn vertices and nonnegative integers k1≤k2≤⋯≤knk_1\le k_2\le\cdots\le k_n.

Output: A partition S=(S1,…,Sn)\mathcal{S}=(S_1,\ldots,S_n) of V(H)V(H) into stable sets of HH (some of which may be empty) such that cost⁡(S):=∑i=1nki∣Si∣\operatorname{cost}(\mathcal{S}):=\sum_{i=1}^{n} k_i|S_i| is minimum.

In other words, color ii has cost kik_i, and OCCP asks for a proper coloring of HH of minimum total cost; since HH has only nn vertices, allowing nn colors is not a restriction. We call a partition of V(H)V(H) into nn stable sets a coloring of HH. In the decision version of OCCP, we are additionally given an integer cc, and the question is whether HH has a coloring of cost at most cc. Jansen [23] proved that OCCP is NP-complete on permutation graphs. Moreover, in the instances constructed in his hardness proof, the costs kik_i are bounded by a polynomial in nn (see [23 Section 4]). We only use this restricted form of Jansen’s result.

Theorem 5.1 (Jansen [23]). There is a constant dd such that the decision version of OCCP is NP-hard when restricted to instances (H,(k1,…,kn),c)(H,(k_1,\ldots,k_n),c) in which HH is a permutation graph and kn≤ndk_n\le n^d.

Scores

It is convenient to measure clique partitions by a slightly different quantity than the number of edges. For a clique partition K=(K1,…,Km)\mathcal{K}=(K_1,\ldots,K_m) of a graph GG, we define the score of K\mathcal{K} to be

sc⁡(K):=∑j=1m∣Kj∣2.\operatorname{sc}(\mathcal{K}):=\sum_{j=1}^{m}|K_j|^2.

Since ∑j=1m∣Kj∣=∣V(G)∣\sum_{j=1}^{m}|K_j|=|V(G)|, we have

∣E(K)∣=∑j=1m(∣Kj∣2)=sc⁡(K)−∣V(G)∣2.(3)|E(\mathcal{K})|=\sum_{j=1}^{m}\binom{|K_j|}{2}=\frac{\operatorname{sc}(\mathcal{K})-|V(G)|}{2}. \tag*{(3)}

Thus, maximizing ∣E(K)∣|E(\mathcal{K})| is the same as maximizing sc⁡(K)\operatorname{sc}(\mathcal{K}), and for every integer tt, GG has a clique partition with at least tt edges if and only if GG has a clique partition of score at least 2t+∣V(G)∣2t+|V(G)|.

The construction

Fix an instance (H,(k1,…,kn),c)(H,(k_1,\ldots,k_n),c) of OCCP, where HH is a graph with vertex set V(H)V(H) of size nn, and k1≤⋯≤knk_1 \le\cdots\le k_n are nonnegative integers. Put

S:=∑i=1nki,M:=n2+1,ai:=1+M(S−ki)(i∈[n]).S := \sum_{i=1}^{n} k_i,\qquad M := n^2+1,\qquad a_i := 1+M(S-k_i)\quad(i\in[n]).

Note that a1≥a2≥⋯≥an≥1a_1 \ge a_2 \ge\cdots\ge a_n \ge1. Let A1,…,AnA_1,\ldots,A_n be pairwise disjoint sets of vertices, disjoint from V(H)V(H), with ∣Ai∣=ai|A_i|=a_i for all i∈[n]i\in[n], and let

G:=H‾∨(K[A1]⊔K[A2]⊔⋯⊔K[An]).G := \overline{H}\vee\bigl(K[A_1]\sqcup K[A_2]\sqcup\cdots\sqcup K[A_n]\bigr).

where K[Ai]K[A_i] denotes the complete graph with vertex set AiA_i. Explicitly, V(G)=V(H)∪A1∪⋯∪AnV(G)=V(H)\cup A_1\cup\cdots\cup A_n; two vertices of HH are adjacent in GG if and only if they are nonadjacent in HH; every vertex of HH is adjacent to every vertex of A1∪⋯∪AnA_1\cup\cdots\cup A_n; each AiA_i is a clique of GG; and there are no edges between AiA_i and AjA_j for i≠ji\ne j. Finally, put

C:=∑i=1nai2+2n+2MSnandT:=C−2Mc.(4)C := \sum_{i=1}^{n} a_i^2+2n+2MSn\qquad\text{and}\qquad T := C-2Mc. \tag*{(4)}

We record two simple observations. First, since there are no edges between distinct sets AiA_i and AjA_j, and since the cliques of H‾\overline{H} are the stable sets of HH, we have the following description of the cliques of GG.

Fact 5.2. The cliques of GG are exactly the sets of the form B∪QB\cup Q, where B⊆AiB\subseteq A_i for some i∈[n]i\in[n] and QQ is a stable set of HH. In particular, no clique of GG meets two of the sets A1,…,AnA_1,\ldots,A_n.

Second, ∣V(G)∣=n+∑i=1nai≤n+n(1+MS)=O(n3S)|V(G)|=n+\sum_{i=1}^{n}a_i\le n+n(1+MS)=O(n^3S). Hence, if kn≤ndk_n\le n^d, then S≤nd+1S\le n^{d+1} and ∣V(G)∣=O(nd+4)|V(G)|=O(n^{d+4}), so GG can be constructed in time polynomial in nn.

For a coloring S=(S1,…,Sn)\mathcal{S}=(S_1,\ldots,S_n) of HH, we define

KS:=(A1∪S1,…,An∪Sn).\mathcal{K}_{\mathcal{S}} := (A_1\cup S_1,\ldots,A_n\cup S_n).

Lemma 5.3. For every coloring S=(S1,…,Sn)\mathcal{S}=(S_1,\ldots,S_n) of HH, KS\mathcal{K}_{\mathcal{S}} is a clique partition of GG, and

sc⁡(KS)=C+∑i=1n∣Si∣2−2M⋅cost⁡(S).\operatorname{sc}(\mathcal{K}_{\mathcal{S}})=C+\sum_{i=1}^{n}|S_i|^2-2M\cdot\operatorname{cost}(\mathcal{S}).

Proof. Each Ai∪SiA_i\cup S_i is a clique of GG by Fact 5.2, and these sets partition V(G)V(G). Using ∑i=1n∣Si∣=n\sum_{i=1}^{n}|S_i|=n, we compute

sc⁡(KS)=∑i=1n(ai+∣Si∣)2=∑i=1nai2+∑i=1n∣Si∣2+2∑i=1nai∣Si∣=∑i=1nai2+∑i=1n∣Si∣2+2∑i=1n(1+M(S−ki))∣Si∣=∑i=1nai2+∑i=1n∣Si∣2+2n+2MSn−2M∑i=1nki∣Si∣=C+∑i=1n∣Si∣2−2M⋅cost⁡(S).\begin{aligned} \operatorname{sc}(\mathcal{K}_{\mathcal{S}}) &=\sum_{i=1}^{n}(a_i+|S_i|)^2 =\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}|S_i|^2+2\sum_{i=1}^{n}a_i|S_i|\\ &=\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}|S_i|^2+2\sum_{i=1}^{n}\bigl(1+M(S-k_i)\bigr)|S_i|\\ &=\sum_{i=1}^{n}a_i^2+\sum_{i=1}^{n}|S_i|^2+2n+2MSn-2M\sum_{i=1}^{n}k_i|S_i|\\ &=C+\sum_{i=1}^{n}|S_i|^2-2M\cdot\operatorname{cost}(\mathcal{S}). \end{aligned}

The next lemma shows that, as far as maximum scores are concerned, we may restrict our attention to clique partitions of the form KS\mathcal{K}_{\mathcal{S}}.

Lemma 5.4. Let K\mathcal{K} be a clique partition of GG of maximum score. Then K=KS\mathcal{K}=\mathcal{K}_{\mathcal{S}} for some coloring S\mathcal{S} of HH. Consequently, for every clique partition K′\mathcal{K}' of GG there is a coloring S\mathcal{S} of HH with sc⁡(KS)≥sc⁡(K′)\operatorname{sc}(\mathcal{K}_{\mathcal{S}})\ge\operatorname{sc}(\mathcal{K}').

Proof. We first show that each AiA_i is contained in a single part of K\mathcal{K}. Suppose not, and let KK and K′K' be distinct parts of K\mathcal{K} that both meet AiA_i. By Fact 5.2, K=B∪QK=B\cup Q and K′=B′∪Q′K'=B'\cup Q', where BB and B′B' are disjoint nonempty subsets of AiA_i, and Q,Q′⊆V(H)Q,Q'\subseteq V(H) are stable sets of HH. By symmetry, we may assume that ∣Q∣≥∣Q′∣|Q|\ge|Q'|. Let K∗\mathcal{K}^* be obtained from K\mathcal{K} by replacing KK and K′K' by K∪B′=B∪B′∪QK\cup B'=B\cup B'\cup Q and K′∖B′=Q′K'\setminus B'=Q' (and discarding Q′Q' if it is empty). By Fact 5.2, K∪B′K\cup B' is a clique of GG, so K∗\mathcal{K}^* is a clique partition of GG, and

sc⁡(K∗)−sc⁡(K)=(∣B∣+∣B′∣+∣Q∣)2+∣Q′∣2−(∣B∣+∣Q∣)2−(∣B′∣+∣Q′∣)2=2∣B′∣(∣B∣+∣Q∣−∣Q′∣)>0.\begin{aligned} \operatorname{sc}(\mathcal{K}^*)-\operatorname{sc}(\mathcal{K})=(|B|+|B'|+|Q|)^2+|Q'|^2-(|B|+|Q|)^2-(|B'|+|Q'|)^2 \\ &=2|B'|(|B|+|Q|-|Q'|)>0. \end{aligned}

since ∣B′∣≥1|B'|\ge1, ∣B∣≥1|B|\ge1 and ∣Q∣≥∣Q′∣|Q|\ge|Q'|. This contradicts the maximality of sc⁡(K)\operatorname{sc}(\mathcal{K}).

Hence, for each i∈[n]i\in[n] there is a unique part KiK_i of K\mathcal{K} containing AiA_i, and by Fact 5.2 we can write Ki=Ai∪SiK_i=A_i\cup S_i with Si⊆V(H)S_i\subseteq V(H) a stable set of HH. The parts K1,…,KnK_1,\ldots,K_n are distinct, since by Fact 5.2 no clique of GG meets two of the sets AiA_i, and every other part of K\mathcal{K} is a nonempty subset of V(H)V(H). Suppose that there is such a part K0⊆V(H)K_0\subseteq V(H). Then ∑i=1n∣Si∣≤n−∣K0∣<n\sum_{i=1}^n|S_i|\le n-|K_0|<n, so Si=∅S_i=\varnothing for some i∈[n]i\in[n], that is, Ki=AiK_i=A_i. By Fact 5.2, Ai∪K0A_i\cup K_0 is a clique of GG, and replacing the two parts KiK_i and K0K_0 by the single part Ai∪K0A_i\cup K_0 increases the score by (ai+∣K0∣)2−ai2−∣K0∣2=2ai∣K0∣>0(a_i+|K_0|)^2-a_i^2-|K_0|^2=2a_i|K_0|>0, again contradicting the maximality of sc⁡(K)\operatorname{sc}(\mathcal{K}).

Therefore, K=(A1∪S1,…,An∪Sn)=KS\mathcal{K}=(A_1\cup S_1,\ldots,A_n\cup S_n)=\mathcal{K}_{\mathcal{S}}, where S=(S1,…,Sn)\mathcal{S}=(S_1,\ldots,S_n) is a coloring of HH. The last assertion follows since a clique partition of maximum score exists.

We are now ready to establish the correctness of the reduction.

Theorem 5.5. HH has a coloring of cost at most cc if and only if GG has a clique partition of score at least TT.

Proof. Suppose first that S=(S1,…,Sn)\mathcal{S}=(S_1,\ldots,S_n) is a coloring of HH with cost⁡(S)≤c\operatorname{cost}(\mathcal{S})\le c. By Lemma 5.3,

sc⁡(KS)=C+∑i=1n∣Si∣2−2M⋅cost⁡(S)≥C−2Mc=T.\operatorname{sc}(\mathcal{K}_{\mathcal{S}})=C+\sum_{i=1}^{n}|S_i|^2-2M\cdot\operatorname{cost}(\mathcal{S})\ge C-2Mc=T.

Conversely, suppose that GG has a clique partition of score at least TT. By Lemma 5.4, there is a coloring S=(S1,…,Sn)\mathcal{S}=(S_1,\ldots,S_n) of HH with sc⁡(KS)≥T\operatorname{sc}(\mathcal{K}_{\mathcal{S}})\ge T. By Lemma 5.3,

2M(cost⁡(S)−c)≤∑i=1n∣Si∣2≤(∑i=1n∣Si∣)2=n2<2M.2M(\operatorname{cost}(\mathcal{S})-c)\le\sum_{i=1}^{n}|S_i|^2\le\left(\sum_{i=1}^{n}|S_i|\right)^2=n^2<2M.

Since cost⁡(S)\operatorname{cost}(\mathcal{S}) and cc are integers, it follows that cost⁡(S)≤c\operatorname{cost}(\mathcal{S})\le c.

The same computation shows that the reduction maps optimal solutions to optimal solutions. Indeed, let K\mathcal{K} be a clique partition of GG of maximum score. By Lemma 5.4, K=KS\mathcal{K}=\mathcal{K}_{\mathcal{S}} for some coloring S\mathcal{S} of HH, and if some coloring S′\mathcal{S}' of HH had cost⁡(S′)<cost⁡(S)\operatorname{cost}(\mathcal{S}')<\operatorname{cost}(\mathcal{S}), then Lemma 5.3 would give sc⁡(KS′)−sc⁡(KS)≥2M−n2>0\operatorname{sc}(\mathcal{K}_{\mathcal{S}'})-\operatorname{sc}(\mathcal{K}_{\mathcal{S}})\ge2M-n^2>0, a contradiction. Thus, S\mathcal{S} is a minimum cost coloring of HH (in fact, one maximizing ∑i=1n∣Si∣2\sum_{i=1}^{n}|S_i|^2 among all minimum cost colorings).

Preserving permutation graphs

It remains to show that the reduction preserves the property of being a permutation graph. This also follows from the facts that the class of permutation graphs is closed under complementation, disjoint unions and joins (see [18]), but we give an explicit permutation.

Lemma 5.6. If HH is a permutation graph, then so is GG. Moreover, given a permutation π\pi with H≅GπH\cong G_\pi, a permutation σ\sigma with G≅GσG\cong G_\sigma can be computed in time polynomial in ∣V(G)∣|V(G)|.

Proof. We may assume that V(H)=[n]V(H)=[n] and H=GπH=G_\pi for a permutation π=[π1,…,πn]\pi=[\pi_1,\ldots,\pi_n] of [n][n]. Put N:=∑i=1naiN:=\sum_{i=1}^{n}a_i and ni:=a1+⋯+ain_i:=a_1+\cdots+a_i for i∈{0,1,…,n}i\in\{0,1,\ldots,n\}, so that n0=0n_0=0 and nn=Nn_n=N. Let σ\sigma be the following permutation of [N+n][N+n],

written as a word:

σ:=[πn+N, πn−1+N, …, π1+N,n1, n1−1, …, n0+1,n2, n2−1, …, n1+1,⋮nn, nn−1, …, nn−1+1].\sigma:= [\pi_n+N,\ \pi_{n-1}+N,\ \ldots,\ \pi_1+N,\quad n_1,\ n_1-1,\ \ldots,\ n_0+1,\quad n_2,\ n_2-1,\ \ldots,\ n_1+1,\quad \vdots\quad n_n,\ n_n-1,\ \ldots,\ n_{n-1}+1].

That is, σ\sigma begins with the reverse of π\pi with all values shifted by NN, followed by nn decreasing runs, the ii-th of which consists of the values in (ni−1,ni](n_{i-1},n_i]. We identify the vertex v∈V(H)v \in V(H) with the value v+Nv+N, and the set AiA_i with the set of values in (ni−1,ni](n_{i-1},n_i], and claim that under this identification Gσ=GG_\sigma=G. Recall that two values are adjacent in GσG_\sigma if and only if the smaller value appears later in the word σ\sigma.

  • Let u<vu<v be vertices of HH. Then u+Nu+N appears later than v+Nv+N in σ\sigma if and only if uu appears earlier than vv in π\pi, that is, if and only if uu and vv are nonadjacent in H=GπH=G_\pi. Hence Gσ[V(H)]=H‾G_\sigma[V(H)]=\overline{H}.

  • Let u∈V(H)u\in V(H) and x∈Aix\in A_i. Then x<u+Nx<u+N and xx appears later than u+Nu+N in σ\sigma, so xx and uu are adjacent in GσG_\sigma.

  • Let x<yx<y be values in A1∪⋯∪AnA_1\cup\cdots\cup A_n. If x,y∈Aix,y\in A_i for some ii, then xx appears later than yy (the ii-th run is decreasing), so xx and yy are adjacent. If x∈Aix\in A_i and y∈Ajy\in A_j with i≠ji\ne j, then i<ji<j, and xx appears earlier than yy, so xx and yy are nonadjacent.

Therefore, Gσ=GG_\sigma=G. Clearly, σ\sigma can be written down in time polynomial in N+n=∣V(G)∣N+n=|V(G)|.

We can now complete the proof of Theorem 1.3.

Proof of Theorem 1.3. As noted above, the decision versions of CLIQUE PARTITION and CLUSTER DELETION are in NP and are polynomially equivalent, so it suffices to show that CLIQUE PARTITION is NP-hard on permutation graphs. Let (H,(k1,…,kn),c)(H,(k_1,\ldots,k_n),c) be an instance of OCCP with HH a permutation graph and kn≤ndk_n\le n^d, where dd is the constant from Theorem 5.1. Construct the graph GG and the integer TT as in (4), and put t:=⌈(T−∣V(G)∣)/2⌉t:=\lceil(T-|V(G)|)/2\rceil. A permutation π\pi with H≅GπH\cong G_\pi can be found in linear time [28], so since ∣V(G)∣=O(nd+4)|V(G)|=O(n^{d+4}), Lemma 5.6 shows that the permutation graph GG (together with a permutation σ\sigma representing it) can be computed in polynomial time. By Theorem 5.5 and (3), HH has a coloring of cost at most cc if and only if GG has a clique partition with at least tt edges. By Theorem 5.1, CLIQUE PARTITION is NP-hard on permutation graphs.

Since the permutation graphs are precisely the graphs that are simultaneously comparability graphs and cocomparability graphs (see [18]), Theorem 1.3 immediately yields hardness for these two well-studied superclasses. Note that both classes contain natural subclasses on which CLUSTER DELETION is polynomial-time solvable. Bipartite graphs are comparability graphs (and on triangle-free graphs CLUSTER DELETION is just a maximum matching problem), while interval graphs are cocomparability graphs, and CLUSTER DELETION is polynomial-time solvable on interval graphs [6, 25].

Corollary 5.7. CLUSTER DELETION and CLIQUE PARTITION are NP-complete on comparability graphs and on cocomparability graphs.

An improved approximation algorithm

In this section we present an improved approximation algorithm for CLIQUE PARTITION. The description of the algorithm is simple. While the current graph has clique number at least 3, we compute a maximum clique XX, put XX into the clique partition, and delete XX. Once the remaining graph has clique number at most 2, an optimal clique partition consists of a maximum matching together with singleton cliques. We call the algorithm GREEDY EDMONDS.

Let GG be a graph, V\mathcal{V} be a clique partition of GG, and C⊆V(G)\mathcal{C}\subseteq V(G). We let V−C\mathcal{V}-\mathcal{C} be the collection of nonempty sets of the form Y∖CY\setminus C, where Y∈VY\in\mathcal{V}. Note that V−C\mathcal{V}-\mathcal{C} is a clique partition of G−CG-C. Recall that ω′(G)\omega'(G) is the number of edges in a maximum clique of GG.

We now show that GREEDY EDMONDS is a 2ω′(G)ω′(G)+1\frac{2\omega'(G)}{\omega'(G)+1}-approximation algorithm for every graph GG. We first require the following lemma.

Input: A graph GG.

Output: A clique partition X\mathcal{X} of GG.

  1. Set X=∅\mathcal{X} = \varnothing.

  2. While ω(G)≥3\omega(G) \ge3: choose a maximum clique XX of GG; set X←X∪{X}\mathcal{X} \gets\mathcal{X} \cup\{X\} and G←G−XG \gets G - X.

  3. Compute a maximum matching M\mathcal{M} of GG.

  4. Add the edges of M\mathcal{M} as two-vertex cliques and all uncovered vertices as singleton cliques.

  5. Return X\mathcal{X}.

Algorithm 2: GREEDY EDMONDS

Lemma 6.1. Let GG be a graph, Y\mathcal{Y} be a clique partition of GG, λ(k):=min⁡{∣E(Y−X)∣:X⊆V(G), ∣X∣=k}\lambda(k) := \min\{|E(\mathcal{Y} - X)| : X \subseteq V(G),\ |X| = k\}, and CC be a subset of V(G)V(G) of size kk. If ∣E(Y−C)∣=λ(k)|E(\mathcal{Y} - C)| = \lambda(k), then there exists an ordering c1,…,ckc_1,\ldots,c_k of CC such that cic_i lies in a largest part of Y−{c1,…,ci−1}\mathcal{Y} - \{c_1,\ldots,c_{i-1}\} for all i∈[k]i \in[k].

Proof. We proceed by induction on kk. The assertion is immediate for k=1k = 1. Suppose k≥2k \ge2, and let CC attain λ(k)\lambda(k). We first show that CC contains a vertex in a largest part of Y\mathcal{Y}. If it does not, choose x∈Cx \in C and choose yy in a largest part of Y\mathcal{Y}. Put D=C∖{x}D = C \setminus\{x\} and C′=D∪{y}C' = D \cup\{y\}. In the partition Y−D\mathcal{Y} - D, the part containing yy has its original maximum size, say qq, whereas the part containing xx has size at most q−1q - 1. Deleting a vertex from a part of size ss removes exactly s−1s - 1 retained edges. Therefore,

∣E(Y−C′)∣<∣E(Y−C)∣.|E(\mathcal{Y} - C')| < |E(\mathcal{Y} - C)|.

contrary to the choice of CC.

Choose such a vertex c1∈Cc_1 \in C, put C1=C∖{c1}C_1 = C \setminus\{c_1\}, and let Y1=Y−{c1}\mathcal{Y}_1 = \mathcal{Y} - \{c_1\}. The set C1C_1 minimizes ∣E(Y1−D)∣|E(\mathcal{Y}_1 - D)| among all (k−1)(k - 1)-subsets D⊆V(G)∖{c1}D \subseteq V(G) \setminus\{c_1\}; otherwise, adjoining c1c_1 to a better set DD would contradict the minimality of CC. The induction hypothesis applied to (Y1,C1)(\mathcal{Y}_1, C_1) gives an ordering c2,…,ckc_2,\ldots,c_k with the required property. Prepending c1c_1 completes the proof.

Theorem 6.2. For every graph GG, GREEDY EDMONDS returns a clique partition X\mathcal{X} such that

OPT≤2ω′(G)ω′(G)+1∣E(X)∣,\mathrm{OPT} \le\frac{2\omega'(G)}{\omega'(G) + 1}|E(\mathcal{X})|,

where OPT\mathrm{OPT} is the number of edges in an optimal clique partition of GG.

Proof. We proceed by induction on ∣V(G)∣|V(G)|. Put

bj:=(j2)b_j := \binom{j}{2}

and

γj:=bj+12bj(j≥2).\gamma_j := \frac{b_j + 1}{2b_j} \qquad(j \ge2).

Let ℓ=ω(G)\ell= \omega(G). If ℓ≤2\ell\le2, then GREEDY EDMONDS is optimal, so assume ℓ≥3\ell\ge3. Let X\mathcal{X} be the partition returned by GREEDY EDMONDS, let Y\mathcal{Y} be an optimal clique partition, and let xix_i and yiy_i be the numbers of parts of size ii in X\mathcal{X} and Y\mathcal{Y}, respectively.

All xℓx_\ell cliques of size ℓ\ell chosen by the algorithm occur before any smaller chosen clique. Let AA be their union, put a=∣A∣=ℓxℓa = |A| = \ell x_\ell, and set

G′=G−A,X′=X−A,Y′=Y−A.G' = G - A,\qquad\mathcal{X}' = \mathcal{X} - A,\qquad\mathcal{Y}' = \mathcal{Y} - A.

Then ω(G′)≤ℓ−1\omega(G') \le\ell- 1, and X′\mathcal{X}' is an output of GREEDY EDMONDS on G′G'. The induction hypothesis, together with the fact that γj\gamma_j decreases with jj, gives

∣E(X′)∣≥γℓ−1∣E(Y′)∣.(5)|E(\mathcal{X}')| \ge\gamma_{\ell-1}|E(\mathcal{Y}')|. \tag*{(5)}

For ℓ=3\ell= 3 this uses γ2=1\gamma_2 = 1, since G′G' has clique number at most 2 and the algorithm is optimal.

Choose an aa-element set C⊆V(G)C \subseteq V(G) minimizing ∣E(Y−C)∣|E(\mathcal{Y}-C)|. Since AA is also an aa-element set,

∣E(Y′)∣≥∣E(Y−C)∣.|E(\mathcal{Y}')| \ge|E(\mathcal{Y}-C)|.

The set AA meets every part of Y\mathcal{Y} of size ℓ\ell; otherwise that part would be an ℓ\ell-clique in G′G'. In particular, a≥yℓa \ge y_{\ell}. By Lemma 6.1, the vertices of CC can be removed successively from a currently largest part of Y\mathcal{Y}. The first yℓy_{\ell} removals therefore meet distinct parts of size ℓ\ell, and no part of size ℓ\ell remains in Y−C\mathcal{Y}-C.

If C=V(G)C=V(G), then

∣E(Y)∣=∑i=1ℓbiyi≤ℓ−12∑i=1ℓiyi=ℓ−12a=bℓxℓ≤∣E(X)∣,\begin{aligned} |E(\mathcal{Y})|=\sum_{i=1}^{\ell}b_i y_i \\ &\le\frac{\ell-1}{2}\sum_{i=1}^{\ell}i y_i \\ &=\frac{\ell-1}{2}a=b_{\ell}x_{\ell}\le|E(\mathcal{X})|, \end{aligned}

and we are done. We may therefore let kk be the largest size of a part in the nonempty partition Y−C\mathcal{Y}-C. Then 1≤k≤ℓ−11\le k\le\ell-1.

The greedy deletion order supplied by Lemma 6.1 first reduces every original part of size greater than kk to size kk. This uses

s:=∑i=kℓ(i−k)yi.s:=\sum_{i=k}^{\ell}(i-k)y_i.

vertices. The remaining d:=a−s≥0d:=a-s\ge0 deletions reduce dd of the resulting parts of size kk to size k−1k-1 (when k=1k=1, they remove those singleton parts). Consequently,

∣E(Y−C)∣=bk(∑i=kℓyi−d)+bk−1d|E(\mathcal{Y}-C)|=b_k\left(\sum_{i=k}^{\ell}y_i-d\right)+b_{k-1}d
+∑i=1k−1biyi=a(1−k)+∑i=kℓ(2i−k)(k−1)2yi\begin{aligned} \quad+\sum_{i=1}^{k-1}b_i y_i \\ &=a(1-k)+\sum_{i=k}^{\ell}\frac{(2i-k)(k-1)}{2}y_i \end{aligned}
+∑i=1k−1biyi.(6)\quad+\sum_{i=1}^{k-1}b_i y_i. \tag*{(6)}

This makes explicit the part sizes of Y−C\mathcal{Y}-C determined by the deletion order supplied by Lemma 6.1.

By (5) and the choice of CC,

∣E(X)∣≥bℓxℓ+γℓ−1∣E(Y−C)∣.(7)|E(\mathcal{X})|\ge b_{\ell}x_{\ell}+\gamma_{\ell-1}|E(\mathcal{Y}-C)|. \tag*{(7)}

Our goal is ∣E(X)∣≥γℓ∣E(Y)∣|E(\mathcal{X})|\ge\gamma_{\ell}|E(\mathcal{Y})|. Because γℓ−1>γℓ\gamma_{\ell-1}>\gamma_{\ell}, the terms with indices i<ki<k in (6) already have a sufficiently large coefficient. Thus, it is enough to prove

bℓxℓ+γℓ−1(a(1−k)+∑i=kℓ(2i−k)(k−1)2yi)≥γℓ∑i=kℓbiyi.(8)\begin{aligned} b_{\ell}x_{\ell}+\gamma_{\ell-1}\left(a(1-k)+\sum_{i=k}^{\ell}\frac{(2i-k)(k-1)}{2}y_i\right) \\ &\ge\gamma_{\ell}\sum_{i=k}^{\ell}b_i y_i. \tag*{(8)} \end{aligned}

Since a=ℓxℓa=\ell x_{\ell},

θ:=(ℓ−k)bℓ−1−k+12bℓ−1.\theta:=\frac{(\ell-k)b_{\ell-1}-k+1}{2b_{\ell-1}}.
bℓxℓ+γℓ−1a(1−k)=θa≥θ∑i=kℓ(i−k)yi.b_{\ell}x_{\ell}+\gamma_{\ell-1}a(1-k)=\theta a \ge\theta\sum_{i=k}^{\ell}(i-k)y_i.

Here we used a≥sa \ge s. The coefficient θ\theta is nonnegative: as a function of k≤ℓ−1k \le\ell-1, its numerator is minimized at k=ℓ−1k=\ell-1, where it equals bℓ−1−ℓ+2=(ℓ−2)(ℓ−3)/2b_{\ell-1}-\ell+2=(\ell-2)(\ell-3)/2.

It remains to check, for k≤i≤ℓk \le i \le\ell, that

f(i,k,ℓ):=(ℓ−k)bℓ−1−k+12bℓ−1(i−k)+γℓ−1(2i−k)(k−1)2−γℓbi≥0.f(i,k,\ell):=\frac{(\ell-k)b_{\ell-1}-k+1}{2b_{\ell-1}}(i-k) +\gamma_{\ell-1}\frac{(2i-k)(k-1)}{2}-\gamma_{\ell}b_i\ge0.

Indeed, summing (∗)(*) with weights yiy_i gives (7). Clearing the positive denominator 4ℓ(ℓ−1)(ℓ−2)4\ell(\ell-1)(\ell-2) shows that the sign of ff is the sign of

g(i,k,ℓ):=(−ℓ3+3ℓ2−4ℓ+4)i2+(2ℓ4−7ℓ3+7ℓ2−4)i+ℓk(−2ℓ2+ℓ2k+7ℓ2−3ℓk−7ℓ+4k).\begin{aligned} g(i,k,\ell):={}&(-\ell^3+3\ell^2-4\ell+4)i^2\\ &+(2\ell^4-7\ell^3+7\ell^2-4)i\\ &+\ell k(-2\ell^2+\ell^2k+7\ell^2-3\ell k-7\ell+4k). \end{aligned}

For fixed k,ℓk,\ell, this is a concave quadratic in ii, because its leading coefficient is −(ℓ−2)(ℓ2−ℓ+2)<0-(\ell-2)(\ell^2-\ell+2)<0. Hence it suffices to check the endpoints i=ki=k and i=ℓi=\ell. Direct simplification gives

g(k,k,ℓ)=4k(k−1)≥0.g(k,k,\ell)=4k(k-1)\ge0.

Moreover, g(ℓ,k,ℓ)=ℓh(k,ℓ)g(\ell,k,\ell)=\ell h(k,\ell), where

h(k,ℓ):=(ℓ2−3ℓ+4)k2−(2ℓ3−7ℓ2+7ℓ)k+ℓ4−4ℓ3+3ℓ2+4ℓ−4.h(k,\ell):=(\ell^2-3\ell+4)k^2-(2\ell^3-7\ell^2+7\ell)k +\ell^4-4\ell^3+3\ell^2+4\ell-4.

As a polynomial in kk, h(k,ℓ)h(k,\ell) has positive leading coefficient ℓ2−3ℓ+4\ell^2-3\ell+4 and roots

r1=ℓ−1,r2=(ℓ−2)2(ℓ+1)ℓ2−3ℓ+4.r_1=\ell-1,\qquad r_2=\frac{(\ell-2)^2(\ell+1)}{\ell^2-3\ell+4}.

For ℓ≥6\ell\ge6, we have r2>r1r_2>r_1, since

r2−r1=ℓ2−7ℓ+8ℓ2−3ℓ+4>0;r_2-r_1=\frac{\ell^2-7\ell+8}{\ell^2-3\ell+4}>0;

hence every 1≤k≤ℓ−11\le k\le\ell-1 lies at or to the left of both roots. For ℓ∈{3,4,5}\ell\in\{3,4,5\}, we have ℓ−2≤r2<r1=ℓ−1\ell-2\le r_2<r_1=\ell-1, since

r2−(ℓ−2)=2(ℓ−2)(ℓ−3)ℓ2−3ℓ+4≥0r_2-(\ell-2)=\frac{2(\ell-2)(\ell-3)}{\ell^2-3\ell+4}\ge0

and ℓ2−7ℓ+8<0\ell^2-7\ell+8<0; so the open interval between the roots contains no integer. In either case, h(k,ℓ)≥0h(k,\ell)\ge0, and hence g(ℓ,k,ℓ)≥0g(\ell,k,\ell)\ge0, for every integer 1≤k≤ℓ−11\le k\le\ell-1. This proves (∗)(*) and completes the induction.

Remark 6.3. By Theorem 1.3, GREEDY EDMONDS cannot compute an optimal clique partition of every permutation graph, unless P=NP\mathbb{P}=\mathbb{NP}. There are also small explicit examples. Let GG be the permutation graph of [2,5,4,1,7,3,6][2,5,4,1,7,3,6], depicted in Figure 2. The maximum cliques of GG are {1,4,5}\{1,4,5\} and {3,4,5}\{3,4,5\}. If GREEDY EDMONDS chooses {1,4,5}\{1,4,5\} in its first iteration, then the remaining graph G−{1,4,5}G-\{1,4,5\} has only the two edges {3,7}\{3,7\} and {6,7}\{6,7\}, so a maximum matching of it has one edge, and the algorithm outputs a clique partition with 3+1=43+1=4 edges. However, the clique partition {{3,4,5},{1,2},{6,7}}\{\{3,4,5\},\{1,2\},\{6,7\}\} has 5 edges.

Figure 2. The permutation graph of [2, 5, 4, 1, 7, 3, 6], on which GREEDY EDMONDS can return a nonoptimal clique partition.

We now give a family of graphs which shows that the approximation ratio from Theorem 6.2 is best possible. Moreover, the same family shows that the improved guarantee of Theorem 6.2 does not carry over to CLUSTER DELETION on these graphs.

Theorem 6.4. For every integer ℓ≥3\ell\ge3, there are infinitely many graphs GG with ω(G)=ℓ\omega(G) = \ell and clique partitions X\mathcal{X} that can be output by GREEDY EDMONDS such that

OPT⁡=2(ℓ2)(ℓ2)+1∣E(X)∣and∣E(X)∣=2OPT⁡CD,\operatorname{OPT} = \frac{2\binom{\ell}{2}}{\binom{\ell}{2}+1}|E(\mathcal{X})| \qquad\text{and} \qquad|E(\mathcal{X})| = 2\operatorname{OPT}_{\mathrm{CD}},

where OPT is the maximum number of edges in a clique partition of GG, and OPT⁡CD=∣E(G)∣−OPT⁡\operatorname{OPT}_{\mathrm{CD}} = |E(G)| - \operatorname{OPT} is the minimum number of edges whose deletion turns GG into a cluster graph.

Proof. Fix ℓ≥3\ell\ge3, let L=lcm⁡(3,4,…,ℓ)L = \operatorname{lcm}(3,4,\ldots,\ell), and let mm be any positive multiple of LL. Begin with mm pairwise disjoint row sets R1,…,RmR_1,\ldots,R_m, each containing ℓ\ell vertices. We recursively define disjoint sets C1,C2,…,CtC_1,C_2,\ldots,C_t. Put N0=mℓN_0 = m\ell. As long as

ki:=⌈Ni−1m⌉≥3,k_i := \left\lceil\frac{N_{i-1}}{m} \right\rceil\ge3,

choose CiC_i to consist of kik_i vertices in distinct rows and put Ni=Ni−1−kiN_i = N_{i-1} - k_i. Choose these vertices from the kik_i largest current rows, breaking ties so that, after deleting C1∪⋯∪CiC_1 \cup\cdots\cup C_i, the numbers of remaining vertices in the rows differ by at most one (this is possible since ki≤ℓ≤mk_i \le\ell\le m). Let tt be the last index produced by this procedure.

Define Gℓ,mG_{\ell,m} on the mℓm\ell vertices by making every row RjR_j a clique, making every CiC_i a clique, and adding no other edges. See Figure 3 for a depiction of G6,6G_{6,6}.

Graph $G_{6,6}$ with vertices colored by cliques

Figure 3. The graph G6,6G_{6,6}, with k1=6k_1 = 6, k2=5k_2 = 5, k3=5k_3 = 5, k4=4k_4 = 4, k5=3k_5 = 3, k6=3k_6 = 3. Vertices of the same (non-white) color form a clique in the graph.

We first record the clique structure of this graph. If a clique contains vertices from two different rows, then those two vertices must lie in a common CiC_i. Since the sets CiC_i are disjoint and each CiC_i meets each row in at most one vertex, every other vertex of the clique must also lie in that same CiC_i. Consequently, every clique of Gℓ,mG_{\ell,m} is contained in a row or in one of the sets CiC_i. In particular,

ω(Gℓ,m)=ℓ.\omega(G_{\ell,m}) = \ell.

After C1,…,Ci−1C_1,\ldots,C_{i-1} have been deleted, the remaining row sizes differ by at most one and have sum Ni−1N_{i-1}. Their maximum size is therefore ⌈Ni−1/m⌉=ki\left\lceil N_{i-1}/m \right\rceil= k_i. The future sets CjC_j have nonincreasing sizes kj≤kik_j \le k_i, and the preceding

::: clique-structure observation remains valid in the induced graph. Thus, CiC_i is a maximum clique at iteration ii, and GREEDY EDMONDS can choose C1,C2,…,CtC_1, C_2, \ldots, C_t in that order.

At termination, Nt≤2mN_t \le2m. Just before the last deletion there were more than 2m2m vertices, and kt≤ℓ≤mk_t \le\ell\le m, so Nt>mN_t > m. The remaining row sizes are therefore all 1 or 2. There are exactly Nt−mN_t-m rows of size 2, and a maximum matching in the remaining graph has Nt−mN_t-m edges. Hence this run of GREEDY EDMONDS outputs a partition Xℓ,m\mathcal{X}_{\ell,m} with

∣E(Xℓ,m)∣=∑i=1t(ki2)+Nt−m.(9)|E(\mathcal{X}_{\ell,m})| = \sum_{i=1}^{t} \binom{k_i}{2} + N_t - m. \tag*{(9)}

The row partition shows that OPT⁡ℓ,m≥m(ℓ2)\operatorname{OPT}_{\ell,m} \ge m\binom{\ell}{2}. The reverse inequality follows from ω(Gℓ,m)=ℓ\omega(G_{\ell,m})=\ell. If a clique partition has part sizes s1,s2,…s_1,s_2,\ldots, then

∑j(sj2)≤ℓ−12∑jsj=ℓ−12mℓ=m(ℓ2).\sum_j \binom{s_j}{2} \le\frac{\ell-1}{2}\sum_j s_j = \frac{\ell-1}{2}m\ell= m\binom{\ell}{2}.

Therefore,

OPT⁡ℓ,m=m(ℓ2).(10)\operatorname{OPT}_{\ell,m} = m\binom{\ell}{2}. \tag*{(10)}

It remains to evaluate (8). This can be done exactly because mm is divisible by every q∈{3,…,ℓ}q \in\{3,\ldots,\ell\}. Initially N0=ℓmN_0=\ell m. While Ni−1N_{i-1} decreases from qmqm to (q−1)m(q-1)m, we have ki=⌈Ni−1/m⌉=qk_i=\lceil N_{i-1}/m\rceil=q. This phase consists of exactly m/qm/q steps, each deleting qq vertices. Inducting downwards from q=ℓq=\ell to q=3q=3 shows that ki=qk_i=q occurs exactly m/qm/q times and that Nt=2mN_t=2m. Therefore, (8) gives

∣E(Xℓ,m)∣=∑q=3ℓmq(q2)+m=m2∑q=3ℓ(q−1)+m=m2((ℓ2)+1).\begin{aligned} |E(\mathcal{X}_{\ell,m})| = \sum_{q=3}^{\ell} \frac{m}{q}\binom{q}{2}+m \\ &= \frac{m}{2}\sum_{q=3}^{\ell}(q-1)+m \\ &= \frac{m}{2}\left(\binom{\ell}{2}+1\right). \end{aligned}

Together with (9), this yields the exact equality

OPT⁡ℓ,m=2(ℓ2)(ℓ2)+1∣E(Xℓ,m)∣.\operatorname{OPT}_{\ell,m} = \frac{2\binom{\ell}{2}}{\binom{\ell}{2}+1}|E(\mathcal{X}_{\ell,m})|.

Finally, we count the deleted edges. The edge set of Gℓ,mG_{\ell,m} is the disjoint union of the edge sets of the mm row cliques and of the cliques C1,…,CtC_1,\ldots,C_t, so by the computation above,

∣E(Gℓ,m)∣=m(ℓ2)+∑i=1t(ki2)=m(ℓ2)+m2((ℓ2)−1).|E(G_{\ell,m})| = m\binom{\ell}{2}+\sum_{i=1}^{t}\binom{k_i}{2} = m\binom{\ell}{2}+\frac{m}{2}\left(\binom{\ell}{2}-1\right).

Hence, by (9), the minimum number of edges whose deletion turns Gℓ,mG_{\ell,m} into a cluster graph is

OPT⁡CD=∣E(Gℓ,m)∣−OPT⁡ℓ,m=m2((ℓ2)−1),\operatorname{OPT}_{\mathrm{CD}}=|E(G_{\ell,m})|-\operatorname{OPT}_{\ell,m} =\frac{m}{2}\left(\binom{\ell}{2}-1\right),

whereas the run of GREEDY EDMONDS above deletes

∣E(X‾ℓ,m)∣=∣E(Gℓ,m)∣−∣E(Xℓ,m)∣=m(ℓ2)−m=2OPT⁡CD|E(\overline{\mathcal{X}}_{\ell,m})|=|E(G_{\ell,m})|-|E(\mathcal{X}_{\ell,m})| =m\binom{\ell}{2}-m=2\operatorname{OPT}_{\mathrm{CD}}

edges. There are infinitely many positive multiples mm of LL, so this gives infinitely many examples.

Since every run of GREEDY EDMONDS is also a run of GREEDY, Theorem 6.4 also shows that the factor 2 in Theorem 3.2 is best possible for GREEDY on graphs of any fixed clique number ℓ≥3\ell\ge3.

Proofs of the greedy approximation theorems

Proof of Theorem 3.1. Let X:=(X1,…,Xℓ)\mathcal{X}:=(X_1,\ldots,X_\ell) be the sequence of cliques constructed by GREEDY, where X1X_1 is a maximum clique of GG. We proceed by induction on ℓ\ell. If ℓ=1\ell=1, then ∣E(X)∣=OPT|E(\mathcal{X})|=\mathrm{OPT}. Thus, we may assume ℓ≥2\ell\ge2. Let Y:=(Y1,…,Ym)\mathcal{Y}:=(Y_1,\ldots,Y_m) be an optimal clique partition of GG. Let G′=G−X1G'=G-X_1, X′:=(X2,…,Xℓ)\mathcal{X}':=(X_2,\ldots,X_\ell), Y′:=(Y1∖X1,…,Ym∖X1)\mathcal{Y}':=(Y_1\setminus X_1,\ldots,Y_m\setminus X_1), and OPT′\mathrm{OPT}' be the number of edges in an optimal clique partition of G′G'. Let k:=∣X1∣k:=|X_1|. For each vertex xx in X1X_1, let Y(x)\mathcal{Y}(x) be the unique cluster YY of Y\mathcal{Y} such that x∈Yx\in Y. Define y(x):=∣Y(x)∣−1y(x):=|\mathcal{Y}(x)|-1. Since X1X_1 is a maximum size clique of GG, y(x)≤k−1y(x)\le k-1 for all x∈X1x\in X_1. Therefore,

∣E(Y)∣−∣E(Y′)∣≤∑x∈X1y(x)≤∑x∈X1(k−1)=k(k−1).|E(\mathcal{Y})|-|E(\mathcal{Y}')|\le\sum_{x\in X_1}y(x)\le\sum_{x\in X_1}(k-1)=k(k-1).

We also clearly have

∣E(X)∣−∣E(X′)∣=k(k−1)2.|E(\mathcal{X})|-|E(\mathcal{X}')|=\frac{k(k-1)}{2}.

By induction, ∣E(X′)∣≥OPT′2≥∣E(Y′)∣2|E(\mathcal{X}')|\ge\frac{\mathrm{OPT}'}{2}\ge\frac{|E(\mathcal{Y}')|}{2}. Since ∣E(Y)∣≤∣E(Y′)∣+k(k−1)|E(\mathcal{Y})|\le|E(\mathcal{Y}')|+k(k-1), the preceding two inequalities give ∣E(X)∣≥∣E(Y)∣2|E(\mathcal{X})|\ge\frac{|E(\mathcal{Y})|}{2}, as required. □\square

Proof of Theorem 3.2. Let X=(X1,…,Xr)\mathcal{X}=(X_1,\ldots,X_r) be the sequence of cliques constructed by GREEDY, where X1X_1 is a maximum clique of GG. We induct on rr. The case r=1r=1 is immediate. Let Y=(Y1,…,Ym)\mathcal{Y}=(Y_1,\ldots,Y_m) be an optimal clique partition, and put

G′=G−X1,X′=(X2,…,Xr),Y′=(Y1∖X1,…,Ym∖X1),Z=(X1,Y1∖X1,…,Ym∖X1),\begin{aligned} G'&=G-X_1, & \mathcal{X}'&=(X_2,\ldots,X_r),\\ \mathcal{Y}'&=(Y_1\setminus X_1,\ldots,Y_m\setminus X_1),\\ \mathcal{Z}&=(X_1,Y_1\setminus X_1,\ldots,Y_m\setminus X_1), \end{aligned}

omitting empty parts. Write D(P)=E(P‾)D(\mathcal{P})=E(\overline{\mathcal{P}}) for any clique partition P\mathcal{P}. By induction,

∣D(X′)∣≤2∣D(Y′)∣.|D(\mathcal{X}')|\le2|D(\mathcal{Y}')|.

Since D(Z)D(\mathcal{Z}) is the disjoint union of δG(X1)\delta_G(X_1) and D(Y′)D(\mathcal{Y}'), it follows that

∣D(X)∣≤∣δG(X1)∣+2∣D(Y′)∣=∣D(Z)∣+∣D(Y′)∣.(11)|D(\mathcal{X})|\le|\delta_G(X_1)|+2|D(\mathcal{Y}')|=|D(\mathcal{Z})|+|D(\mathcal{Y}')|. \tag*{(11)}

Let

P=D(Z)∖D(Y)andQ=D(Y)∖D(Z).P=D(\mathcal{Z})\setminus D(\mathcal{Y}) \qquad\text{and}\qquad Q=D(\mathcal{Y})\setminus D(\mathcal{Z}).

Put k=∣X1∣k=|X_1| and xi=∣X1∩Yi∣x_i=|X_1\cap Y_i|. Because every YiY_i is a clique and X1X_1 is a maximum clique, ∣Yi∣≤k|Y_i|\le k, and hence

∣P∣=∑i=1mxi(∣Yi∣−xi)≤∑i=1mxi(k−xi)=2∑1≤i<j≤mxixj=2∣Q∣.\begin{aligned} |P|=\sum_{i=1}^{m}x_i(|Y_i|-x_i) \\ &\le\sum_{i=1}^{m}x_i(k-x_i)=2\sum_{1\le i<j\le m}x_i x_j=2|Q|. \end{aligned}

Here QQ consists precisely of the edges of the clique X1X_1 whose ends lie in different parts of Y\mathcal{Y}. Moreover, D(Y′)D(\mathcal{Y}') and QQ are edge-disjoint subsets of D(Y)D(\mathcal{Y}): the former contains edges with both ends outside X1X_1, while the latter contains edges with both ends inside X1X_1. Using (10), we obtain

∣D(X)∣≤∣D(Z)∣+∣D(Y′)∣=∣D(Y)∣+∣P∣−∣Q∣+∣D(Y′)∣≤∣D(Y)∣+∣Q∣+∣D(Y′)∣≤2∣D(Y)∣=2OPT.\begin{aligned} |D(\mathcal{X})|&\le|D(\mathcal{Z})|+|D(\mathcal{Y}')|\\ &=|D(\mathcal{Y})|+|P|-|Q|+|D(\mathcal{Y}')|\\ &\le|D(\mathcal{Y})|+|Q|+|D(\mathcal{Y}')|\\ &\le2|D(\mathcal{Y})|=2\mathrm{OPT}. \end{aligned}
□\square

Funding

Tony Huynh is supported by the Institute for Basic Science (IBS-R029-C1). Nicola Galesi was partly supported by PRIN 2022 project "Logical methods in combinatorics", 2022BXH4R5, MIUR (Italian Ministry of University and Research).

AI Declaration

The main ideas of the proof of Theorem 1.3 were found by ChatGPT 5.6 Sol. We remark that the ChatGPT proof of Theorem 1.3 contained some serious errors, and has been completely rewritten by the authors. The example in Proposition 4.6 was found by a computer search carried out with the assistance of Anthropic Claude. All other results in this paper were obtained by humans. OpenAI Codex and Anthropic Claude were also used for language editing, proof checking, and to search for additional references. After using these tools, the authors reviewed and edited the content as needed and take full responsibility for the content of the article.

References

References

  1. [1]Aprile, M., Drescher, M., Fiorini, S., Huynh, T., 2023. A tight approximation algorithm for the cluster vertex deletion problem. Math. Program. 197, 1069–1091. URL: https://doi.org/10.1007/s10107-021-01744-w, doi:10.1007/s10107-021-01744-w.
  2. [2]Balmaseda, V., Xu, Y., Cao, Y., Veldt, N., 2024. Combinatorial approximations for cluster deletion: Simpler, faster, and better, in: Proceedings of the 41st International Conference on Machine Learning, pp. 2586–2606.arxiv.org/abs/2404.16131
  3. [3]Bansal, N., Blum, A., Chawla, S., 2004. Correlation clustering. Mach. Learn. 56, 89–113. URL: https://doi.org/10.1023/B:MACH.0000033116.57574.95, doi:10.1023/B:MACH.0000033116.57574.95.
  4. [4]Bathie, G., Bousquet, N., Cao, Y., Ke, Y., Perron, T., 2022. (sub)linear kernels for edge modification problems toward structured graph classes. Algorithmica 84, 3338–3364. URL: https://doi.org/10.1007/s00453-022-00969-1, doi:10.1007/s00453-022-00969-1.
  5. [5]Ben-Dor, A., Shamir, R., Yakhini, Z., 1999. Clustering gene expression patterns. J. Comput. Biol. 6, 281–297. URL: https://doi.org/10.1089/106652999318274, doi:10.1089/106652999318274.
  6. [6]Bonomo, F., Durán, G., Valencia-Pabon, M., 2015. Complexity of the cluster deletion problem on subclasses of chordal graphs. Theor. Comput. Sci. 600, 59–69. doi:https://doi.org/10.1016/j.tcs.2015.07.001.
  7. [7]Böcker, S., Damaschke, P., 2011. Even faster parameterized cluster deletion and cluster editing. Inf. Process. Lett. 111, 717–721. doi:https://doi.org/10.1016/j.ipl.2011.05.003.
  8. [8]Charikar, M., Guruswami, V., Wirth, A., 2005. Clustering with qualitative information. J. Comput. Syst. Sci. 71, 360–383. doi:https://doi.org/10.1016/j.jcss.2004.10.012.
  9. [9]Damaschke, P., 2009. Bounded-degree techniques accelerate some parameterized graph algorithms, in: Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, pp. 98–109.DOI
  10. [10]Dessmark, A., Jansson, J., Lingas, A., Lundell, E.M., Person, M., 2007. On the approximability of maximum and minimum edge clique partition problems. Int. J. Found. Comput. Sci. 18, 217–226. URL: https://doi.org/10.1142/S0129054107004656, doi:10.1142/S0129054107004656.
  11. [11]Diestel, R., [2025] ©2025. Graph theory. volume 173 of Graduate Texts in Mathematics. Sixth ed., Springer, Berlin.
  12. [12]Edmonds, J., 1965. Paths, trees, and flowers. Can. J. Math. 17, 449–467. doi:10.4153/CJM-1965-045-4.DOI
  13. [13]Even, S., Pnueli, A., Lempel, A., 1972. Permutation graphs and transitive graphs. J. ACM 19, 400–410. URL: https://doi.org/10.1145/321707.321710, doi:10.1145/321707.321710.
  14. [14]Fortunato, S., 2010. Community detection in graphs. Phys. Rep. 486, 75–174. doi:https://doi.org/10.1016/j.physrep.2009.11.002.
  15. [15]Fredman, M.L., 1975. On computing the length of longest increasing subsequences. Discrete Math. 11, 29–35. doi:10.1016/0012-365X(75)90103-X.DOI
  16. [16]Gao, Y., Hare, D.R., Nastos, J., 2013. The cluster deletion problem for cographs. Discrete Math. 313, 2763–2771. URL: https://doi.org/10.1016/j.disc.2013.08.017, doi:10.1016/j.disc.2013.08.017.
  17. [17]Golovach, P.A., Heggernes, P., Konstantinidis, A.L., Lima, P.T., Papadopoulos, C., 2018. Parameterized Aspects of Strong Subgraph Closure, in: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), pp. 23:1–23:13. doi:10.4230/LIPIcs.SWAT.2018.23.arxiv.org/abs/1802.10386
  18. [18]Golumbic, M.C., 2004. Algorithmic graph theory and perfect graphs. volume 57. Elsevier.
  19. [19]Gramm, J., Guo, J., Hüffner, F., Niedermeier, R., 2005. Graph-modeled data clustering: Exact algorithms for clique generation. Theory Comput. Syst. 38, 373–392. URL: https://doi.org/10.1007/s00224-004-1178-y, doi:10.1007/s00224-004-1178-y.
  20. [20]Grötschel, M., Lovász, L., Schrijver, A., 1993. Geometric Algorithms and Combinatorial Optimization. volume 2 of Algorithms and Combinatorics. Second ed., Springer-Verlag, Berlin. doi:10.1007/978-3-642-78240-4.DOI
  21. [21]Grüttemeier, N., Komusiewicz, C., 2020. On the relation of strong triadic closure and cluster deletion. Algorithmica 82, 853–880. doi:https://doi.org/10.1007/s00453-019-00617-1.
  22. [22]Italiano, G.F., Konstantinidis, A.L., Papadopoulos, C., 2025. Structural parameterization of cluster deletion. Algorithmica 87, 961–981. doi:10.1007/s00453-025-01303-1.DOI
  23. [23]Jansen, K., 2000. Approximation results for the optimum cost chromatic partition problem. Journal of Algorithms 34, 54–89. URL: https://www.sciencedirect.com/science/article/pii/S0196677499010222, doi:https://doi.org/10.1006/jagm.1999.1022.
  24. [24]Komusiewicz, C., Uhlmann, J., 2012. Cluster editing with locally bounded modifications. Discrete Appl. Math. 160, 2259–2270. doi:https://doi.org/10.1016/j.dam.2012.05.019.
  25. [25]Konstantinidis, A.L., Papadopoulos, C., 2021. Cluster deletion on interval graphs and split related graphs. Algorithmica 83, 2018–2046. doi:10.1007/s00453-021-00817-8.DOI
  26. [26]Li, P., Puleo, G., Milenkovic, O., 2020. Motif and hypergraph correlation clustering. IEEE Trans. Inf. Theory 66, 3065–3078. doi:10.1109/TIT.2019.2940246.DOI
  27. [27]Marshall, A.W., Olkin, I., Arnold, B.C., 2011. Inequalities: Theory of Majorization and its Applications. Springer Series in Statistics. second ed., Springer, New York. doi:10.1007/978-0-387-68276-1.DOI
  28. [28]McConnell, R.M., Spinrad, J.P., 1999. Modular decomposition and transitive orientation. Discrete Math. 201, 189–241. doi:10.1016/S0012-365X(98)00319-7.DOI
  29. [29]Pnueli, A., Lempel, A., Even, S., 1971. Transitive orientation of graphs and identification of permutation graphs. Can. J. Math. 23, 160–175. doi:10.4153/CJM-1971-016-5.DOI
  30. [30]Puleo, G.J., Milenkovic, O., 2015. Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM J. Optim. 25, 1857–1872. URL: https://doi.org/10.1137/140994198, doi:10.1137/140994198.
  31. [31]Rhee, C., Liang, Y.D., 1995. Finding a maximum matching in a permutation graph. Acta Inform. 32, 779–792. URL: https://doi.org/10.1007/s002360050033, doi:10.1007/s002360050033.
  32. [32]Shamir, R., Sharan, R., Tsur, D., 2004. Cluster graph modification problems. Discrete Appl. Math. 144, 173–182. doi:https://doi.org/10.1016/j.dam.2004.01.007.
  33. [33]Shi, J., Malik, J., 2000. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 888–905. doi:10.1109/34.868688.DOI
  34. [34]Sintos, S., Tsaparas, P., 2014. Using strong triadic closure to characterize ties in social networks, in: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1466–1475. doi:10.1145/2623330.2623664.DOI
  35. [35]Veldt, N., 2022. Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds, in: Proceedings of the 39th International Conference on Machine Learning, pp. 22060–22083.arxiv.org/abs/2111.10699
  36. [36]Veldt, N., Gleich, D.F., Wirth, A., 2018. A correlation clustering framework for community detection, in: Proceedings of the 2018 World Wide Web Conference, pp. 439–448. doi:10.1145/3178876.3186110.DOI

Paper details

vlnc:W_6uwdu72e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents