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 linear-time algorithm to solve Cluster Edge Deletion on 2-trees?

  • $\begingroup$ Your definition of M needs to be reworked, or give a formal definition for "the minimum edges of G". Can you also explain how your construction works on your graph if the vertex f didn't exist. Resulting cluster deletions do not necessarily end up in triangles only: 2-vertex components might be in the final partition. Cluster deletion was studied thoroughly on chordal graphs here: hal.archives-ouvertes.fr/hal-01102512/file/… but I don't think any of those results answer the case of 2-trees, which is an interesting question. Or k-trees in general. $\endgroup$
    – JimN
    Jun 28, 2016 at 17:40

1 Answer 1


The edge sets whose deletion leaves a cluster graph can easily be described as a formula with one free variable (the edge set) in monadic second-order graph logic. Therefore, by an optimization version of Courcelle's theorem, the minimum cardinality set can be found in linear time for graphs of bounded treewidth, which obviously include the 2-trees.

See e.g. Arnborg, Lagergren, and Seese, "Easy problems for tree-decomposable graphs", J. Algorithms 1991.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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