<p>look at this paper <a href="https://www.sciencedirect.com/science/article/pii/0022000080900604" rel="nofollow noreferrer">Lewis-Yannakakis</a> where it is proved that for all non-trivial hereditary properties, it is NP-complete, and see <a href="https://www.sciencedirect.com/science/article/pii/0020019096000506?via%3Dihub" rel="nofollow noreferrer">Cai</a> where it is proved that with parameter <span class="math-container">$\ell$</span>, the problem is FPT for hereditary properties with finite number of obstructions. </p>

CC BY-SA 4.0
2019-12-17T14:02:43.507Z
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
CC BY-SA 4.0
2019-12-17T09:58:23.297Z
2019-12-17T09:58:23.297Z
M. kanté
<p>Let <span class="math-container">$Q$</span> be a polynomial time decidable graph property. In a graph let us call a subgraph <span class="math-container">$S$</span> a <em><span class="math-container">$Q$</span>-subgraph,</em> if <span class="math-container">$S$</span> has the property <span class="math-container">$Q$</span>. Consider the following optimization problem:</p>
<p><strong>Maximum <span class="math-container">$Q$</span>-Subgraph problem</strong></p>
<p><strong>Input:</strong> Simple undirected graph <span class="math-container">$G=(V,E)$</span>, and an integer <span class="math-container">$\ell$</span>, with <span class="math-container">$1\leq \ell\leq |V|$</span>.</p>
<p><strong>Question:</strong> Does there exist a subset <span class="math-container">$S\subseteq V$</span> with <span class="math-container">$|S|\geq \ell$</span>, such that the subgraph induced by <span class="math-container">$S$</span> is a <span class="math-container">$Q$</span>-subgraph?</p>
<p>With various choices for the property <span class="math-container">$Q$</span> we can get classical problems. For example, if <span class="math-container">$Q(S)=$</span> &quot;<span class="math-container">$S$</span> spans a clique&quot; then we obtain the Maximum Clique problem, which is <span class="math-container">$NP$</span>-complete. The choice  <span class="math-container">$Q(S)=$</span> &quot;<span class="math-container">$S$</span> spans a subgraph with a perfect matching&quot; leads to the Maximum Matching problem, which is in <span class="math-container">$P.$</span> If we take <span class="math-container">$Q(S)=$</span> &quot;<span class="math-container">$S$</span> spans a subgraph with minimum degree <span class="math-container">$\geq k$</span>&quot; leads to the <span class="math-container">$k$</span>-core problem, which is also in <span class="math-container">$P.$</span></p>
<p><strong>Questions:</strong></p>
<blockquote>
<ol>
<li><p>Is there any choice for the (polynomial time decidable) graph property <span class="math-container">$Q$</span>, such that the complexity of the Maximum <span class="math-container">$Q$</span>-Subgraph problem is not known?</p>
</li>
<li><p>If we do not find such an example for <span class="math-container">$Q$</span>, then I would venture into the following conjecture: there is a dichotomy here, that is, for every polynomial time decidable graph property <span class="math-container">$Q$</span>, the Maximum <span class="math-container">$Q$</span>-Subgraph problem is always either <span class="math-container">$NP$</span>-complete or is in <span class="math-container">$P.$</span> Is there any argument for or against this conjecture?</p>
</li>
</ol>
</blockquote>

<cc.complexity-theory><graph-theory><graph-algorithms><np-complete>
Maximum subgraph problem with unknown complexity
Andras Farago
# Maximum subgraph problem with unknown complexity

(Asked by: username_0 on 2019-12-17)

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?

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

---

## 1 answers

### Answer by username_1 on 2019-12-17. Score: 4

look at this paper [Lewis-Yannakakis](https://www.sciencedirect.com/science/article/pii/0022000080900604) where it is proved that for all non-trivial hereditary properties, it is NP-complete, and see [Cai](https://www.sciencedirect.com/science/article/pii/0020019096000506?via%3Dihub) where it is proved that with parameter $\ell$, the problem is FPT for hereditary properties with finite number of obstructions.

> **Comments:**
> **username_0**: These are indeed interesting results. However, they do not seem to provide an example for the Maximum $Q$-Subgraph problem with unknown complexity status.  

---

