how to get non overlapping sets from integer sets?-CodePudding

I need help!

I want to know efficient algorithms for get answer from this problem.

problem: get maximum number of sets can be chosen from given sets

sets = {1,2,4}, {2,3,4}, {3,4,5}, {1,2,6}, {2,3,5}

expected answer is 2! {1,2,6}, {3,4,5}

how can I get the answer when the sets become numerous? Isn't there any algorithm can solve this problem?

CodePudding user response：

Your problem is an instance of the Maximum independent set problem.

Using python and networkx' maximum_independent_set:

from networkx import Graph
from networkx.algorithms.approximation.clique import maximum_independent_set
from itertools import combinations

V = [frozenset(s) for s in [{1,2,4}, {2,3,4}, {3,4,5}, {1,2,6}, {2,3,5}]]
E = [(x,y) for x,y in combinations(V, 2) if x&y] # "if x&y" means "if intersection of sets x and y is non-empty"
G = Graph()
G.add_nodes_from(V)
G.add_edges_from(E)

print( maximum_independent_set(G) )
# {frozenset({1, 2, 6}), frozenset({3, 4, 5})}

Note that networkx' maximum_independent_set function uses an approximation algorithm, i.e. in a big graph, the maximal independent set it finds might not be of maximum size. The documentation page links the research paper detailing the algorithm, and comments: "The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph."