The mentioned problem: Cluster Editing Problem. I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can anyone helps me to face the problem?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ (Did you try "implementing the last paragraph"? For any sub-graph with three vertices and two edges, follow removing each pre-existing edge and adding the "missing" one.) $\endgroup$– greybeardOct 12, 2021 at 21:38
-
$\begingroup$ I received this problem a couple of days ago, so I haven't implemented anything yet. $\endgroup$– Nicholas_Oct 12, 2021 at 23:07
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Here's my thoughts on it. Create a tree with the root node containing $G$. If the graph in a node contains a forbidden induced subgraph $P_3$ then it will have children containing the resulting graphs after applying each of the 3 branching rules. As you continue down the tree, each successive graph becomes one edit closer to satisfying the condition of disjoint cliques. Apply BFS to find the first node with no children - that node will not have a forbidden induced subgraph $P_3$ and is a graph $S$ of disjoint cliques solving the problem. Since the depth of the tree corresponds with the number of edits made, $S$ will have the minimum number of edits required.
Now, I'm not sure how to prove that a solution $S$ will exist for every $G$ by applying the branching rules. If you can show this tree contains all permutations of edges of $G$ then the search ought to be exhaustive. You will also need to prove a graph not containing a forbidden induced subgraph $P_3$ is a solution. I believe that is the case but I can't think of a proof off the top of my head.
