Orientation with shortest round trip
Let G=(V,E) be a mixed graph with non-negative edge-lengths and let [math]s,t \in V[/math]. Can we find in polynomial time an orientation where the sum of the lengths of the shortest s-t directed path and the shortest t-s directed path is minimal?
Remarks
The following question is probably easier: Can we decide whether there is an orientation where both the length of the shortest s-t path and the shortest t-s path is the same as in the mixed graph (considering undirected edges as bidirected)?
This is easy in undirected graphs; in fact, Hassin and Megiddo [1] showed that given two node pairs [math](s_1,t_1), (s_2,t_2)[/math], one can decide in polynomial time whether there is an orientation where both the length of the shortest [math]s_1-t_1[/math] path and the shortest [math]s_2-t_2[/math] path is the same as in the undirected graph. In contrast, finding an orientation that minimizes the sum of the lengths of the shortest [math]s_1-t_1[/math] path and the shortest [math]s_2-t_2[/math] path seems to be more difficult. Fenner, Lachish, and Popa [2] presented a PTAS for this problem, and also showed that it can be reduced to the problem of finding Min-sum two edge-disjoint paths. Since Björklund and Husfeldt [3] gave a randomized polynomial-time algorithm for the latter, the orientation problem also has such an algorithm. The complexity is open for more pairs if the number of pairs is fixed, while the decision problem is NP-complete if the number of pairs is not fixed.
It was shown in [4] that one can decide in polynomial time if a mixed graph has an orientation with an [math]s_1-t_1[/math] path and an [math]s_2-t_2[/math] path; however, the complexity of finding an orientation having an [math]s_1-t_1[/math] path and two arc-disjoint [math]s_2-t_2[/math] paths remains open.
A related problem is to find an orientation where the diameter of the graph increases as little as possible. This was addressed by Chvátal and Thomassen [5] for undirected graphs and by Chung, Garey, and Tarjan [6] for mixed graphs.
References
- ↑ R. Hassin, N. Megiddo, On orientations and shortest paths, DOI link, Author link
- ↑ T. Fenner, O. Lachish, A. Popa, Min-Sum 2-Paths Problems, DOI link, author link
- ↑ A. Björklund, T. Husfeldt, Shortest Two Disjoint Paths in Polynomial Time, DOI link, author link
- ↑ E.M. Arkin, R. Hassin, A note on orientations of mixed graphs, DOI link, author link
- ↑ V. Chvátal, C. Thomassen, Distances in orientations of graphs, DOI link
- ↑ F. R. K. Chung, M. R. Garey, R. E. Tarjan, Strongly connected orientations of mixed multigraphs DOI link, Author link
