<p>An interesting paper to look at might be:</p>

<p>A. Brandstadt, V. V. Lozin, R. Mosca: Independent Sets of Maximum Weight in Apple-Free Graphs, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. <a href="http://dx.doi.org/10.1137/090750822">doi:10.1137/090750822</a></p>

<p>The infinite class of apples is defined as cycles C_k, k>=5, each with a stalk.</p>

<p>You don't mention whether your notion of IS-easiness includes the weighted IS problem. Chair-free graphs (aka fork-free graphs) are known to be IS-easy:</p>

<p>V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi:10.1016/S0166-218X(02)00290-1 </p>

<p>The tractability of the weighted case is a non-trivial extension, see:</p>

<p>V. V. Lozin, M. Milanic: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi:10.1016/j.jda.2008.04.001</p>

<p>Are there any other (interesting) classes where the weighted IS problem is significantly more difficult/intractable/open than the unweighted case?</p>

CC BY-SA 2.5
2010-10-27T13:49:23.420Z
Interesting question, might be worth posting separately.
András Salamon
CC BY-SA 2.5
2010-10-28T22:43:22.760Z
In the definition of apples, you mean k ≥ 4, right?
David Eppstein
CC BY-SA 2.5
2010-10-29T15:33:43.443Z
Yes, k>=4, sorry for the typo.
Standa Zivny
CC BY-SA 2.5
2010-10-27T11:03:42.210Z
2010-10-27T11:03:42.210Z
Standa Zivny
<p>A paper accepted to SODA 2014 gives a polynomial time algorithm for Max Weight Independent set on $P_5$ free graphs.
<a href="http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf">http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf</a></p>

<p>Let H be a graph on at most 5 vertices, then the complexity of Independent set is known on the class of H-free graphs.</p>

<p>The problem is hard if H contains a cycle or a degree 4 vertex.
The only remaining cases of connected H are $P_5$, claw and fork, for these classes the problem is known to be polynomial
for disconnected H with no cycles there are only a few possibilities.
If H has isolated vertices it is easy to see that IS is polynomial since it is polynomial for all H on 4 vertices without cycles.
The case $H = P_2 \cup P_3$ was settled by Lozin and Mosca in 2005.</p>

CC BY-SA 3.0
2013-10-08T15:43:24.557Z
2013-10-08T15:43:24.557Z
Martin Vatshelle
<p>According to Vassilis Giakoumakis and Irena Rusu, <a href="http://dx.doi.org/10.1016/S0166-218X%2897%2900093-0">Disc. Appl. Math. 1997</a>, the <a href="http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_402.html">(P5,house)-free graphs</a> (aka (P5,coP5)-free graphs) are IS-easy.</p>

<p>Another one, credited by ISGCI to V. Lozin, R. Mosca <a href="http://dx.doi.org/10.1016/j.dam.2004.07.006">Disc. Appl. Math. 2005</a>, is the family of <a href="http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_735.html">(K2 u claw)-free graphs</a>.</p>

<p><i>There might also be infinite ascending chains of tractable classes</i></p>

<p>There are definitely infinite ascending chains. If H is a finite set of graphs for which the H-free graphs are IS-easy, let H' be the graphs formed adding an independent vertex to each graph in H. Then the H'-free graphs are also IS-easy: just apply the H-free algorithm to the sets of non-neighbors of each vertex. For instance, as ISGCI describes, the <a href="http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_423.html">co-gem-free graphs</a> are IS-easy for the reason that a co-gem is a P4 plus an independent vertex and the P4-free graphs are IS-easy. So you probably want to restrict your question to maximal classes in which not all of the forbidden subgraphs have an independent vertex.</p>

CC BY-SA 2.5
2010-10-29T08:48:49.653Z
Thanks for the additional classes and for highlighting an easy construction of infinite chains!  Will reword.
András Salamon
CC BY-SA 2.5
2010-10-29T09:41:55.567Z
So also claw-free graphs, as per the Wikipedia entry on Independent set : http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Finding_maximum_independent_sets
gphilip
CC BY-SA 2.5
2010-10-29T15:11:54.500Z
@gphilip: claw-free are included under both chair-free and (K2 u claw)-free.
David Eppstein
CC BY-SA 2.5
2010-10-28T22:56:09.283Z
2010-10-29T03:52:50.880Z
2010-10-29T03:52:50.880Z
David Eppstein
<p>In the meantime, it was shown that the problem is polynomial-time solvable on <span class="math-container">$P_6$</span>-free graphs:</p>
<p>Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time Algorithm for Maximum Weight Independent Set on <span class="math-container">$P_6$</span>-free Graphs. ACM Trans. Algorithms 18(1): 4:1-4:57 (2022)</p>
<p><a href="https://doi.org/10.1145/3414473" rel="nofollow noreferrer">https://doi.org/10.1145/3414473</a></p>

CC BY-SA 4.0
2024-03-22T17:03:04.290Z
2024-03-22T17:03:04.290Z
Christian Komusiewicz
<p>The question is already a bit older, but ISGCI can be of some help here.</p>

<p>When you start the ISGCI Java application and go to the menu Problems -> Boundary/Open classes -> Independent set, you get a dialog with 3 lists.</p>

<p>The list Maximal P contains all classes C (in ISGCI) on which IS can be solved in polynomial time, such that there is a minimal superclass of C on which IS is not known to be in P (i.e. NP-complete, open, or unknown to ISGCI). Selecting a class and clicking 'Draw' will draw the class and the superclasses that are found by walking BFS-style up the inclusion hierarchy as far as is needed to find a class on which IS is not known to be in P.</p>

<p>The list Minimal NP-complete goes the other way around: It contains classes on which IS is NP-complete, such that not all maximal subclasses are also NP-complete. Drawing goes down in the hierarchy until a not-NP-complete class is found.</p>

<p>The open list contains classes for which the problem is either open or unknown. Drawing walks over super/subclasses until a class is reached that is not open.</p>

<p>When creating a drawing it is a good idea to set the colouring to the Independent Set problem (Problems -> Colour for problem -> Independent set).</p>

<hr/>

<p>With regard to Standa Zivny's question, the following 20 classes are listed in ISGCI with known complexity for the unweighted IS problem, but with unknown complexity for the weighted case (ISGCI cannot distinguish between "simple" and "complicated" polynomial algorithms):</p>

<p>gc_11 extended P<sub>4</sub>-laden<br>
gc_128 EPT<br>
gc_415 well covered<br>
gc_428 (K<sub>3,3</sub>-e,P<sub>5</sub>,X<sub>98</sub>)-free<br>
gc_648 (K<sub>3,3</sub>-e,P<sub>5</sub>)-free<br>
gc_752 co-hereditary clique-Helly<br>
gc_756 (E,P)-free<br>
gc_757 (P,T<sub>2</sub>)-free<br>
gc_758 (P,P<sub>8</sub>)-free<br>
gc_759 (K<sub>3,3</sub>-e,P<sub>5</sub>,X<sub>99</sub>)-free<br>
gc_808 (C<sub>6</sub>,K<sub>3,3</sub>+e,P,P<sub>7</sub>,X<sub>37</sub>,X<sub>41</sub>)-free<br>
gc_811 (P,star<sub>1,2,5</sub>)-free<br>
gc_812 (P<sub>5</sub>,P<sub>2</sub> ∪ P<sub>3</sub>)-free<br>
gc_813 (P,P<sub>7</sub>)-free<br>
gc_818 (P,star<sub>1,2,3</sub>)-free<br>
gc_819 (P,star<sub>1,2,4</sub>)-free<br>
gc_841 (2K<sub>3</sub> + e,A,C<sub>6</sub>,E,K<sub>3,3</sub>-e,P<sub>6</sub>,R,X<sub>166</sub>,X<sub>167</sub>,X<sub>169</sub>,X<sub>170</sub>,X<sub>171</sub>,X<sub>172</sub>,X<sub>18</sub>,X<sub>45</sub>,X<sub>5</sub>,X<sub>58</sub>,X<sub>84</sub>,X<sub>95</sub>,X<sub>98</sub>,A,C<sub>6</sub>,E,P<sub>6</sub>,R,X<sub>166</sub>,X<sub>167</sub>,X<sub>169</sub>,X<sub>170</sub>,X<sub>171</sub>,X<sub>172</sub>,X<sub>18</sub>,X<sub>45</sub>,X<sub>5</sub>,X<sub>58</sub>,X<sub>84</sub>,X<sub>95</sub>,X<sub>98</sub>,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free<br>
gc_894 co-circular perfect<br>
gc_895 strongly circular perfect<br>
 (3K<sub>2</sub>,E,P<sub>2</sub> ∪ P<sub>4</sub>,net)-free<br></p>

<p>No doubt a number of these will have known algorithms for the weighted case as well. Additions and corrections are always welcome at the address given on the ISGCI web page!</p>

CC BY-SA 2.5
2011-02-02T20:55:19.450Z
thanks for the pointer to the Java application's functionality to find maximal tractable classes, and the list of classes for which the weighted case is open.  And of course thanks for your work on ISGCI!
András Salamon
CC BY-SA 2.5
2011-02-01T13:33:23.510Z
2011-02-01T13:33:23.510Z
Ernst de Ridder
<p>The <a href="http://graphclasses.org/" rel="noreferrer">ISGCI</a> lists over 1100 classes of graphs.  For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called <strong>IS-easy classes</strong>.  I would like to compile a list of <em>maximal</em> IS-easy classes.  These classes together form the boundary of (known) tractability for this problem.</p>

<p>Since one can just add a finite number of graphs to any infinite IS-easy class without affecting tractability, some restrictions are in order.  Let's restrict the classes to those that are hereditary (closed under taking of induced subgraphs, or equivalently, defined by a set of excluded induced subgraphs).  Moreover, let's consider only those families that are X-free for a set X with a small description.  There <strike>might</strike> <em>are</em> also <strike>be</strike> infinite ascending chains of tractable classes (such as $(P,\text{star}_{1,2,k})$-free and the classes described by David Eppstein below), but let's restrict attention to classes that have actually been proved to be IS-easy.</p>

<p>Here are the ones I know of:</p>

<ul>
<li><a href="http://graphclasses.org/classes/gc_56.html" rel="noreferrer">perfect graphs</a></li>
<li><a href="http://graphclasses.org/classes/gc_811.html" rel="noreferrer">$(P,\text{star}_{1,2,5})$-free</a></li>
<li><a href="http://graphclasses.org/classes/gc_648.html" rel="noreferrer">$(K_{3,3}-e, P_5)$-free</a></li>
<li><a href="http://graphclasses.org/classes/gc_162.html" rel="noreferrer">co-Meyniel</a></li>
<li><a href="http://graphclasses.org/classes/gc_640.html" rel="noreferrer">nearly bipartite</a></li>
<li><a href="http://graphclasses.org/classes/gc_391.html" rel="noreferrer">chair-free</a></li>
<li><a href="http://graphclasses.org/classes/gc_427.html" rel="noreferrer">($P_5$,cricket)-free</a></li>
<li><a href="http://dx.doi.org/10.1016/S0166-218X(01)00321-3" rel="noreferrer">$(P_5,K_{n,n})$-free</a> (for any fixed $n$)</li>
<li><a href="http://graphclasses.org/classes/gc_647.html" rel="noreferrer">$(P_5, X_{82}, X_{83})$-free</a></li>
</ul>

<blockquote>
  <p>Are other such maximal classes known?</p>
</blockquote>

<hr>

<p><em>Edit:</em> See also a related question asked by Yaroslav Bulatov dealing with classes defined by excluded minors <a href="https://cstheory.stackexchange.com/questions/2384/what-is-easy-for-minor-excluded-graphs">what is easy for minor-excluded graphs?</a> and see <a href="https://cstheory.stackexchange.com/questions/1005/global-properties-of-hereditary-classes">Global properties of hereditary classes?</a> for a more general question I asked previously about hereditary classes.</p>

<p>As Jukka Suomela points out in comments, the minor-excluded case is also interesting (and would make an interesting question), but this is not the focus here.</p>

<p>To avoid David's example, a maximal class should also be definable as the X-free graphs, where not every graph in X has an independent vertex.</p>

<p>Classes given in answers below:</p>

<ul>
<li><a href="https://cstheory.stackexchange.com/q/2503/#2504">apple-free</a> (suggested by Standa Živný)</li>
<li><a href="http://graphclasses.org/classes/gc_402.html" rel="noreferrer">($P_5$,house)-free</a> (suggested by David Eppstein)</li>
<li><a href="http://graphclasses.org/classes/gc_735.html" rel="noreferrer">($K_2 \cup$ claw)-free</a> (suggested by David Eppstein)</li>
</ul>

<hr>

<p><em>Added 2013-10-09:</em> the recent result by Lokshtanov, Vatshelle and Villanger, mentioned by Martin Vatshelle in an answer, supersedes some of the previously known maximal classes.</p>

<p>In particular, $P_5$-free being IS-easy subsumes ($P_5$,cricket)-free,
($P_5$,$K_{n,n}$)-free,
($P_5$,$X_{82}$,$X_{83}$)-free, and
($P_5$,house)-free
all being IS-easy.</p>

<p>This means that all the hereditary graph classes defined by a single forbidden induced subgraph with up to five vertices can now be definitively classified as IS-easy or not IS-easy.</p>

<p>Unfortunately the proof that $P_5$-free graphs form an IS-easy class does not seem to work for $P_6$-free graphs, so the next frontier is to classify all the hereditary graph classes defined by a single six-vertex graph.</p>

<p>I remain especially interested in IS-easy classes of the form $X$-free for some collection $X$ of graphs with infinitely many isomorphism classes, yet where $Y$-free is not IS-easy for any $Y \subset X$.</p>

CC BY-SA 2.5
2010-10-27T09:23:33.863Z
What about graphs with bounded treewidth? I guess they are already contained in one of the classes that you mentioned?
Jukka Suomela
CC BY-SA 2.5
2010-10-27T13:59:21.210Z
@Jukka: as far as I know bounded treewidth is not possible to capture with a small set of excluded induced subgraphs.  For instance, treewidth 2 is $K_4$-minor-free; this generates an infinite set of excluded induced subgraphs.  On the other hand, "partial k-tree" could well qualify as a "small" description.  What do you think?
András Salamon
CC BY-SA 2.5
2010-10-27T14:04:16.727Z
ás: Oh, it seems that I hadn't read your question carefully enough, I thought you were also interested in graph families that are characterised in terms of forbidden minors.
Jukka Suomela
CC BY-SA 2.5
2010-10-28T16:22:07.470Z
Does $2K_2$-free qualifies? Since there are only FEW independent sets (precisely, $O(n^2)$) in such graphs.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-28T16:45:01.583Z
@Hsien-Chih Chang: Thanks for mentioning the Balas-Yu class, had forgotten about that one.  Yes, that certainly would make a relevant answer.
András Salamon
<ds.algorithms><graph-theory><co.combinatorics><graph-classes>
Maximal classes for which largest independent set can be found in polynomial time?
András Salamon
# Maximal classes for which largest independent set can be found in polynomial time?

(Asked by: username_0 on 2010-10-27)

The [ISGCI](http://graphclasses.org/) lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called **IS-easy classes**. I would like to compile a list of *maximal* IS-easy classes. These classes together form the boundary of (known) tractability for this problem.

Since one can just add a finite number of graphs to any infinite IS-easy class without affecting tractability, some restrictions are in order. Let's restrict the classes to those that are hereditary (closed under taking of induced subgraphs, or equivalently, defined by a set of excluded induced subgraphs). Moreover, let's consider only those families that are X-free for a set X with a small description. There might *are* also be infinite ascending chains of tractable classes (such as $(P,\text{star}\_{1,2,k})$-free and the classes described by username_4 below), but let's restrict attention to classes that have actually been proved to be IS-easy.

Here are the ones I know of:

* [perfect graphs](http://graphclasses.org/classes/gc_56.html)
* [$(P,\text{star}\_{1,2,5})$-free](http://graphclasses.org/classes/gc_811.html)
* [$(K\_{3,3}-e, P\_5)$-free](http://graphclasses.org/classes/gc_648.html)
* [co-Meyniel](http://graphclasses.org/classes/gc_162.html)
* [nearly bipartite](http://graphclasses.org/classes/gc_640.html)
* [chair-free](http://graphclasses.org/classes/gc_391.html)
* [($P\_5$,cricket)-free](http://graphclasses.org/classes/gc_427.html)
* [$(P\_5,K\_{n,n})$-free](http://dx.doi.org/10.1016/S0166-218X(01)00321-3) (for any fixed $n$)
* [$(P\_5, X\_{82}, X\_{83})$-free](http://graphclasses.org/classes/gc_647.html)

> Are other such maximal classes known?

---

*Edit:* See also a related question asked by Yaroslav Bulatov dealing with classes defined by excluded minors [what is easy for minor-excluded graphs?](https://cstheory.stackexchange.com/questions/2384/what-is-easy-for-minor-excluded-graphs) and see [Global properties of hereditary classes?](https://cstheory.stackexchange.com/questions/1005/global-properties-of-hereditary-classes) for a more general question I asked previously about hereditary classes.

As username_1 points out in comments, the minor-excluded case is also interesting (and would make an interesting question), but this is not the focus here.

To avoid David's example, a maximal class should also be definable as the X-free graphs, where not every graph in X has an independent vertex.

Classes given in answers below:

* [apple-free](https://cstheory.stackexchange.com/q/2503/#2504) (suggested by Standa Živný)
* [($P\_5$,house)-free](http://graphclasses.org/classes/gc_402.html) (suggested by username_4)
* [($K\_2 \cup$ claw)-free](http://graphclasses.org/classes/gc_735.html) (suggested by username_4)

---

*Added 2013-10-09:* the recent result by Lokshtanov, Vatshelle and Villanger, mentioned by username_5 in an answer, supersedes some of the previously known maximal classes.

In particular, $P\_5$-free being IS-easy subsumes ($P\_5$,cricket)-free,
($P\_5$,$K\_{n,n}$)-free,
($P\_5$,$X\_{82}$,$X\_{83}$)-free, and
($P\_5$,house)-free
all being IS-easy.

This means that all the hereditary graph classes defined by a single forbidden induced subgraph with up to five vertices can now be definitively classified as IS-easy or not IS-easy.

Unfortunately the proof that $P\_5$-free graphs form an IS-easy class does not seem to work for $P\_6$-free graphs, so the next frontier is to classify all the hereditary graph classes defined by a single six-vertex graph.

I remain especially interested in IS-easy classes of the form $X$-free for some collection $X$ of graphs with infinitely many isomorphism classes, yet where $Y$-free is not IS-easy for any $Y \subset X$.

**Tags:** ds.algorithms, graph-theory, co.combinatorics, graph-classes

> **Comments:**
> **username_1**: What about graphs with bounded treewidth? I guess they are already contained in one of the classes that you mentioned?  
> **username_0**: @Jukka: as far as I know bounded treewidth is not possible to capture with a small set of excluded induced subgraphs.  For instance, treewidth 2 is $K_4$-minor-free; this generates an infinite set of excluded induced subgraphs.  On the other hand, "partial k-tree" could well qualify as a "small" description.  What do you think?  
> **username_1**: ás: Oh, it seems that I hadn't read your question carefully enough, I thought you were also interested in graph families that are characterised in terms of forbidden minors.  
> **username_2**: Does $2K_2$-free qualifies? Since there are only FEW independent sets (precisely, $O(n^2)$) in such graphs.  
> **username_0**: @Hsien-Chih Chang: Thanks for mentioning the Balas-Yu class, had forgotten about that one.  Yes, that certainly would make a relevant answer.  

---

## 5 answers

### Answer by username_8 on 2011-02-01. Score: 11 | Accepted answer

The question is already a bit older, but ISGCI can be of some help here.

When you start the ISGCI Java application and go to the menu Problems -> Boundary/Open classes -> Independent set, you get a dialog with 3 lists.

The list Maximal P contains all classes C (in ISGCI) on which IS can be solved in polynomial time, such that there is a minimal superclass of C on which IS is not known to be in P (i.e. NP-complete, open, or unknown to ISGCI). Selecting a class and clicking 'Draw' will draw the class and the superclasses that are found by walking BFS-style up the inclusion hierarchy as far as is needed to find a class on which IS is not known to be in P.

The list Minimal NP-complete goes the other way around: It contains classes on which IS is NP-complete, such that not all maximal subclasses are also NP-complete. Drawing goes down in the hierarchy until a not-NP-complete class is found.

The open list contains classes for which the problem is either open or unknown. Drawing walks over super/subclasses until a class is reached that is not open.

When creating a drawing it is a good idea to set the colouring to the Independent Set problem (Problems -> Colour for problem -> Independent set).

---

With regard to username_3's question, the following 20 classes are listed in ISGCI with known complexity for the unweighted IS problem, but with unknown complexity for the weighted case (ISGCI cannot distinguish between "simple" and "complicated" polynomial algorithms):

gc\_11 extended P4-laden  
gc\_128 EPT  
gc\_415 well covered  
gc\_428 (K3,3-e,P5,X98)-free  
gc\_648 (K3,3-e,P5)-free  
gc\_752 co-hereditary clique-Helly  
gc\_756 (E,P)-free  
gc\_757 (P,T2)-free  
gc\_758 (P,P8)-free  
gc\_759 (K3,3-e,P5,X99)-free  
gc\_808 (C6,K3,3+e,P,P7,X37,X41)-free  
gc\_811 (P,star1,2,5)-free  
gc\_812 (P5,P2 ∪ P3)-free  
gc\_813 (P,P7)-free  
gc\_818 (P,star1,2,3)-free  
gc\_819 (P,star1,2,4)-free  
gc\_841 (2K3 + e,A,C6,E,K3,3-e,P6,R,X166,X167,X169,X170,X171,X172,X18,X45,X5,X58,X84,X95,X98,A,C6,E,P6,R,X166,X167,X169,X170,X171,X172,X18,X45,X5,X58,X84,X95,X98,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free  
gc\_894 co-circular perfect  
gc\_895 strongly circular perfect  
(3K2,E,P2 ∪ P4,net)-free

No doubt a number of these will have known algorithms for the weighted case as well. Additions and corrections are always welcome at the address given on the ISGCI web page!

> **Comments:**
> **username_0**: thanks for the pointer to the Java application's functionality to find maximal tractable classes, and the list of classes for which the weighted case is open.  And of course thanks for your work on ISGCI!  

---

### Answer by username_3 on 2010-10-27. Score: 12

An interesting paper to look at might be:

A. Brandstadt, V. V. Lozin, R. Mosca: Independent Sets of Maximum Weight in Apple-Free Graphs, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. [doi:10.1137/090750822](http://dx.doi.org/10.1137/090750822)

The infinite class of apples is defined as cycles C\_k, k>=5, each with a stalk.

You don't mention whether your notion of IS-easiness includes the weighted IS problem. Chair-free graphs (aka fork-free graphs) are known to be IS-easy:

V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi:10.1016/S0166-218X(02)00290-1

The tractability of the weighted case is a non-trivial extension, see:

V. V. Lozin, M. Milanic: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi:10.1016/j.jda.2008.04.001

Are there any other (interesting) classes where the weighted IS problem is significantly more difficult/intractable/open than the unweighted case?

> **Comments:**
> **username_0**: Interesting question, might be worth posting separately.  
> **username_4**: In the definition of apples, you mean k ≥ 4, right?  
> **username_3**: Yes, k>=4, sorry for the typo.  

---

### Answer by username_4 on 2010-10-28. Score: 10

According to Vassilis Giakoumakis and Irena Rusu, [Disc. Appl. Math. 1997](http://dx.doi.org/10.1016/S0166-218X%2897%2900093-0), the [(P5,house)-free graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_402.html) (aka (P5,coP5)-free graphs) are IS-easy.

Another one, credited by ISGCI to V. Lozin, R. Mosca [Disc. Appl. Math. 2005](http://dx.doi.org/10.1016/j.dam.2004.07.006), is the family of [(K2 u claw)-free graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_735.html).

*There might also be infinite ascending chains of tractable classes*

There are definitely infinite ascending chains. If H is a finite set of graphs for which the H-free graphs are IS-easy, let H' be the graphs formed adding an independent vertex to each graph in H. Then the H'-free graphs are also IS-easy: just apply the H-free algorithm to the sets of non-neighbors of each vertex. For instance, as ISGCI describes, the [co-gem-free graphs](http://wwwteo.informatik.uni-rostock.de/isgci/classes/gc_423.html) are IS-easy for the reason that a co-gem is a P4 plus an independent vertex and the P4-free graphs are IS-easy. So you probably want to restrict your question to maximal classes in which not all of the forbidden subgraphs have an independent vertex.

> **Comments:**
> **username_0**: Thanks for the additional classes and for highlighting an easy construction of infinite chains!  Will reword.  
> **username_6**: So also claw-free graphs, as per the Wikipedia entry on Independent set : http://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Finding_maximum_independent_sets  
> **username_4**: @username_6: claw-free are included under both chair-free and (K2 u claw)-free.  

---

### Answer by username_5 on 2013-10-08. Score: 8

A paper accepted to SODA 2014 gives a polynomial time algorithm for Max Weight Independent set on $P\_5$ free graphs.
<http://www.ii.uib.no/~martinv/Papers/ISinP5free.pdf>

Let H be a graph on at most 5 vertices, then the complexity of Independent set is known on the class of H-free graphs.

The problem is hard if H contains a cycle or a degree 4 vertex.
The only remaining cases of connected H are $P\_5$, claw and fork, for these classes the problem is known to be polynomial
for disconnected H with no cycles there are only a few possibilities.
If H has isolated vertices it is easy to see that IS is polynomial since it is polynomial for all H on 4 vertices without cycles.
The case $H = P\_2 \cup P\_3$ was settled by Lozin and Mosca in 2005.


---

### Answer by username_7 on 2024-03-22. Score: 1

In the meantime, it was shown that the problem is polynomial-time solvable on $P\_6$-free graphs:

Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk:
Polynomial-time Algorithm for Maximum Weight Independent Set on $P\_6$-free Graphs. ACM Trans. Algorithms 18(1): 4:1-4:57 (2022)

<https://doi.org/10.1145/3414473>


---

