Orientation with shortest round trip

Definitions and mathematical statement

A finite mixed graph consists of vertices $V$, fixed directed arcs $A$, and undirected edges $E$. Each edge and arc has a nonnegative rational length. An orientation selects a direction for every member of $E$ and leaves every arc in $A$ unchanged. For a resulting digraph $D$, let $d_D(u,v)$ be the length of a shortest directed path, with value $\infty$ if no such path exists.

Given distinct vertices $s,t$, can one compute in polynomial time an orientation minimizing \[ d_D(s,t)+d_D(t,s), \] or determine that no orientation permits travel in both directions? Polynomial time is measured against the graph description and binary encoding of the lengths. An optimum orientation and two realizing paths provide a concrete output.

Each undirected edge receives one permanent direction, not a separate direction for the outward and return trips. The two paths may share vertices and may reuse a fixed arc in the same direction; no additional disjointness condition is imposed. Shortest-path distances in the original mixed graph, obtained by temporarily allowing an undirected edge both ways, need not be simultaneously realizable after orientation. The objective minimizes their sum, rather than requiring either trip to retain its individually best possible length. The fixed directed arcs distinguish this problem from orienting a wholly undirected graph.

Short English statement

Can one efficiently orient the undirected edges of a mixed graph to minimize the combined shortest outward and return distances between two vertices?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000061 (AMR-029-0061), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Orientation with shortest round trip. Original source indexed by AMR-029-0061. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Orientation with shortest round trip. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Orientation_with_shortest_round_trip.