Graph Theory - Max. Independent set algorithm

Click For Summary
SUMMARY

The discussion revolves around designing a polynomial time greedy algorithm to compute a maximum independent set in graph theory. Participants clarify that finding a maximum independent set is generally not achievable in polynomial time, referencing the Wikipedia page on independent sets. The confusion stems from interpreting the homework statement, with suggestions that the task may involve finding an independent set where no additional vertices can be included, which can be accomplished in O(n²) time complexity.

PREREQUISITES
  • Understanding of graph theory concepts, specifically independent sets.
  • Familiarity with algorithm design, particularly greedy algorithms.
  • Knowledge of time complexity analysis, including polynomial time.
  • Basic proficiency in mathematical proofs related to algorithm efficiency.
NEXT STEPS
  • Research "Greedy algorithms in graph theory" for foundational knowledge.
  • Study "Polynomial time complexity" to understand algorithm efficiency.
  • Explore "Independent set algorithms" to review existing methods and their complexities.
  • Learn about "Graph traversal techniques" to enhance understanding of graph structures.
USEFUL FOR

Students in computer science, algorithm designers, and anyone interested in graph theory and optimization problems will benefit from this discussion.

oneamp
Messages
222
Reaction score
0
Graph Theory -- Max. Independent set algorithm

Homework Statement



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


Homework Equations





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:
http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Finding_maximum_independent_sets

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
 
Physics news on Phys.org
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.
 

Similar threads

Evaluate the complexity of this graph coloring algorithm
  • · Replies 1 ·
Replies
1
Views
2K
Finding an expression for max distance in terms of theta
  • · Replies 10 ·
Replies
10
Views
3K
Plotting a Scatter Diagram from a Large Data Set
  • · Replies 4 ·
Replies
4
Views
2K
[Group Theory] Constructing Cayley Graph from Given Relations
  • · Replies 2 ·
Replies
2
Views
2K
Determining the Max. Set of Linearly Independent Vectors
  • · Replies 7 ·
Replies
7
Views
3K
MHB Does Max-Kruskal Algorithm Find the Maximum Spanning Tree?
  • · Replies 1 ·
Replies
1
Views
2K
C - Degree of a directed unweighted graph
  • · Replies 1 ·
Replies
1
Views
2K
High School Is Max Born's probabilistic proposal artificial?
  • · Replies 10 ·
Replies
10
Views
2K
Efficiently Finding Cycles in a Graph: A Scientific Exploration
  • · Replies 2 ·
Replies
2
Views
2K
MHB Maximizing Independent Set in Graphs: Proving NP-Completeness
  • · Replies 9 ·
Replies
9
Views
4K