<p>The definition of "natural" is a bit fuzzy, but there's a trivial reason the answer here is likely "no". Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a "this is a certificate and not part of the problem component", in the sense that we can sneak this certificate in without affecting the true answer. </p>

<p>Most "natural" problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examples</p>

<ul>
<li>Max Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)</li>
<li>Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its own</li>
<li>Hamiltonian Circuit: same as Hamiltonian path except <em>some</em> designated vertex is replaced with a certificate graph containing a Hamiltonian cycle</li>
<li>Max Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)</li>
<li>Vertex cover: the certificate is again encoded by a matching</li>
</ul>

<p>We ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most "natural" problems).</p>

<p>Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.</p>

CC BY-SA 3.0
2014-02-27T02:42:02.330Z
2014-02-27T04:27:20.833Z
2014-02-27T04:27:20.833Z
Yonatan N
<p>Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to <em> any </em> polynomial-time recognizable graph class? To avoid degenerated cases, let us consider only <em> dense </em> graph classes, in which   the number of non-isomorphic $\leq n$-vertex graphs grows exponentially with $n$.</p>

<p><em> Notes: </em> </p>

<p>(1) Both a "yes" or a "no" answer would be quite interesting. If the answer is yes, then we would have a natural  $\mathsf{NP}$-complete graph property that could be called <em> universally hard, </em> because it preserves hardness even when  restricted to any reasonable graph class.  If the answer is no, it would mean that every natural $\mathsf{NP}$-complete graph property can be made easy on some nontrivial graph class. </p>

<p>(2) It is important to consider only polynomial-time recognizable graph classes, to exclude that the hardness of the property is simply shifted to the class.
For example, 3-COLORABILITY becomes trivial when restricted  to 3-colorable graphs.</p>

CC BY-SA 3.0
2014-02-12T18:08:33.153Z
Perhaps it would be interesting to ask if there are polynomial time candidates ... for example a graph with $5n/2$ nodes built with a $K_n$ (to satisfy density constraint) linked to a caterpillar with a central path of length $n$ and with $n/2$ nodes of the central path having a single "hair" (to get many non-isomorphic graphs).
Marzio De Biasi
CC BY-SA 3.0
2014-02-27T02:57:04.903Z
Do you allow weights? If you do, it is easy to create problems which remain NP-complete even restricted to the class of complete graphs. And taking a fraction of edges off of the graph would make the number of graphs in the class grow exponentially.
Vinicius dos Santos
CC BY-SA 3.0
2014-02-11T17:38:04.900Z
Finding a 4-coloring of a 3-colorable graph is NP-hard.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-11T17:43:44.167Z
Does this answer your question? [NP-hard problems on paths](http://cstheory.stackexchange.com/questions/20861/np-hard-problems-on-paths/20862#20862)
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-02-11T17:57:59.397Z
why do you ask for a "natural" problem? do you have the answer in general?
Denis
CC BY-SA 3.0
2014-02-11T18:11:28.053Z
A clarification: what do you mean with "any reasonable graph class" exactly? Do you mean that the class members can be recognized in polynomial time? E.g. are paths, or $G = \{ V, \emptyset \}$ (the class of graphs with no edges), or a class with a finite number of members reasonable?
Marzio De Biasi
CC BY-SA 3.0
2014-02-11T18:41:59.750Z
@MarzioDeBiasi it is specified that the class has to be dense, so it rules out graphs with no edges, and all "very small" classes.
Denis
CC BY-SA 3.0
2014-02-11T18:56:38.023Z
@dkuper: you're right, I didn't notice it! :-S
Marzio De Biasi
CC BY-SA 3.0
2014-02-11T19:04:26.157Z
This might interest you: http://www.sciencedirect.com/science/article/pii/0304397576900591
Denis
CC BY-SA 3.0
2014-02-11T20:32:57.077Z
@dkuper: Thank you, I know there are many results about restricting the tasks to special graph classes so that they still remain hard. What I am asking is whether there is a problem that remains hard on $every$ dense, polynomial-time recognizable class. Regarding the issue of naturalness, I do not have the answer in general, but I can imagine that something could possibly be constructed via diagonalization. Of course, a natural problem would be much more attractive.
Andras Farago
<cc.complexity-theory><graph-theory><graph-algorithms><np-complete><graph-classes>
Can a natural graph problem be universally hard?
Andras Farago
# Can a natural graph problem be universally hard?

(Asked by: username_0 on 2014-02-11)

Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to  *any*  polynomial-time recognizable graph class? To avoid degenerated cases, let us consider only  *dense*  graph classes, in which the number of non-isomorphic $\leq n$-vertex graphs grows exponentially with $n$.

*Notes:*

(1) Both a "yes" or a "no" answer would be quite interesting. If the answer is yes, then we would have a natural $\mathsf{NP}$-complete graph property that could be called  *universally hard,*  because it preserves hardness even when restricted to any reasonable graph class. If the answer is no, it would mean that every natural $\mathsf{NP}$-complete graph property can be made easy on some nontrivial graph class.

(2) It is important to consider only polynomial-time recognizable graph classes, to exclude that the hardness of the property is simply shifted to the class.
For example, 3-COLORABILITY becomes trivial when restricted to 3-colorable graphs.

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

> **Comments:**
> **username_3**: Finding a 4-coloring of a 3-colorable graph is NP-hard.  
> **username_3**: Does this answer your question? [NP-hard problems on paths](http://cstheory.stackexchange.com/questions/20861/np-hard-problems-on-paths/20862#20862)  
> **username_4**: why do you ask for a "natural" problem? do you have the answer in general?  
> **username_1**: A clarification: what do you mean with "any reasonable graph class" exactly? Do you mean that the class members can be recognized in polynomial time? E.g. are paths, or $G = \{ V, \emptyset \}$ (the class of graphs with no edges), or a class with a finite number of members reasonable?  
> **username_4**: @MarzioDeBiasi it is specified that the class has to be dense, so it rules out graphs with no edges, and all "very small" classes.  
> **username_1**: @dkuper: you're right, I didn't notice it! :-S  
> **username_4**: This might interest you: http://www.sciencedirect.com/science/article/pii/0304397576900591  
> **username_0**: @dkuper: Thank you, I know there are many results about restricting the tasks to special graph classes so that they still remain hard. What I am asking is whether there is a problem that remains hard on $every$ dense, polynomial-time recognizable class. Regarding the issue of naturalness, I do not have the answer in general, but I can imagine that something could possibly be constructed via diagonalization. Of course, a natural problem would be much more attractive.  
> **username_1**: Perhaps it would be interesting to ask if there are polynomial time candidates ... for example a graph with $5n/2$ nodes built with a $K_n$ (to satisfy density constraint) linked to a caterpillar with a central path of length $n$ and with $n/2$ nodes of the central path having a single "hair" (to get many non-isomorphic graphs).  
> **username_2**: Do you allow weights? If you do, it is easy to create problems which remain NP-complete even restricted to the class of complete graphs. And taking a fraction of edges off of the graph would make the number of graphs in the class grow exponentially.  

---

## 1 answers

### Answer by username_5 on 2014-02-27. Score: 2 | Accepted answer

The definition of "natural" is a bit fuzzy, but there's a trivial reason the answer here is likely "no". Suppose to the contrary that there is such a problem, $P$. If $P$ only acts on the first component of the provided graph, then $P$ is easy on the class of graphs where the first component is an instance of $P$ and the second component encodes a certificate of $P$ holding on the first component. Further, this class of graphs is polytime recognizable. Indeed, the same holds true if we can designate a portion of the graph as a "this is a certificate and not part of the problem component", in the sense that we can sneak this certificate in without affecting the true answer.

Most "natural" problems, as far as I can tell, allow for the designation of such a piece of the graph. Here are a few examples

* Max Clique: just ensure that the certificate portion of the graph does not have a large clique (eg. encode it using a matching)
* Hamiltonian Path: the tail node is replaced by a certificate graph which has an easy-to-find Hamiltonian path of its own
* Hamiltonian Circuit: same as Hamiltonian path except *some* designated vertex is replaced with a certificate graph containing a Hamiltonian cycle
* Max Cut: this doesn't affect the solution as long as there are no edges to the rest of the graph, so we just ensure that the max cut here is easy to find (eg. we encode using a matching)
* Vertex cover: the certificate is again encoded by a matching

We ensure that the certificate portion of the graph is designated as such, so to not lose it in the rest of the graph (though designating them implicitly via the graph structure is probably easy enough for most "natural" problems).

Since NP-complete problems cannot be sparse unless $P=NP$ (Mahaney's theorem), neither can this construction, satisfying your non-triviality constraint.


---

