NPI-candidate hereditary graph property?

Question

A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover, a number of nontrivial general facts are also known about hereditary classes of graphs, see "Global properties of hereditary classes?"

Considering complexity, hereditary graph properties include both polynomial-time decidable and NP-complete ones. We know, however, that there are a number of natural problems in NP that are candidates for NP-intermediate status, see a nice collection in Problems Between P and NPC. Among the numerous answers there, however, none of them looks like a hereditary graph property (unless I overlooked something).

Question: Do you know a hereditary graph property that is a candidate for NP-intermediate status? Or else, is there a dichotomy theorem for hereditary graph properties?

Answer 1

Is there a particular style of problem you are looking for, or anything related to a hereditary graph property? Two common types of problems would be (1) recognition: does a given $G$ have the hereditary property? or (2) find the largest (induced or not) subgraph $H$ in $G$ having the hereditary property.

As I'm sure you are familiar, (2) is NP-complete (Mihalis Yannakakis: Node- and Edge-Deletion NP-Complete Problems. STOC 1978: 253-264) But I'm not sure if you are specifically only asking about problems of type (1) (recognition problems.)

There are a few recognition problems of hereditary graph classes which are still open. I think the one-in-one-out graphs are open to recognize and clearly in NP.

Graphclasses.org also reports that the related class of opposition graphs is still open to recognize (and these are also clearly in NP.) Apparently, so is the class of Domination graphs.

A large list of open (and unknown) recognition status can be found on that site, and pretty much all of those properties appear to be hereditary.

http://www.graphclasses.org/classes/problem_Recognition.html

There is one recognition problem they list under GI-complete, which is not a hereditary property ... so it is interesting to think that perhaps deciding a hereditary problem may indeed have a dichotomy theorem.

Answer 2

Let $G$ be a finite undirected graph. By a "$k$-independent" (resp. a "$k$-clique") of $G$, I mean a disjoint union of $k$ independent sets of $G$; the maximum size of such a set is denoted by $\alpha_k(G)$ (resp. $\omega_k(G)$). Say that $G$ has the "Greene-Kleitman property" if the sequences $(\alpha_i(G))$ and $(\beta_i(G))$ are increasing and correspond to conjugate partitions. It is known that comparability graphs enjoy the Greene-Kleitman property (see "The Structure of Sperner k-Families" by C. Greene and D.J. Kleitman, J. Comb. Theory, Ser. A 20(1): 41-68, and "Generalizations of the Greene-Kleitman theorem" by S. Fomin, FPSAC'94 problem session).

I have no idea if the Greene-Kleitman graphs give an answer to your question, although I would expect their recognition to be either polynomial or NP-intermediate. Similar to perfect graphs, it seems reasonable to investigate this question for restricted graph classes first: for example, it can be seen that the split graphs having the GK property are exactly the (net,tent)-free graphs. I'm probably missing some of the relevant literature though as I'm not a graph theorist.