# Maximum subgraph problem with unknown complexity

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?

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.
• These are indeed interesting results. However, they do not seem to provide an example for the Maximum $Q$-Subgraph problem with unknown complexity status. – Andras Farago Dec 17 '19 at 14:02