2
$\begingroup$

Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? I believe this would take $O(|E|+W)$ time where $|E|$ is the number of edges and $W$ is the total weight of all edges. My concern is whether I can include this weight variable and still consider this algorithm to be in polynomial time.

(NOTE: This algorithm may apply to all positively weighted graphs, not just DAGs.)

$\endgroup$
3
$\begingroup$

I believe that this would qualify as pseudo-polynomial time. See http://en.wikipedia.org/wiki/Pseudo-polynomial_time.

The idea is that, usually we represent the time complexity as a function of the length of the string (bit) representation of the input. So your algorithm runs in polynomial time, given a fixed (or at least bounded) value for $W$.

To follow your algorithm, if you perform $O(|w|) $ operations for each edge, you perform $O(2^{b})$ operations where $b$ is the length of the binary-representation of the weight. This means that overall, the algorithm runs in $O(|E|2^{b_{max}})$, where $b_{max}$ is the length of the largest edge weight.

In summary, if you fix an upper bound on the edge weights, $b_{max}$ becomes a constant and the algorithm runs in linear time, but if you allow edge weights to be unbounded, the algorithm is exponential.

This is a common pattern we see when dealing with numerical inputs. The Knapsack problem, as well as factoring the product of two primes, face the same issue.

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