Algorithm: Finding max subset of elements in array

Question

I have an array arr containing pairs of elements. I need to find the largest subset from that array, such that, each pair wise element in that subset exists in the array arr.

e.g. let arr = [(a,b), (a,c), (a,d), (b,d)]
Then, the largest subset would be {a,b,d}, because all possible pair-wise combinations in the subset exists in arr.

What if there's a loop? Consider [(a,b), (b,d), (d, c), (c,a)] — erip
– erip, Commented Nov 10, 2015 at 13:41
@erip there won't be any duplicates, i.e. both (a,b) and (b,a) won't be in the array. — Saad
– Saad, Commented Nov 10, 2015 at 13:49
@Kriggs the pairs of elements that exist in the array satisfy a condition (have intersection <> null), my goal is to find the largest combination of elements that satisfy this condition (intersection <> null). — Saad
– Saad, Commented Nov 10, 2015 at 13:56

user4668606 · Accepted Answer · 2015-11-10 14:59:03Z

1

This is equivalent to the problem of finding the largest complete component (maximum clique problem) in an undirected graph, where each pair represents an edge in the graph.

This problem is NP-hard, so there's no better approach than a simple brute-force-search. The implementation is either trivial or too complex to be posted here though, so you'll have to figure that out on your own.

answered Nov 10, 2015 at 14:59

user4668606

Sign up to request clarification or add additional context in comments.

2 Comments

Saad Over a year ago

Thanks for your input, will have a look at that. Also, is finding just the size of the subset also NP-hard? e.g. There maybe multiple combinations of (largest) subset possible, but I am more interested in finding the size of that subset.

user4668606 Over a year ago

that'll be NP-hard aswell

Collectives™ on Stack Overflow

Algorithm: Finding max subset of elements in array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related