0
$\begingroup$

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

$\endgroup$

closed as off-topic by D.W. Jun 28 '16 at 20:51

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – David Richerby Jun 22 '16 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 '16 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$ – David Richerby Jun 22 '16 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 '16 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 '16 at 5:59
2
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 16:39

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