# Computation of max H-free sets

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).

• If k and H are both fixed, then you could just enumerate all subsets of vertices of size k and check if they contain H as an induced subgraph. This will be a polynomial time algorithm. – Robin Kothari Sep 4 '10 at 21:53
• sorry for silliness: editing to remove all instances of k! – RJK Sep 4 '10 at 22:12

Suppose $H$ has at least two vertices. The family of all $H$-free graphs is hereditary on induced subgraphs and the property of being $H$-free is non-trivial, where a property is non-trivial if it is true for infinitely many graphs and it is false for infinitely many graphs. Thus, the result of Lewis and Yannakakis [1] applies, showing that for all $H$ with at least two vertices, the problem is NP-complete.
• @Andras. Yes, you're right. I'll slightly generalize my answer from $H$ has at least one edge to $H$ has at least two vertices. You get an up-vote of course. – Serge Gaspers Sep 4 '10 at 23:49
• @Tsuyoshi: By a graph is $H$-free, I mean that the graph does not have $H$ as an induced subgraph (as in the question). – Serge Gaspers Sep 5 '10 at 0:56