# 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{aligned} (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{aligned}

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 .
Tags: algorithm.