Help making the distinction between polynomial and exponential time

Question

I'm trying to understand how problems are categorized in these two classes. I have a specific problem I'm looking at, the directed path problem: PATH = $\{\langle G,s,t \rangle | G$ is a directed graph that has a directed path from $s$ to $t$$\}$. The algorithm that's said to run in polynomial time is described as follows:

1. Place a mark on node $s$

2. Repeat the following until no additional nodes are marked:

3. Scan all the edges of $G$. If an edge $(a,b)$ is found going from a marked node $a$ to an unmarked node $b$, mark node $b$.

4. If $t$ is marked, $accept$. Otherwise, $reject$.

I'm just having trouble understanding how this runs in polynomial time and why it runs in polynomial time. Because it seems like this would be no different than a brute-force search which actually runs exponential.

Any clarification on the problem would be highly appreciated.

Answer 1

There are at most $N^2$ edges in a directed graph on $N$ vertices (think in terms of an adjacency matrix), so each iteration of the loop takes $O(N^2)$ time to scan all the edges and at each edge check if the endpoint of the edge is marked (the check for marked-ness/marking a node is $O(1)$ ). Each iteration must mark at least one more node to continue, so there are at most $N$ iterations (since there are $N$ nodes), so the overall algorithm is at most $O(N^3)$ with the final check for $t$ being marked being $O(1)$.

Answer 2

Thinking about this in terms of an adjacency list might be better. Adjacency matrices are great for examining the structure of a graph, but an adjacency list structure is generally (not always, but generally) better for algorithmic graph theory, such as path finding.

Now let's look at the algorithm in terms of pseudo-code:

$$ function doesPathExist(Digraph graph, Vertex start, Vertex end){

Hashtable markedVertices := new Hashtable
Queue vertexQueue := new Queue

add start to markedVertices
for each edge e in E(start)
    push e.other onto vertexQueue

while vertexQueue is not empty
    Vertex temp := vertexQueue.poll()
    add temp to markedVertices

    for each edge e in E(temp)
       if !vertexQueue.contains(e.other)
            push e.other onto vertexQueue

return hashtable.contains(end) 

} $$

So let's examine the algorithm. The first for loop takes at most V-1 iterations, which is O(V). The while loop takes at most V-1 iterations, if all of the vertices are visited. The inner for loop also takes V-1 iterations. Since the inner for loop is nested in the while loop, the complexity of the while loop is $(V-1) * (V - 1) = O(V^{2})$. So our runtime complexity is $O(V) + O(V^{2}) = O(V^{2})$.

Of course, we could optimize the algorithm some more. But hopefully this helps you see the complexity.

Answer 3

You might want to think about solving this problem with an algorithm that runs in exponential time. Recall that exponential time is $EXP = TIME(2^{n^k})$ for constant $k$, where $n$ is the size of the input. An exponential running time algorithm enters a loop over $n$, and in that loop it enters two more loops over $(n-1)$, and in those loops it enters two more loops over $(n-2)$...

An algorithm with exponential running time can be obtained by converting a non-deterministic algorithm to a deterministic algorithm. Consider the non-deterministic algorithm $N$ that decides whether a path exists from $a$ to $b$ in some graph $G$.

$N = $ "On input $\langle G,a,b \rangle$

1. Non-deterministically select all vertices $S \in \mathcal{P}(V)$, where $V$ is the set of vertices in graph $G$.
2. If $a,b \notin S$ then reject.
3. If $S$ constitutes a valid path from $a$ to $b$, then accept. Otherwise reject."

Step 3 has polynomial running time (we have to check whether the nodes actually are a path from $a$ to $b$), so $N \in NTIME(n^k)$ for constant $k$, but it has at least exponential deterministic running time. Step 1 will branch exponentially in deterministic time: It requires $2^{|V|}$ branches, which is exponential in the size of the input: The input is $|G|$, which is at most $|E| + |V|$ or $|V|^2 + |V|$, because any directed graph has at most $|V|^2$ edges.

Recall that polynomial time is $P = TIME(n^k)$ for constant $k$. The algorithm you have given traverses over all edges multiple times in a BFS like manner, which has running time $O(|E|) = O(|V|^2)$ or $O(n^2) \in TIME(n^k) = P$. It is essentially a BFS where $\Omega(n^2) = O(n^2)$ (best case running time is equal to worst case running time).