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