The Art Gallery Guardian

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.


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

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

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

D(v)=min(v,u)Amax(D(u)w((v,u)),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 (R{},min,,,0)(\mathbb{R}\cup \{\infty\},\min,\otimes,\infty,0), where ab=max(ab,0)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.

(ab)c=max(min(a,b)c,0)=max(min(ac,bc),0)=min(max(ac,0),max(bc,0))=(ac)(bc)\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 kk-closed for any graph GG for kk depending on GG and ww. 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].


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