Maximum subgraph problem with unknown complexity

Question

Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:

Maximum $Q$-Subgraph problem

Input: Simple undirected graph $G=(V,E)$, and an integer $\ell$, with $1\leq \ell\leq |V|$.

Question: Does there exist a subset $S\subseteq V$ with $|S|\geq \ell$, such that the subgraph induced by $S$ is a $Q$-subgraph?

With various choices for the property $Q$ we can get classical problems. For example, if $Q(S)=$ "$S$ spans a clique" then we obtain the Maximum Clique problem, which is $NP$-complete. The choice $Q(S)=$ "$S$ spans a subgraph with a perfect matching" leads to the Maximum Matching problem, which is in $P.$ If we take $Q(S)=$ "$S$ spans a subgraph with minimum degree $\geq k$" leads to the $k$-core problem, which is also in $P.$

Questions:

1. Is there any choice for the (polynomial time decidable) graph property $Q$, such that the complexity of the Maximum $Q$-Subgraph problem is not known?

2. If we do not find such an example for $Q$, then I would venture into the following conjecture: there is a dichotomy here, that is, for every polynomial time decidable graph property $Q$, the Maximum $Q$-Subgraph problem is always either $NP$-complete or is in $P.$ Is there any argument for or against this conjecture?

Answer 1

look at this paper Lewis-Yannakakis where it is proved that for all non-trivial hereditary properties, it is NP-complete, and see Cai where it is proved that with parameter $\ell$, the problem is FPT for hereditary properties with finite number of obstructions.