I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start.

Also, I want to devise a Mont Carlo algorithm for this problem.

I would appreciate any help. Thank you.

  • $\begingroup$ Maximum Independent Set in an NP-hard optimization problem. You are unlikely to find any kind of efficient algorithm that always works. $\endgroup$ Feb 5 at 9:43
  • 1
    $\begingroup$ I know it, but I want to devise a randomized algorithm anyway. @YuvalFilmus $\endgroup$ Feb 5 at 14:39
  • $\begingroup$ The acronym MIS is usually used to indicate maximal independent set, is that what you mean or indeed maximum? $\endgroup$
    – kviiri
    Feb 5 at 18:51
  • 5
    $\begingroup$ What's the context in which you encountering this? What is the motivation for this task? It is trivial to construct an exponential-time algorithm if you don't care about its running time. What is preventing you from doing that? What progress have you made? $\endgroup$
    – D.W.
    Feb 5 at 21:47
  • 1
    $\begingroup$ @SepehrOmidvar I know. What I was saying is that maybe it's easier for you to find a Las Vegas for Clique than for IS. Problems are equally hard, but humans think with intuition not always with hardness. $\endgroup$ Feb 10 at 8:27

Your Answer

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

Browse other questions tagged or ask your own question.