I have a set S consisting of natural numbers and a function that when given two natural numbers as an input it returns either true or false. Let's call the criteria based on which it computes the output with the name "independence". So, some pairs of numbers are independent, others aren't. A pair consisting of the same number is not independent. What I want to compute is the largest subset of S such that all of its elements are pairwise independent.
Are there any classic algorithms that solve a similar problems? Do you have suggestions or hints? I just really don't know what to try, even with a bruteforce approach, I'm not sure how to efficiently compute and store different subsets and compare them to find the largest one.
Edit: I just realized the problem can be described using a graph where the independence between two numbers defines an edge that connects two vertices. The problem boils down to finding a longest path in the graph.
P.S. my language of choice is C++ but I'm comfortable with other syntaxes.
Your graph theory interpretation of the problem isn't exactly correct - a simple counterexample would be a relation where two numbers are "independent" if they are consecutive. While a valid path if you constructed the graph would be 1, 2, 3, etc. it's obvious that 1 and 3 aren't independent. Thus, there exist infinitely long paths, while the largest such subset can only contain 2 elements.
The analogy you want would be finding the largest complete subgraph of a graph, to which I'd direct you to this Wikipedia article, and is equivalent to the maximum clique problem. You can find some recursive code implementations of MCP online.