您可以在多项式时间内将一个正加权的DAG转换为非加权DAG吗？

Question

给定一个正加权的dag（定向循环图）$ d =（v，e）$，您可以通过用重量$ w（e）= x $转换为x non的每个边缘来创建一个新的非加权dag $ d'$ - 加权边缘和顶点？我相信这将需要$ o（| e |+w）$时间，其中$ | e | $是边缘的数量，$ w $是所有边缘的总重量。我担心的是我是否可以包括此权重变量，并且仍然认为该算法是多项式时间。

（注意：此算法可能适用于所有正加权图，而不仅仅是DAG。）

Answer 1

我相信这将有资格成为伪多项式的时间。看 http://en.wikipedia.org/wiki/pseudo-polynomial_time.

这个想法是，通常我们表示输入的字符串长度（位）表示的函数的时间复杂性。因此，给定$ w $的固定（或至少有界）值，您的算法在多项式时间内运行。

要遵循算法，如果您对每个边缘执行$ o（| w |）$操作，则执行$ o（2^{b}）$操作，其中$ b $是重量的二进制代表的长度。这意味着总体而言，该算法以$ o（| e | 2^{b_ {max}}）$运行，其中$ b_ {max} $是最大的边缘重量的长度。

总而言之，如果您将上限固定在边缘重量上，则$ b_ {max} $将变为常数，并且算法在线性时间内运行，但是如果允许不限制边缘权重，则算法是指数的。

这是我们在处理数值输入时看到的一种常见模式。背包问题以及考虑两个素数的产物，面临同一问题。