1
$\begingroup$

I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired?

Example of pairs:

A-B
A-C
A-F
B-C
C-D
E-F
F-G

Here the largest subset would be of size 4, and one of the subsets with size 4 would be: {A,D,E,G}.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Let $G$ be the graph whose edges are the given pairs. Then, the problem is to find a maximum independent set in $G$. There exist algorithms for this, but this problem is NP-hard in general.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.