2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are the variables you are looking at when talking about polynomial or exponential running time? $\endgroup$ – John Habert Mar 15 '14 at 3:43
1
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ Each vertex can have at most $V-1$ outgoing edges, if we are excluding loops and multiple edges. So at most $O(V)$ edges will be checked on each iteration of the loop. $\endgroup$ – ml0105 Mar 15 '14 at 4:27
  • $\begingroup$ Just being strict with the problem description and crude enough with the bounds to show polynomial time -- as it says all edges are checked on each iteration (obviously, this is not necessary and no sane implementation would do that). Also, this analysis easily lends itself to multiple edges + loops, just by noting the maximum number of edges is bounded above by maximum number of edges going out of a vertex * N^2 (in this case anyway, multiple edges could be combined to 1 edge depending on implementation - easy in adjacency matrix,harder in adjacency list form unless tracked with each edge). $\endgroup$ – Batman Mar 15 '14 at 6:01
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

Be careful. Complexity people tend to talk loosely about "polynomial" to mean that the function is bounded by a polynomial, essentially bounded by a power of $n$, and "exponential" to mean functions that are not bounded by a polynomial. Cases in point are $c^n$, but also $n!$ or $e^{n^2}$, both of the last two grow even faster than exponential. But there are also functions like $n^{\log n}$ in this bunch, this one grows faster than any fixed power of $n$ (the exponent grows) but slower than $c^n$ for any $c > 1$ (compare their logarithms when $n \to \infty$)

$\endgroup$

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.