CODEWITHSUNDEEP
algorithmdata-structuressetnp-hard
Sazzad Hissain Khan
Sazzad Hissain Khan

Reputation: 40236

Given n sets of integers, how to maximize the number of non overlapping sets

Given n sets of integers, how to maximize the number of non overlapping sets?

For example, lets the given sets be,

{1,2,3}
{1,4,5}
{6,7,8}
{2,3}
{8,9}
{9}

Then the answer will be 4,

 {1,4,5}, {6,7,8}, {2,3}, {9}

{1,2,3} and {1,4,5} can not consist of the non overlapping sets because 1 is common in both sets. Is it an NP heard problem? I will expect a little detail if there is an efficient solution for that problem.

[N.B.] The number of input sets can be upto 1000 with each set containing upto 1000 integers.

Upvotes: 0

Views: 392

Answers (2)

gnasher729
gnasher729

Reputation: 52602

In this case the answer is simple: Assuming no set is empty, you can always find a maximum set where no set is a superset of one of the original sets - because a non-empty set and its superset or overlapping and cannot both be in the maximum set, and the superset can be replaced with the subset without creating any overlaps.

Here, {1, 2, 3} and {8, 9} can be excluded, and happily the remaining four sets are not overlapping.

Upvotes: 0

user555045
user555045

Reputation: 64903

That's a Maximum Independent Set problem, where your sets correspond to nodes, and nodes corresponding to sets that share at least one element have an edge between them. It's NP-Hard and also hard to approximate to a constant factor.

You can still attempt to solve it, for example with integer linear programming:

maximize: sum x[i]

for each pair of sets (i,j) that overlap: x[i] + x[j] <= 1

x[i] is a boolean indicated whether the i'th set is part of the MIS that you're finding.

Upvotes: 5

Related Questions