Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?

Question

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

Answer 1

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.