# Is the gas enough?

I have been trying to use the more general frameworks when I encounter dynamic programming questions, so I can demonstrate the power of abstraction later on.

Problem1

Let $$D=(V,A)$$ be a directed acyclic graph. $$w(e)$$ is the weight of an arc. A $$s-t$$ path $$e_1,\ldots,e_m$$ is called a $$\alpha$$-deficient path if $$\sum_{i=1}^k w(e_i) + \alpha \geq 0$$ for all $$1 \leq k\leq m$$. Find the smallest $$\alpha$$, such that there is a $$\alpha$$-deficient $$s-t$$ path.

One can view this problem as how much gas would one require to travel from $$s$$ to $$t$$. If one knows how much gas one can gain or lose between arcs.

Let $$D(v)$$ be the value of the minimum deficiency path from $$v$$ to $$t$$, and $$D(t)=0$$.

$D(v) = \min_{(v,u)\in A} \max(D(u)-w((v,u)),0)$

Because the graph is acyclic, there is a nice ordering allowing us to compute this nicely.

Note this is exactly the best weight problem[1] under the semiring $$(\mathbb{R}\cup \{\infty\},\min,\otimes,\infty,0)$$, where $$a \otimes b = \max(a-b,0)$$.

One should prove it's a semiring before using it. Everything seems obvious except the distributive property of the $$\otimes$$ operation. Here is a proof for one of the two distributive laws, the other is left as an exercise to the reader.

\begin{align*} (a\oplus b) \otimes c &= \max(\min(a,b)-c,0)\\ &= \max(\min(a-c,b-c),0)\\ &= \min(\max(a-c,0),\max(b-c,0))\\ &= (a \otimes c) \oplus (b \otimes c) \end{align*}

Can we extend the problem to directed graph with cycles? Yes. This semiring has the property that it is $$k$$-closed for any graph $$G$$ for $$k$$ depending on $$G$$ and $$w$$. It means we can't keep going though a cycle and keep producing better solutions. We can run a generic single source shortest distance algorithm[2].

# References

[1] L. Huang, Advanced dynamic programming in semiring and hypergraph frameworks, (2008).

[2] M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, J. Autom. Lang. Comb. 7 (2002) 321–350.

Posted by Chao Xu on 2014-02-25.
Tags: .