11
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 4, 2010 at 21:53
  • $\begingroup$ sorry for silliness: editing to remove all instances of k! $\endgroup$
    – RJK
    Sep 4, 2010 at 22:12

1 Answer 1

10
$\begingroup$

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.

[1] John M. Lewis, Mihalis Yannakakis: The Node-Deletion Problem for Hereditary Properties is NP-Complete. J. Comput. Syst. Sci. 20(2): 219-230 (1980)

$\endgroup$
9
  • $\begingroup$ Spot on! Thanks for the reference! Maybe this type of approach also could be (has been?) applied for the partition problem? $\endgroup$
    – RJK
    Sep 4, 2010 at 23:18
  • 1
    $\begingroup$ I don't follow the reasoning here. The problem is NP-hard even when H has no edges, as long as H has at least two vertices. $\endgroup$ Sep 4, 2010 at 23:39
  • $\begingroup$ @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. $\endgroup$ Sep 4, 2010 at 23:49
  • $\begingroup$ This answer (revision 2) refers to the problem of finding the largest induced subgraph that does not contain H as subgraph. The result of Lewis and Yannakakis applies to the problem of finding the largest induced subgraph that does not contain H as induced subgraph, but the condition on H for the property to be nontrivial is different. $\endgroup$ Sep 4, 2010 at 23:49
  • $\begingroup$ @Tsuyoshi: By a graph is $H$-free, I mean that the graph does not have $H$ as an induced subgraph (as in the question). $\endgroup$ Sep 5, 2010 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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