CODEWITHSUNDEEP
c++algorithmsetmax
Juan Ignacio Suarez
Juan Ignacio Suarez

Reputation: 45

Efficient maximum independent set within a graph with a maximum degree of 2

The limitations are of 100.000 (10^5) nodes and 2 or less edges per node

How could we get a maximum independent set for this graph in O(n) or O(n log n) time? Otherwise, it goes out on time. By the way, i just need to know the amount of points integrating the set, not necessarily the set of points itself.

I know of the greedy aproximation that works on O(n) which is picking nodes with the lowest number of degree, adding them to our set and then removing all its neighbors, repeating that until the graph is empty, and this aproximation works for many cases. Thing is, with these restrictions, isn't there any algorithm that always work?

Upvotes: 2

Views: 1439

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

On that class of graphs, if you greedily choose the node with the lowest degree and delete it and its neighbors, then you'll get an optimal solution, in linear time.

Upvotes: 3

Related Questions