# Why is a directed graph not NP complete

Let's say I have a PATH as so...

$$PATH = {G, s, t}$$

Where G is a directed path from $s$ to $t$. Apparently this is considered not NP-Complete. I fail to see why. Can someone explain?

• The term "NP-complete" is used about certain decision problems, and you don't seem to be describing any decision problem at all ... – hmakholm left over Monica Nov 28 '17 at 6:47

NP-completeness is a property of decision problems, not graphs or paths. I'm going to guess and say that $PATH$ refers to the question of whether a directed path exists from $s$ to $t$ in the graph $G$. This can be done with e.g. a depth first search, which has time complexity $O(|V|+|E|)$, polynomial in the number of vertices. Based on current understanding of complexity theory, problems that can be solved in polynomial time are not NP-complete, because that would mean problems that are widely considered unsolvable in polynomial time could be reduced to $PATH$ in polynomial time and then solved in polynomial time.