Reputation: 3
I am working on a task to find the largest independent set in a graph. After researching various approaches, I found that backtracking is often recommended, but it has exponential time complexity, leading to a significant state space growth.
To optimize my solution, I implemented a greedy approach with a slight variation. I represented the graph using an adjacency list and sorted the vertices by their in-degree in descending order. My process is as follows:
1.Select the vertex with the highest in-degree. 2.Remove this vertex from the graph (along with its edges). 3.Repeat the process until no vertices remain.
I have consistently obtained what I believe to be the optimal solution using this method, and it performs faster than backtracking. However, I am curious if there are any counterexamples that would demonstrate that my approach is not optimal.
Is my greedy method for finding the largest independent set sound, or are there specific cases where it fails to provide the optimal solution? Can anyone provide a counterexample where my approach yields a suboptimal independent set?
I tried multiple examples. The counter example for regular greedy is not working here. It finds the optimal.
Help me find a counter example for this.
Upvotes: 0
Views: 91
Reputation: 692
The greedy approach is a good heuristic, but removing highest ranking nodes first might sometimes prohibit finding the optimal solution. Consider for example the nodes N1 to N6 with following adjacence matrix:
N1 N2 N3 N4 N5 N6
0 1 1 1 0 0
1 0 0 0 1 0
1 0 0 0 0 1
1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
Here the largest independent set is N1, N5, N6. If you remove N1 using the greedy approach, you won't find the optimal solution. Also a node with the highest degree of edges might therefore be part of the optimal independent set.
Upvotes: 0