2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.