3
$\begingroup$

Given a directed multigraph with $n$ groups of edges and without cycles, can we find the path that minimizes the largest of the sum of weights of each group? All weights are non-negative integers in the range 0..30,000.

Let me put an example for $n=2$ groups to understand it better:

multigraph example

If we were to find the shortest path from s to t of this multigraph, that would be easy. Just run a Floyd-Warshall algorithm and in case there is more than 1 edge for a pair of vertices, get the one with lowest weight. The shortest path in this case would be getting all the red edges (s-1-2-t)

This would give us 2 groups with following weights:

  • Blue: 0
  • Red: 5+5+5 = 15

So the largest of this groups is max(0,15) = 15


But in this problem, we want to minimize the largest of the sum of weights of the two groups, so the path that minimizes this in this example is s-1-2-t (red-red-blue).

This would give us 2 groups with following weights:

  • Blue: 10
  • Red: 5+5 = 10

So the largest of this groups is max(10,10) = 10


I guess this problem is NP-hard, because the partition problem can be reduced to this problem. Given an instance of partition, i.e., a multiset $S$ with $k$ elements, just build a graph with $k+1$ vertices and two edges between each pair of consecutive vertices (both edges having weight equal to the corresponding element of $S$; one red, and one blue). Or, you can reduce $n$-way multi-way partition to this problem. Again, build a graph with $k+1$ vertices, and between each pair of consecutive vertices add $n$ edges (one for each group in the partition problem) with weights equal to the numbers in the multiset. Here is a diagram that tries to explain this reduction:

k-partition reduction

But just like there is an easy greedy approximation for the partition problem, there might be something simple for this problem aswell. To be honest, I don't even know how to approach this problem. Any ideas?

And even though it would be great to have a general case approximation, an approximation for the case where n=2 groups would be enough for me right now.

$\endgroup$
2
$\begingroup$

At least for the case $k=2$, there is an efficient algorithm to solve your problem. Suppose all weights are integers in the range $0..\alpha$. Then there is an algorithm whose running time is $O(\alpha VE \log^2(\alpha V))$. In your case, $\alpha=30,000$.

How does this algorithm work? I'll show that, when $k=2$ and when the solution is known to be at most $\beta$, there is an algorithm with running time $O(\beta E \log (\beta V) \log \beta)$. It's easy to see that we must have $\beta \le \alpha V$, so this will imply the claimed result (using the fact that $\log(\alpha V^2) \le 2 \log(\alpha V) = O(\log (\alpha V))$.

The algorithm works by reducing to the decision version of the problem. Given an instance of the problem and a proposed $\gamma$, we test whether there exists a solution that is at most $\gamma$ (i.e., a path from $s$ to $t$ using red edges that total at most $\gamma$ and blue edges that total at most $\gamma$). Then we do binary search on $\gamma$. This will require $O(\log \beta)$ solutions of the decision problem, so it suffices to solve the decision problem in $O(\beta E \log (\beta V))$ time.

How do we do that? We make $\gamma+1$ copies of each vertex $v$; call these copies $(v,0)$, $(v,1)$, ..., $(v,\gamma)$. Intuitively, the new vertex $(v,i)$ corresponds to a state that can be reached if you can reach vertex $v$ from the starting point along a path where the sum of the blue edges is at most $i$. Now we'll construct a new graph on these $(\gamma+1)V$ vertices as follows. For each blue edge $u \to v$ with weight $w$ in the original graph, we add edges $(u,i) \to (v,i+w)$ for each $i$. For each red edge $u \to v$ in the original graph, we add edges $(u,i) \to (v,i)$ for each $i$.

Once this larger graph is constructed, we check whether there exists a path from $(s,0)$ to any $(t,i)$ with length at most $\gamma$. This can be done using Dijkstra's algorithm. Since the larger graph has $O(\gamma V)$ vertices and $O(\gamma E)$ edges, the running time of Dijkstra's algorithm in this graph will be $O(\gamma E \log (\gamma V))$. Since $\gamma \le \beta$, the claimed result follows.

This doesn't contradict your NP-hardness result, as your NP-hardness result uses very large integer weights, while the running time of this algorithm is proportional to the weights themselves (rather than to the number of bits needed to represent the weights). Or, to put it another way, this algorithm is a pseudopolynomial time algorithm, but not a fully polynomial time algorithm.

$\endgroup$
  • $\begingroup$ Sorry it took so long to answer, been quite busy lately. Worked like a charm for my case. Thanks! $\endgroup$ – Ivan Feb 16 '17 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.