Cluster Edge Deletion on 2-trees [closed]

Question

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$.

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.