I have a bunch of ordered pairs x, y where 0 < x < y <= n (some given upper bound)


like S = [(1,2), (1,3), (1,4), (2,3), (3,4)]


I need to find the Length of the longest subset where all the numbers within the ordered pairs are unique.


Here that would be 2. eg: (1,4) (2,3)


I am writing code that deals with situations where n is in 100s and S contains thousands of ordered pairs. So looping through the possible combinations is too much computation. I am looking for some other approach.



longest possible chain from a collection of ordered pairs/ co-ordinates
This is an instance of the [*maximum independent set problem*](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximum_independent_sets_and_maximum_cliques) (equivalently, maximum clique of the complement) in a graph with a node per ordered pair and an edge for each pair of ordered pairs that intersect. You can solve the problem via integer linear programming as follows. Let binary decision variable $x\_i$ indicate whether node $i$ is chosen. The problem is to maximize $\sum\_i x\_i$ subject to a conflict constraint $x\_i + x\_j \le 1$ for each edge $\{i,j\}$.


As @Emil Jeřábek 3.0 observed, in the case of pairs, you can instead reformulate as a maximum matching problem in a graph with node set $\{1,\dots,n\}$ and edge set $S$. You can solve that problem via the [blossom algorithm.](https://en.wikipedia.org/wiki/Blossom_algorithm) You can also solve the problem via integer linear programming as follows. Let binary decision variable $y\_{i,j}$ indicate whether edge $\{i,j\}$ is chosen. The problem is to maximize $\sum\_{\{i,j\}\in S} y\_{i,j}$ subject to a constraint $\sum\_{\{i,j\}\in S: k\in\{i,j\}} y\_{i,j} \le 1$ for each node $k$.


