<p>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 <em>non-trivial</em> 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.</p>

<p>[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)</p>

CC BY-SA 2.5
2010-09-04T23:18:44.080Z
Spot on!  Thanks for the reference!  Maybe this type of approach also could be (has been?) applied for the partition problem?
RJK
CC BY-SA 2.5
2010-09-04T23:39:40.870Z
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.
András Salamon
CC BY-SA 2.5
2010-09-04T23:49:03.143Z
@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
CC BY-SA 2.5
2010-09-04T23:49:38.587Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-05T00:56:20.033Z
@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
CC BY-SA 2.5
2010-09-05T01:01:27.623Z
The answer was edited just after I posted the comment, so my previous comment does not apply to the current answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-05T10:11:26.830Z
The Lewis and Yannakakis paper is http://dx.doi.org/10.1016/0022-0000(80)90060-4
András Salamon
CC BY-SA 2.5
2010-09-05T14:53:11.343Z
@Tsuyoshi, @Serge, @Andras: Apologies for the late-evening typos. *Induced* seems to be what's usually referred to when using the term H-free.  But my ill-fated grammar choice forced me to write the word too many times for my liking.  Anyway...  So now my next question is whether the above problem has a finer behaviour when the input G is restricted. Planar? Bounded {path,tree,clique}width? Chordal? Bipartite, even??  Not posting as a separate question yet, in case Serge or somebody else has another nice reference up their sleeve.
RJK
CC BY-SA 2.5
2010-09-05T16:34:36.997Z
@RJK: I don't have an answer to this new bunch of questions. I found some approximation algorithms for planar graphs and their generalizations though; for a starting point, see  Dimitrios M. Thilikos, Hans L. Bodlaender: Fast Partitioning l-Apex Graphs with Application to Approximating Maximum Induced-Subgraph Problems. Inf. Process. Lett. (IPL) 61(5):227-232 (1997).
Serge Gaspers
CC BY-SA 2.5
2010-09-04T23:02:01.010Z
2010-09-05T00:58:44.757Z
2010-09-05T00:58:44.757Z
Serge Gaspers
<p>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.</p>

<p>For fixed graph H, given input graph G, is it NP-hard to determine the size of a largest H-free set in G?</p>

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

<p>Failing that, are there non-trivial classes of H for which the answer is yes? ... no?</p>

<p>I was digging around, looking into two queries about generalised/H-free chromatic numbers --- <a href="https://cstheory.stackexchange.com/questions/65/h-free-cut-problem">here</a> and <a href="https://cstheory.stackexchange.com/questions/884/h-free-partition">here</a> --- 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).</p>

CC BY-SA 2.5
2010-09-04T21:53:34.740Z
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
CC BY-SA 2.5
2010-09-04T22:12:26.723Z
sorry for silliness: editing to remove all instances of k!
RJK
<ds.algorithms><reference-request><graph-theory><np-hardness><co.combinatorics>
Computation of max H-free sets
RJK
# Computation of max H-free sets

(Asked by: username_0 on 2010-09-04)

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](https://cstheory.stackexchange.com/questions/65/h-free-cut-problem) and [here](https://cstheory.stackexchange.com/questions/884/h-free-partition) --- 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).

**Tags:** ds.algorithms, reference-request, graph-theory, np-hardness, co.combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_0**: sorry for silliness: editing to remove all instances of k!  

---

## 1 answers

### Answer by username_2 on 2010-09-04. Score: 10 | Accepted answer

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)

> **Comments:**
> **username_0**: Spot on!  Thanks for the reference!  Maybe this type of approach also could be (has been?) applied for the partition problem?  
> **username_3**: 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.  
> **username_2**: @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.  
> **username_4**: 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.  
> **username_2**: @Tsuyoshi: By a graph is $H$-free, I mean that the graph does not have $H$ as an induced subgraph (as in the question).  
> **username_4**: The answer was edited just after I posted the comment, so my previous comment does not apply to the current answer.  
> **username_3**: The Lewis and Yannakakis paper is http://dx.doi.org/10.1016/0022-0000(80)90060-4  
> **username_0**: @Tsuyoshi, @Serge, @Andras: Apologies for the late-evening typos. *Induced* seems to be what's usually referred to when using the term H-free.  But my ill-fated grammar choice forced me to write the word too many times for my liking.  Anyway...  So now my next question is whether the above problem has a finer behaviour when the input G is restricted. Planar? Bounded {path,tree,clique}width? Chordal? Bipartite, even??  Not posting as a separate question yet, in case Serge or somebody else has another nice reference up their sleeve.  
> **username_2**: @username_0: I don't have an answer to this new bunch of questions. I found some approximation algorithms for planar graphs and their generalizations though; for a starting point, see  Dimitrios M. Thilikos, Hans L. Bodlaender: Fast Partitioning l-Apex Graphs with Application to Approximating Maximum Induced-Subgraph Problems. Inf. Process. Lett. (IPL) 61(5):227-232 (1997).  

---

