1
$\begingroup$

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?

$\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$
    – greybeard
    Oct 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

1 Answer 1

1
$\begingroup$

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.

tree

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.

$\endgroup$
1
  • $\begingroup$ It seems a good starting point! $\endgroup$
    – Nicholas_
    Oct 13, 2021 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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