32
$\begingroup$

The ISGCI 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 David Eppstein below), but let's restrict attention to classes that have actually been proved to be IS-easy.

Here are the ones I know of:

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? and see Global properties of hereditary classes? for a more general question I asked previously about hereditary classes.

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.

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:


Added 2013-10-09: the recent result by Lokshtanov, Vatshelle and Villanger, mentioned by Martin Vatshelle 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$.

$\endgroup$
5
  • 1
    $\begingroup$ What about graphs with bounded treewidth? I guess they are already contained in one of the classes that you mentioned? $\endgroup$ Oct 27, 2010 at 9:23
  • $\begingroup$ @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? $\endgroup$ Oct 27, 2010 at 13:59
  • $\begingroup$ á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. $\endgroup$ Oct 27, 2010 at 14:04
  • $\begingroup$ Does $2K_2$-free qualifies? Since there are only FEW independent sets (precisely, $O(n^2)$) in such graphs. $\endgroup$ Oct 28, 2010 at 16:22
  • $\begingroup$ @Hsien-Chih Chang: Thanks for mentioning the Balas-Yu class, had forgotten about that one. Yes, that certainly would make a relevant answer. $\endgroup$ Oct 28, 2010 at 16:45

5 Answers 5

11
$\begingroup$

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

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!

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$ Feb 2, 2011 at 20:55
12
$\begingroup$

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

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?

$\endgroup$
3
  • 1
    $\begingroup$ Interesting question, might be worth posting separately. $\endgroup$ Oct 27, 2010 at 13:49
  • $\begingroup$ In the definition of apples, you mean k ≥ 4, right? $\endgroup$ Oct 28, 2010 at 22:43
  • $\begingroup$ Yes, k>=4, sorry for the typo. $\endgroup$ Oct 29, 2010 at 15:33
10
$\begingroup$

According to Vassilis Giakoumakis and Irena Rusu, Disc. Appl. Math. 1997, the (P5,house)-free graphs (aka (P5,coP5)-free graphs) are IS-easy.

Another one, credited by ISGCI to V. Lozin, R. Mosca Disc. Appl. Math. 2005, is the family of (K2 u claw)-free graphs.

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

$\endgroup$
3
  • $\begingroup$ Thanks for the additional classes and for highlighting an easy construction of infinite chains! Will reword. $\endgroup$ Oct 29, 2010 at 8:48
  • $\begingroup$ So also claw-free graphs, as per the Wikipedia entry on Independent set : en.wikipedia.org/wiki/… $\endgroup$
    – gphilip
    Oct 29, 2010 at 9:41
  • 3
    $\begingroup$ @gphilip: claw-free are included under both chair-free and (K2 u claw)-free. $\endgroup$ Oct 29, 2010 at 15:11
8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

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

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