1. ## 13:1912th Aug 2013

### The minimum weight path of length $k$ in a DAG with Monge property

Problem

Consider we have a complete directed acyclic graph of $n$ vertices, such that the topological sort order is $v_1,\ldots,v_n$. There is a weight function $w(v_i,v_j)$, such that it has the Monge property, i.e. $w(v_i,v_j) + w(v_{i+1},v_{j + 1}) \leq w(v_i,v_{j+1}) + w(v_{i+1},v_{j})$ holds for all $1 < i + 1 < j \leq n$.

The weight of a path is the sum of the weight of all edges in the path. We want to find a path of length $k$ from $v_1$ to $v_n$, such that the weight is minimized.

The function would have the signature minWeightKLinkedPath :: (Integral a, Num b)=>a->a->(a->a->b)->[a]. The input is $n$, $k$, $w$ and the output is a minimum weight path of length $k$.

Solve the problem in $O(kn)$ time.

Hint

There is an algorithm to solve it in $O(k(n+m))$ time on stackoverflow, which can be modified to run in $O(kn^2)$ time.

Apply the technique in the talk Revisiting The Monge Property. The exercise on totally monotone matrices already implemented the subroutine!

Extensions

We can actually implement the most general form of the problem in Revisiting The Monge Property, and also reduce the memory usage from $O(kn)$ to $O(n)$. Looks like no one has done it with Haskell yet.

Applications

Consider the linear partition problem that got featured on hacker news. It can be reduced to this problem and produce a $O(kn)$ time solution. In the application $k$ is just $cn$ for some constant $c$, thus in theory there is a even better (in theory) solution that takes $n2^{O(\sqrt{\log k \log \log n})}$ time discovered by Schieber.

# Solution

minWeightkEdgePath :: (Ord a, Num a) => Int -> Int -> (Int -> Int -> a) -> [Int]
minWeightkEdgePath k n w = backtrack (k-1) n
where
backtrack (-1) _ = []
backtrack x y = y':backtrack (x-1) y'
where y' = snd (d!(x,y))
d = array ((0,0),(k-1,n)) [ ((i,j), f i j) | i<-[0..k-1],j<-[0..n]]
f 0 i = (w 0 i,0)
-- uncomment the following line to use the slower algorithm
-- f k i = minimum [(m k j i, j)|j<-[0..n]]
f k i = (m k j i,j)
where j = p!(k,i)
p = array ((1,0),(k,n)) [((z,i),t) |z<-[1..k],(i,t)<-zip [0..n] (columnMinima (m z) (n+1) (n+1))]
m k j i = fst (d!(k-1,j)) + w j i