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

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

CC BY-SA 3.0
2014-03-05T02:01:38.457Z
A correction: the GK property as defined is not hereditary. Consider instead the "hereditary Greene-Kleitman" property requiring that each induced subgraph has the GK property. My claim is that the split graphs having the HGK property are exactlly the (net,tent)-free graphs.
Super8
CC BY-SA 3.0
2014-03-05T06:04:32.057Z
A P5 is in the class of (net,tent)-free graphs, but there is no way the P5 is in split \intersect HGK since it is not split. Do you want to rephrase your claim?
JimN
CC BY-SA 3.0
2014-03-04T21:41:32.687Z
2014-03-04T21:41:32.687Z
Super8
<p>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.</p>

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

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

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

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

<p><a href="http://www.graphclasses.org/classes/problem_Recognition.html">http://www.graphclasses.org/classes/problem_Recognition.html</a></p>

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

CC BY-SA 3.0
2014-03-04T19:42:50.053Z
On the page you linked, what are the difference between class "open" and class "unkown"?
Peng Zhang
CC BY-SA 3.0
2014-03-04T19:48:28.910Z
@PengZhang I think open problems are ones that have been confirmed open, and the unknown ones are unconfirmed or under-researched.
JimN
CC BY-SA 3.0
2017-07-04T15:35:45.623Z
This is a nice answer!
Tayfun Pay
CC BY-SA 3.0
2014-03-04T19:04:17.533Z
2014-03-04T19:04:17.533Z
JimN
<p>A graph property is called <strong>hereditary</strong> 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 "<a href="https://cstheory.stackexchange.com/questions/1005/global-properties-of-hereditary-classes">Global properties of hereditary classes?</a>"</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc">Problems Between P and NPC</a>. Among the numerous answers there, however, none of them looks like a hereditary graph property (unless I overlooked something). </p>

<blockquote>
  <p><strong>Question:</strong> 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?</p>
</blockquote>

<cc.complexity-theory><graph-theory><graph-algorithms><p-vs-np>
NPI-candidate hereditary graph property?
Andras Farago
# NPI-candidate hereditary graph property?

(Asked by: username_0 on 2014-03-04)

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?](https://cstheory.stackexchange.com/questions/1005/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](https://cstheory.stackexchange.com/questions/79/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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, p-vs-np

---

## 2 answers

### Answer by username_2 on 2014-03-04. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_3**: On the page you linked, what are the difference between class "open" and class "unkown"?  
> **username_2**: @PengZhang I think open problems are ones that have been confirmed open, and the unknown ones are unconfirmed or under-researched.  
> **username_4**: This is a nice answer!  

---

### Answer by username_1 on 2014-03-04. Score: 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.

> **Comments:**
> **username_1**: A correction: the GK property as defined is not hereditary. Consider instead the "hereditary Greene-Kleitman" property requiring that each induced subgraph has the GK property. My claim is that the split graphs having the HGK property are exactlly the (net,tent)-free graphs.  
> **username_2**: A P5 is in the class of (net,tent)-free graphs, but there is no way the P5 is in split \intersect HGK since it is not split. Do you want to rephrase your claim?  

---

