In a graph, an independent set is a vertex subset which doesn't contain an edge as an induced subgraph. The problem of finding largest independent sets in a graph is a fundamental algorithmic question, and a hard one at that. Let's consider the more general question of finding (the size of) a largest H-free set in a graph, where H-free means that it does not induce a subgraph that contains a copy of the fixed graph H as an induced subgraph.
For fixed graph H, given input graph G, is it NP-hard to determine the size of a largest H-free set in G?
Is there a sensible way to construct a "table" of graphs H (or classes of H), so as to fill in the entries with correct yes or "no" answers to the above question? (Let's pretend that "no" = P, and even that a "no" entry means there is a polytime algorithm to generate a largest H-free set.)
Failing that, are there non-trivial classes of H for which the answer is yes? ... no?
I was digging around, looking into two queries about generalised/H-free chromatic numbers --- here and here --- when it occurred to me that the (ostensibly simpler) "dual" problem of an H-free analogue of independence number might also be open. I am aware of classical papers on a related problem for random graphs, cf. e.g. Erdos, Suen and Winkler (1995) or Bollobas and Thomason (2000), which are in a still very active line of research. So perhaps there is already some work that I have not seen yet addressing this more basic question and that a rough internet search did not uncover (hence the reference-request tag).
