Cluster Editing on Cographs and Related Classes

We first settle the complexity of Cluster Editing on cographs by showing that it is not only NP-hard, but also W[1]-hard when a parameter $p$ is specified, which represents the number of desired clusters. We use the Unary Bin Packing hardness results from [32], which also implies an Exponential Time Hypothesis (ETH) lower bound that forbids time $n^{o(p/\log p)}$ under this parameter. In fact, our hardness holds for very restricted classes of cographs, namely graphs obtained by taking two cluster graphs, and adding all possible edges between them (this also correspond to cographs that admit a cotree of height $3$). Moreover, because cographs have clique-width ($cw$) at most 2, this also means that the problem is para-NP-hard in clique-width, and that a complexity of the form $n^{g(cw)}$ is unlikely, for any function $g$ (the same actually holds for the modular-width parameter and generalizations, see [20, 39]). In fact, the ETH forbids time $f(p)n^{g(cw)\cdot o(p/\log p)}$ for any functions $f$ and $g$, which contrasts with the aforementioned subexponential bounds in $pk$ [19].

The hardness also extends to all superclasses of cographs, such as circle graphs, perfect graphs, and permutation graphs. On the other hand we show that time $n^{O(p)}$ can be achieved on any cograph, which is almost tight. This contrasts with the general Cluster Editing problem which is NP-hard when $p=2$. In fact, this complexity follows from a more general algorithm for arbitrary graphs that runs in time $n^{O(cw\cdot p)}$, which shows that Cluster Editing is XP in parameter $cw+p$. Note that our hardness results imply that XP membership in either parameter individually is unlikely, and so under standard assumptions both $cw$ and $p$ must contribute in the exponent of $n$.

Finally, we aim to find the largest subclass of cographs on which Cluster Editing is polynomial-time solvable. The literature mentioned above implies that such a class lies somewhere between $P_4$-free and $\{P_4,C_4,2K_2\}$-free graphs. We improve the latter by showing that Cluster Editing can be solved in time $O(n^3)$ on $\{P_4,C_4\}$-free graphs, also known as trivially perfect graphs (TPG). This result is achieved by a characterization of optimal clusterings on TPGs, which says that as we build a clustering going up in the cotree, only the largest cluster is allowed to become larger as we proceed.

Our results are summarized in the following, where $n$ is the number of vertices of the graphs, and $p$-Cluster Editing is the variant in which the edge modifications must result in $p$ connected components that are cliques. We treat $p$ as a parameter specified in the input.

A cograph is a graph that can be constructed using the three following rules: (1) a single vertex is a cograph; (2) the disjoint union $G\cup H$ of cographs $G,H$ is a cograph; (3) the join $G\vee H$ of cographs $G,H$ is a cograph. Cographs are exactly the $P_4$-free graphs, i.e., that do not contain a path on four vertices as an induced subgraph.

Cographs are also known for their tree representation. For a graph $G$, a cotree for $G$ is a rooted tree $T$ whose set of leaves, denoted $L(T)$, satisfies $L(T)=V(G)$. Moreover, every internal node $v\in V(T)\setminus L(T)$ is one of two types, either a $0$-node or a $1$-node, such that $uv\in E(G)$ if and only if the lowest common ancestor of $u$ and $v$ in $T$ is a $1$-node¹¹1To emphasize the distinction between general graphs and trees, we will refer to vertices of a tree as nodes.. It is well-known that $G$ is a cograph if and only if there exists a cotree $T$ for $G$. This can be seen from the intuition that leaves represent applications of Rule (1) above, $0$-node represents disjoint unions, and $1$-node represents joins.

A trivially perfect graph (TPG), among several characterizations, is a cograph $G$ that has no induced cycle on four vertices, i.e., a $\{P_4,C_4\}$-free graph. TPGs are also the chordal cographs. For our purposes, a TPG is a cograph that admits a cotree $T$ in which every $1$-node has at most one child that is not a leaf (see [28, Lemma 4.1]).

Our clique-width ($cw$) algorithm does not use the notion of $cw$ directly, but instead the analogous measure of NLC-width [28]. We only provide the definition of the latter. Let $G=(V,E,lab)$ be a graph in which every vertex has one of $k$ node labels ($k$-NL), where $lab$ is a function from $V$ to $[k]$. A single-vertex graph labeled $t$ is denoted by ${\bullet }_t$.

Intuitively, operation 2 denoted by ${\times }_S$ takes the disjoint union of the graphs $G_1,G_2$, then adds all possible edges between labeled vertices of $G_1$ and labeled vertices of $G_2$ as controlled by the pairs of $S$. Operation 3 denoted by ${\circ }_R$ relabels the vertices of a graph controlled by $R$. $NL{C}_k$ denotes all $k$-NLC graphs. The NLC-width of a labeled graph $G$ is the smallest $k$ such that $G$ is a $k$-NLC graph. Furthermore, for a labeled graph $G=(V,E,lab)$, the NLC-width of a graph $G^{\prime }=(V,E)$, obtained from $G$ with all labels removed, equals the NLC-width of $G$.

A well-parenthesized expression $X$ built with operations 1, 2, 3 is called a $k$-expression. The graph constructed by $X$ is denoted by $G_X$. We associate the $k$-expression tree $T$ of $G_X$ with $X$ in a natural way, that is, leaves of $T$ correspond to all vertices of $G_X$ and the internal nodes of $T$ correspond to the operations 2, 3 of $X$. For each node $u$ of $T$, the sub-tree rooted at $u$ corresponds to a sub $k$-expression of $X$ denoted by $X_u$, and the graph $G_{X_u}$ constructed by $X_u$ is also denoted by $G^u$. Moreover, we say $G^u$ is the related graph of $u$ in $T$.

Let us briefly mention that a graph has clique-width at most $k$ if it can be built using what we will call a $cw(k)$-expression, which has four operations instead: creating a single labeled vertex ${\bullet }_t$; taking the disjoint union; adding all edges between vertices of a specified label pair $(i,i^{\prime })$; relabeling all vertices with label $i$ to another label $j$. We do not detail further, since the following allows us to use NLC-width instead of clique-width.

We will assume that our $k$-expressions are derived from a given $cw(k)$-expression. Reference [34] is often cited for this transformation, but seems to have vanished from nature. The transformation can be done using the normal form of a $cw(k)$-expression described in [17].

Clearly, Unary Perfect Bin Packing is in NP. Let $(A,b,k)$ be an instance of Unary Bin Packing, where $A=[a_1,\mathrm{\dots },a_n]$. We assume that $k$ is even, as otherwise we increase $k$ by $1$ and add to $A$ an item of value $b$. If ${\sum }_{i=1}^n{a}_i\le 0.1kb$, we argue that we have a YES instance: we can pack the largest $k/2$ of the $n$ items into $k/2$ bins, and pack the other $n-k/2$ items in the remaining bins, as follows. Assume w.l.o.g. $b\ge a_1\ge \mathrm{\cdots }\ge a_{k/2}\ge a_{k/2+1}\ge \mathrm{\cdots }\ge a_n$. We have $k/2\cdot a_{k/2}\le {\sum }_{i=1}^{k/2}{a}_i\le 0.1kb$, so $a_{k/2}\le 0.2b$. This means that $a_{k/2+1},\mathrm{\dots },a_n\le 0.2b$ and we can always select a batch of items with these sizes such that the total size of a batch is in the interval $[0.8b,b]$ until there are no items left (the last batch may have a size less than $0.8b$). Thus, we can pack the items with sizes $a_{k/2+1},\mathrm{\dots },a_n$ using at most bins.

So assume henceforth that ${\sum }_{i=1}^n{a}_i>0.1kb$. Construct an instance $(B,b,k)$ for Unary Perfect Bin Packing, where $B=[a_1,\mathrm{\dots },a_n,1,\mathrm{\dots },1]$ consists of all integers of $A$ and $kb-{\sum }_{i=1}^n{a}_i$ 1s. Since , the new instance size is bounded by a linear function of the original instance size. Moreover, the new instance can be obtained in polynomial time. It is easy to verify that $(A,b,k)$ is a YES instance of Unary Bin Packing if and only if $(B,b,k)$ is a YES instance of Unary Perfect Bin Packing. $◀$

For the remainder, let us denote $a:={\sum }_{i=1}^n{a}_i$ and $s:={\sum }_{i=1}^n{a}_i^2$. Construct an instance $(G,t)$ for Cluster Editing as follows. First, add two cluster graphs $I=B_1\cup \mathrm{\dots }\cup B_k$ and $J=A_1\cup \mathrm{\dots }\cup A_n$ into $G$, where $B_i$ is a complete graph with $h:={(nka)}^{10}$ vertices for every $i\in [k]$, and $A_j$ is a complete graph with $a_j$ vertices for every $j\in [n]$. Then, connect each $v\in V(I)$ to all vertices of $V(J)$. See Figure 1. One can easily verify that $G$ is a cograph obtained from the join of two cluster graphs. In addition, define $t:=(k-1)ah+\frac{1}{2}(k{b}^2-s)$. Clearly, $t$ is an integer since $s\equiv a\equiv kb\equiv k{b}^2$ (mod 2). Let $ℐ=\{V(B_1),\mathrm{\dots },V(B_k)\}$ and $𝒥=\{V(A_1),\mathrm{\dots },V(A_n)\}$. Clearly, every element in $ℐ\cup 𝒥$ is a critical clique of $G$.

Let $𝒞=\{P_1,\mathrm{\dots },P_l\}$. Since each element in $ℐ\cup 𝒥$ is a critical clique of $G$, each such element is a subset of some cluster in $𝒞$ by Proposition 2. Note that each cluster of $𝒞$ could contain $0,1$, or more cliques of $ℐ$. We split the possibilities into three cases and provide bounds on $|F|$ for each case. First, if there exists a cluster of $𝒞$ that includes at least two critical cliques from $ℐ$, then $F$ contains $h^2$ inserted edges to connect two critical cliques from $ℐ$, and thus $|F|\ge h^2$. Assume instead that every cluster of $𝒞$ includes at most one critical clique from $ℐ$. Then, we have $l\ge k$. Suppose $l\ge k+1$. Then, there are $l-k$ clusters in $𝒞$ that do not contain any critical cliques from $ℐ$. Let ${𝒞}^{\prime }\subseteq 𝒞$ consist of these $l-k$ clusters and $U={\bigcup }_{P\in {𝒞}^{\prime }}P$. Then, for every $v\in U$, $kh$ deleted edges are required in $F$ to disconnect $v$ from all vertices of $V(I)$, and for every $u\in V(J)\setminus U$, $(k-1)h$ deleted edges are required in $F$ to disconnect $u$ from all vertices of $V(I)\setminus P$, where $P$ is the clique of $ℐ$ contained in the same cluster as $u$. Therefore,

Now assume that $l=k$. Then, every element of $𝒞$ includes exactly one critical clique from $ℐ$. Consider each $i\in [k]$ and assume w.l.o.g. that $V(B_i)\subseteq P_i$. Let $W_i=P_i\setminus V(B_i)$ and let $\{{𝒥}_1,\mathrm{\dots },{𝒥}_k\}$ be a partition of $𝒥$ such that, for each $i\in [k]$, the union of all elements of ${𝒥}_i$ is $W_i$ (such a partition exists because each element of $𝒥$ is entirely contained in some $W_i$). Firstly, $(k-1)h$ deleted edges are required in $F$ to disconnect each $v\in W_i$ from all vertices of $V(I)\setminus V(B_i)$. Secondly, for each $i\in [k]$, $\frac{1}{2}{\sum }_{S,S^{\prime }\in {𝒥}_i}|S||S^{\prime }|$ inserted edges are required in $F$ to connect all vertices of $W_i$. One can easily check that for each $i\in [k]$, $F$ accounts for every edge with an endpoint in $P_i$ and an endpoint outside, and accounts for all non-edges within $P_i$. Therefore, all the possible edges of $F$ are counted. Thus,

We can now compare $|F|$ from the lower bounds obtained in the previous two cases, as follows.

The last line implies that having $|𝒞|=k$, with each element of $𝒞$ a superset of exactly one element from $ℐ$, always achieves a lower cost than the other possibilities.

Next, consider the lower bound of $|F|\ge t$ and the conditions on equality. Using the same starting point,

In (1), we used the Cauchy-Schwarz inequality, and the two sides are equal if and only if $|W_1|=\mathrm{\cdots }=|W_k|$. In addition, $|W_1|=\mathrm{\cdots }=|W_k|$ if and only if $|P_1|=\mathrm{\cdots }=|P_k|$ (recall that $W_i=P_i\setminus V(B_i)$ and $|V(B_i)|=h$ for each $i\in [k]$). This proves every statement of the claim. $\mathrm{⊲}$

Armed with the above claim, we immediately deduce the first statement of the theorem. We now show the second part, i.e., the $n$ items of $A$ can fit perfectly into $k$ bins of capacity $b$ if and only if we can make $G$ a cluster graph with at most $t$ edge modifications.
$(\Leftarrow )$: Assume there is a clustering $𝒞$ of $G$ with cost at most $t$. By Claim 7, the size of any optimal cluster editing set for $G$ is at least $t$. Thus, the cost of $𝒞$ must be equal to $t$, and $𝒞$ must be optimal. Claim 7 then implies that $𝒞=\{P_1,\mathrm{\dots },P_k\}$, such that $|P_1|=\mathrm{\cdots }=|P_k|$ and $V(B_i)\subseteq P_i$ for each $i\in [k]$ (w.l.o.g.). Moreover, each critical clique of $𝒥$ is a subset of some element of $𝒞$ by Proposition 2. So there is a partition ${𝒥}_1,\mathrm{\dots },{𝒥}_k$ of $𝒥$ such that $P_i\setminus V(B_i)={\bigcup }_{S\in {𝒥}_i}S$ for every $i\in [k]$. This means that $𝒥$ can be partitioned into $k$ groups such that the number of vertices in each group equals $b$.
$(\Rightarrow )$: Assume the $n$ items can be perfectly packed into $k$ bins with capacity $b$. We construct a cluster editing set $F$ of size at most $t$. Consider each $i\in [k]$. Let $S_i\subseteq A$ consist of the sizes of the items packed in the $i$-th bin, and define a corresponding cluster graph $B_i^{\prime }={\bigcup }_{a_j\in S_i}{A}_j$. We put in $F$ a set of $(k-1)h$ deleted edges, by disconnecting each $v\in V(B_i^{\prime })$ from every vertex in $V(I)\setminus V(B_i)$ in $G$. We then add to $F$ the set of $\frac{1}{2}{\sum }_{V(A_j),V(A_r)\subseteq V(B_i^{\prime })}{a}_j{a}_r$ of inserted edges into $F$ to make $B_i^{\prime }$ a complete graph, where $j,r\in [n]$. Applying the modifications in $F$ results in a clustering $𝒞=\{P_1,\mathrm{\dots },P_k\}$ such that $P_i=V(B_i)\cup V(B_i^{\prime })$ for each $i\in [k]$. Moreover, the cardinality of the cluster editing set is

Thus, $G$ has a clustering with cost at most $t$. $◀$

Since the reduction given in Lemma 6 is a parameter-preserving Karp reduction from Unary Perfect Bin Packing with parameter $k$ to $p$-Cluster Editing in cographs with parameter $p=k$, we can make the following series of deductions.

Since cographs have a constant clique-width [15], we have the following.