Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance:
Input: A digraph $G=(V,E)$ and two nodes $u,v \in V$
Question: Is there a path in $G$ from $u$ to $v$?
Can we say this problem is NP-Complete problem since the digraph have only two nodes that they have a path from one another and this makes it be a Hamiltonian Path.
Hints are appreciated!

  • $\begingroup$ @FrankW the question part was is there a path in $G$ from $u$ to $v$ $\endgroup$
    – fudu
    Mar 13 '14 at 14:08
  • $\begingroup$ I still don't get what you want to know. The problem you describe is exactly Hamiltonian Path, which is NP-complete but does not restrict the size of the given graph. So where does "since the digraph have only two nodes" come from? And what is the relation to your first sentence? $\endgroup$
    – FrankW
    Mar 13 '14 at 14:54
  • $\begingroup$ @FrankW I had a wrong understanding that the number of nodes could affect the problem to be NP-Complete problem or not. Now I get the whole picture. :D $\endgroup$
    – fudu
    Mar 13 '14 at 15:05
  • $\begingroup$ I don't really understand the downvote. Sure, having properly understood the basics of complexity, this question doesn't come up, but it seems to me that this is a fair enough question to ask for someone who is just starting to learn the subject. $\endgroup$
    – G. Bach
    Mar 13 '14 at 16:57

When a problem is NP-complete, it doesn't necessarily mean that all instances are hard to solve. It just means that enough instances are hard to solve that, if you could solve this problem efficiently, you could do the same for all problems in NP. Enough, in this case, does mean infinitely many1 and that should lead you towards looking at large inputs if you want to find hard cases.2

For example, the fact that 3-SAT is NP-complete doesn't mean that you would have any difficulty telling me whether the formula $(X\vee Y\vee Z)$ is satisfiable. In your example, you've observed that, for a graph with a single edge, that edge is a Hamiltonian path. That doesn't mean that it's hard to tell whether a graph has a single edge, or that it's easy to compute Hamiltonian paths on all graphs.

1 Probably infinitely many, anyway. If P = NP, there wouldn't be any "hard" instances of NP-complete problems.

2 Note that, strictly speaking, there's no such thing as a single "hard case" since, if we restrict to that single input, the problem can be solved in constant time. Properly, I mean a whole infinite class of instances such that it's "hard" to write an algorithm that answers the problem on that whole class of inputs.

  • $\begingroup$ Very illustrative; I wonder why there isn't a big book collecting such illustrative instructive examples for basic principles in CS (or maybe I just don't know it). $\endgroup$
    – G. Bach
    Mar 13 '14 at 17:00

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.