8

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.

Andras Farago
  • 11,396
  • 37
  • 70
  • 1
    Finding a 4-coloring of a 3-colorable graph is NP-hard. – Mohammad Al-Turkistany Feb 11 '14 at 17:38
  • 1
    Does this answer your question? NP-hard problems on paths – Mohammad Al-Turkistany Feb 11 '14 at 17:43
  • 1
    why do you ask for a "natural" problem? do you have the answer in general? – Denis Feb 11 '14 at 17:57
  • 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 Feb 11 '14 at 18:11
  • @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 Feb 11 '14 at 18:41
  • @dkuper: you're right, I didn't notice it! :-S – Marzio De Biasi Feb 11 '14 at 18:56
  • This might interest you: http://www.sciencedirect.com/science/article/pii/0304397576900591 – Denis Feb 11 '14 at 19:04
  • @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 Feb 11 '14 at 20:32
  • 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 Feb 12 '14 at 18:08
  • 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 Feb 27 '14 at 02:57

1 Answers1

2

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.

Yonatan N
  • 1,642
  • 14
  • 22