# Cluster Edge Deletion on 2-trees

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?

• 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.
– JimN
Jun 28 '16 at 17:40