1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory - Max. Independent set algorithm

  1. Oct 24, 2013 #1
    Graph Theory -- Max. Independent set algorithm

    1. The problem statement, all variables and given/known data

    Design a polynomial time greedy algorithm to compute a maximum independent set for a graph. Explain the algorithm and compute T_w(n).

    2. Relevant equations

    3. The attempt at a solution

    My terse and informal Internet research indicates that a maximum independent set cannot be calculated in polynomial time. For example:

    What could my teacher possibly want? Do I need to design an algorithm that nobody else to date has done? I guess not. I think I misunderstand the question. Can someone help me understand what he wants?

    Thank you
  2. jcsd
  3. Oct 25, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    Maybe "maximum independent set" is not meant in that way, and you are supposed to find an algorithm that finds an independent set where no other vertices can be added (should be easy in n^2). Just a guess, I don't know how the problem statement is meant.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted