<p>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.</p>

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

CC BY-SA 3.0
2016-06-28T18:20:06.857Z
2016-06-28T19:12:54.483Z
2016-06-28T19:12:54.483Z
David Eppstein
<p><strong>Definitions:</strong>
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).</p>

<p>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 &gt; k)$ can be constructed from a $k$-tree&nbsp;$T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.</p>

<p><strong>Question:</strong>
Does exist a linear-time algorithm to solve Cluster Edge Deletion on 2-trees?</p>

CC BY-SA 3.0
2016-06-28T17:40:02.770Z
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: https://hal.archives-ouvertes.fr/hal-01102512/file/cluster-del-chordal-v7.pdf 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
<graph-theory><graph-algorithms><clustering>
Cluster Edge Deletion on 2-trees
VuanCoal
# Cluster Edge Deletion on 2-trees

(Asked by: username_0 on 2016-06-24)

**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?

**Tags:** graph-theory, graph-algorithms, clustering

> **Comments:**
> **username_1**: 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: https://hal.archives-ouvertes.fr/hal-01102512/file/cluster-del-chordal-v7.pdf 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.  

---

## 1 answers

### Answer by username_2 on 2016-06-28. Score: 4

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.


---

