If we are given an undirected graph and we want to find if the graph can be broken down to two subsets of vertices at maximum and not more than that. The vertices in each set are such that each vertex has edge with all other vertices . A single vertex can also be a part of the subsets formed.

Example The graph edges are as follows The graph is undirected 1-2 2-3 1-3 2-4 4-5 5-6 4-6 In this graph we can make {1,2,3} ,{4,5,6}

  • $\begingroup$ This is part of an ongoing coding contest: codechef.com/SEPT16/problems/CHFNFRN. Please don't ask us to solve contest problems for you. And asking for outside help violates the rules of that contest. Also, don't forget to provide attribution for your sources: cs.stackexchange.com/help/referencing. $\endgroup$
    – D.W.
    Sep 11 '16 at 23:26
  • $\begingroup$ Sorry that I asked it while it is on , I will have this post deleted !! Sorry for this !! $\endgroup$
    – user339853
    Sep 12 '16 at 1:33
  • $\begingroup$ I have flagged it and asked it to be deleted . Hope action is taken asap . $\endgroup$
    – user339853
    Sep 12 '16 at 1:58

This sounds like it would require checking all possible subsets. If so, you can solve the problem by enumerating every single subset and checking all of them, but that will not be practical for N > 10 or so.

If I'm understanding correctly, it sounds very similar to the Vertex Cover problem. Which is NP-Hard.

If this for a class, that answer might suffice.

If this is for a project, you're better off finding an approximate answer, where you are certain you are correct with some degree of probability. You can use statistical optimization techniques like simulated annealing to get an answer with some reasonable degree of certainty.

It could be that I misread/misunderstand the problem though, so pardon me if so.


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.