Definitions: Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced subgraph (that is, the resulting graph is a disjoin union of cliques).

The class of $k$-trees is defined as follows: a complete graph with $k$ vertices is a $k$-tree; a $k$-trees with $n + 1$ vertices $(n > k)$ can be constructed from a $k$-tree $T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.

Question: Does exist a polynomial-time algorithm to solve Cluster Edge Deletion on 2-trees?

My idea: Let $G$ be the 2-tree. I transform $G$ to a new graph $G'$ where, each node of $G'$ represents a $K_3$ in $G$. And two nodes of $G'$ are adjacent if and only if their corresponding $K_3$ share a common vertex in $G$.

Let $M$ be the resulting graph after removing the minimum edges from $G$. I think that if always exist some graph $M$ contains a 3-clique $H$ which has a node with minimum degree in $G'$, then I can solve this problem on $G \backslash H$.

For example as below figure, I choose node $x$ with minimum degree 3 in $G'$, and after remove all vertices of clique $\{f,g,e\}$ in $G$, I got an union disjoint of two clique $\{f,g,e\}$ and $\{b,c,d\}$ in $G$.

enter image description here

  • $\begingroup$ @D.W. I edited the question to clarify the definition. A 2-tree can be more than just an edge. In particular, the point of $k$-trees is that they give you a class of graphs such that every graph of treewidth at most $k$ ($k-1$?) is a subgraph of some $k$-tree. Or, in other words, a $k$-tree is an edge-maximal graph of treewidth $k$ ($k-1$?)$. $\endgroup$ Jun 22, 2016 at 7:34
  • $\begingroup$ @DavidRicherby: Thanks you for giving nice properties on $k$-tree. But I don't know how to use it in this problem :3. Can you say it more detail? $\endgroup$
    – VuanCoal
    Jun 22, 2016 at 10:31
  • $\begingroup$ I don't know if the properties I've given are useful to the question; I mentioned them only to help @D.W. understand the definition. It might be useful to know that, for any fixed $k$, there is a polynomial-time algorithm for the following problem: given a graph, either output a tree decomposition of width at most $k$ or return "Treewidth is greater than $k$." The porblem might be much easier to solve once you have a tree decomposition, since every maximal clique must be within a bag of the decomposition. $\endgroup$ Jun 22, 2016 at 10:47
  • $\begingroup$ 1. The definition of your $G'$ is not clear. I doubt you intend that $G'$ has only a single vertex, and I'm having a hard time understanding the definition of $E'$. 2. You mention recursively applying the algorithm to $G \setminus H$, but is there any reason to think that $G \setminus H$ is guaranteed to be a 2-trees? If not, then you can't recursively apply the same algorithm (or at least it needs some justification why you can). 3. Can you edit the question to clarify? $\endgroup$
    – D.W.
    Jun 22, 2016 at 16:50
  • $\begingroup$ @D.W.: Sorry for late reply, I will edit question and definition of $E'$ as soon as possible. And about $G \backslash H$, it is not guaranteed to be 2-trees, but if can prove the first statement I given, I think can get some directions to look into. $\endgroup$
    – VuanCoal
    Jun 23, 2016 at 5:59

1 Answer 1


Let me first formalize the problem:

Cluster edition

Instance: A graph $G$ and an integer $k$.

Question: Can $G$ be transformed into a cluster graph by deleting at most $k$ edges?

It is not difficult to see that the problem is, already for general graphs, fixed-parameter tractable (FPT) parameterized by the number of edge deletions $k$. Being FPT means the problem is solvable in time $f(k) n^{O(1)}$, where $f$ is a computable function depending solely on $k$.

The observation is the following: cluster graphs are precisely the $P_3$-free graphs, i.e., the graphs that don't contain the path on 3 vertices as an induced subgraph. So, in order to produce a cluster from $G$, the $k$ edge deletions must "hit" each $P_3$. Clearly, there are two ways to destroy a $P_3$: either we remove edge $a$ or edge $b$. The algorithm is as follows: as long as there is a $P_3$, branch by choosing either one of its edges to delete. This will give you a straightforward $2^k n^{O(1)}$-time algorithm, that will be quite practical if $k$ is not too large.

Looking up the literature, the problem can be solved in $O^*(1.77^k)$ time by a more clever yet simple branching algorithm (see Gramm et al. [1]). Here the $O^*$ notation hides polynomially bounded factors.

It is interesting to ask whether you can do better for chordal graphs, or indeed $q$-trees (I'm using $q$ here to make a distinction between $k$). The problem is solvable in polynomial-time for cographs [2], but NP-complete for chordal graphs [3]. I don't know if the complexity for $q$-trees is known, and I also didn't think hard about it but merely glanced the literature.

[1] Gramm, Jens, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. "Graph-modeled data clustering: Fixed-parameter algorithms for clique generation." In Italian Conference on Algorithms and Complexity, pp. 108-119. Springer Berlin Heidelberg, 2003.

[2] Gao, Yong, Donovan R. Hare, and James Nastos. "The cluster deletion problem for cographs." Discrete Mathematics 313, no. 23 (2013): 2763-2771.

[3] Bonomo, Flavia, Guillermo Duran, and Mario Valencia-Pabon. "Complexity of the cluster deletion problem on subclasses of chordal graphs." Theoretical Computer Science 600 (2015): 59-69.

  • $\begingroup$ Thanks you for clearly explanation. Follow @DavidRicherby's comment, I have searched with additional "tree decomposition" keyword and got a paper mention to Disjoint Cliques Problem on some classes of graph, include partial $k$-tree, but I don't understand it well :3. And here is that link. $\endgroup$
    – VuanCoal
    Jun 22, 2016 at 16:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.