d4-conf-atal-2023-0533 (d4-conf-atal-2023-0533)

Given a weighted road graph \(G\), ordered PoI categories \(V_1,\ldots,V_k\), and a finite support \(T\) of origin–destination types \(t=(o_t,d_t)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), find a valid itinerary \(P=(v_1,\ldots,v_k)\) minimizing \(J_\mu(P)=\sum_{t\in T}\mu_t\left[d_G(o_t,v_1)+\sum_{j=1}^{k-1}d_G(v_j,v_{j+1})+d_G(v_k,d_t)\right]\).

Let \(G=(V,E,w)\) be a finite connected undirected road graph with \(n=|V|\), \(m=|E|\), and nonnegative binary-rational edge lengths; let \(d_G\) denote shortest-path distance. There are \(k\geq 1\) ordered, nonempty, pairwise disjoint PoI categories \(V_1,\ldots,V_k\subseteq V\).
A society is given by its support: a list \(T\) of \(\tau\) distinct origin–destination types \(t=(o_t,d_t)\in V\times V\), each with positive binary-rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length.
A valid itinerary is a single common tuple \(P=(v_1,\ldots,v_k)\) with \(v_j\in V_j\); travel between successive designated stops uses shortest paths. Incidental visits to other PoIs and repeated road vertices are allowed. Any minimizing itinerary is acceptable.
Minimize \(J_\mu(P)=\sum_{t\in T}\mu_t\bigl[d_G(o_t,v_1)+\sum_{j=1}^{k-1}d_G(v_j,v_{j+1})+d_G(v_k,d_t)\bigr]\).

Is exact minimization of \(J_\mu\) solvable in time polynomial in \(n,m,k,\tau,L\), or is it NP-hard?

For a finite list of agents, minimizing the unweighted sum of their travel distances over common itineraries with prescribed category order admits a polynomial-time algorithm.

Exact minimization is polynomial-time solvable, including when the masses are arbitrary positive binary-rational numbers. The key is that the travel cost between designated stops is common to all types.

• Separate the objective.

Define
\(A(v)=\sum_{t\in T}\mu_t d_G(o_t,v)\) and
\(B(v)=\sum_{t\in T}\mu_t d_G(v,d_t)\).

Since \(\sum_{t\in T}\mu_t=1\), every valid itinerary satisfies
\[ J_\mu(v_1,\ldots,v_k) =A(v_1)+\sum_{j=1}^{k-1}d_G(v_j,v_{j+1})+B(v_k). \]
Thus the society affects only the costs at the first and last designated stops. This identity uses a single common itinerary, exactly as required.

• Compute an optimal itinerary by dynamic programming.

First compute all shortest-path distances. For \(v\in V_1\), set \(F_1(v)=A(v)\). For each \(j\in\{2,\ldots,k\}\) and \(v\in V_j\), set
\[ F_j(v)=\min_{u\in V_{j-1}}\bigl(F_{j-1}(u)+d_G(u,v)\bigr). \]
Return a tuple attaining
\[ \min_{v\in V_k}\bigl(F_k(v)+B(v)\bigr), \]
recording a minimizing predecessor in each recurrence and tracing backward.

To prove correctness, interpret \(F_j(v)\) as the minimum of
\(A(v_1)+\sum_{i=1}^{j-1}d_G(v_i,v_{i+1})\)
over all choices \(v_i\in V_i\) with \(v_j=v\). For \(j=1\), this is precisely the initialization. For \(j\geq2\), every such tuple has a predecessor \(u=v_{j-1}\in V_{j-1}\). Once \(u\) is fixed, its minimum prefix cost is \(F_{j-1}(u)\), and extending to \(v\) adds exactly \(d_G(u,v)\). Conversely, every minimizing prefix can be extended to \(v\). This proves the recurrence by induction. Adding \(B(v_k)\) gives the original objective by step 1.

All minima exist because the categories are finite and nonempty. Connectivity makes every distance finite. The same argument covers \(k=1\), where the answer minimizes \(A(v)+B(v)\) over \(V_1\). Incidental PoI visits and repeated road vertices impose no additional constraints under the stated premises.

• Verify polynomial bit complexity.

Write each edge length as \(w_e=p_e/q_e\), with integer \(p_e\geq0\) and integer \(q_e>0\), and each mass as \(\mu_t=r_t/s_t\), with positive integer numerator and denominator. Let
\(D=\prod_{e\in E}q_e\) and \(M=\prod_{t\in T}s_t\), taking an empty product to be \(1\).

Both products have bit length \(O(L)\): the logarithm of each product is the sum of the logarithms of its input denominators. Define integer edge lengths \(a_e=Dw_e\) and integer masses \(b_t=M\mu_t\). Then \(\sum_t b_t=M\).

Let \(\delta(x,y)\) be the shortest-path distance with edge lengths \(a_e\). Scaling every walk’s length by \(D>0\) preserves its ordering, so \(\delta(x,y)=D\,d_G(x,y)\). Consequently,
\[ DM\,J_\mu(P) =\sum_t b_t\delta(o_t,v_1) +M\sum_{j=1}^{k-1}\delta(v_j,v_{j+1}) +\sum_t b_t\delta(v_k,d_t). \]
We can therefore perform the entire algorithm using integers: use endpoint costs \(\sum_t b_t\delta(o_t,v)\) and \(\sum_t b_t\delta(v,d_t)\), and transition costs \(M\delta(u,v)\). Multiplication of the objective by the positive constant \(DM\) preserves all minimizers.

Set \(H=\max(\{1\}\cup\{a_e:e\in E\})\). Nonnegative lengths imply that deleting cycles cannot increase a walk’s length. Hence every shortest-path distance is attained by a simple path and is at most \(nH\). The bit length of \(H\) is \(O(L)\).

Each scaled endpoint cost is at most \(MnH\), because \(\sum_t b_t=M\). Every dynamic-programming value and every candidate final cost is at most \(M(k+1)nH\), so their bit lengths are \(O(L+\log n+\log(k+1))\). Thus all arithmetic and comparisons have polynomial cost.

For example, Floyd–Warshall computes the integer distances with \(O(n^3)\) additions and comparisons. Its recurrence considers whether a shortest path uses the newly allowed internal vertex; cycle deletion justifies choosing a simple shortest path, including when some edges have length zero. Computing the endpoint costs takes \(O(\tau n)\) arithmetic operations. The dynamic program takes
\(O\bigl(\sum_{j=2}^k |V_{j-1}||V_j|\bigr)\subseteq O(kn^2)\)
operations. Constructing the scaled integers and recovering the tuple also take polynomial time.

Therefore, the complete algorithm runs in time polynomial in \(n,m,k,\tau,L\). It processes the support directly; rational masses do not require expanding the society into a potentially enormous list of agents.

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned task correctly: exact minimization is polynomial-time solvable in \(n,m,k,\tau,L\). The argument establishes both correctness and polynomial bit complexity. No major or minor issues were found.

• Objective decomposition is valid.

Because every type uses the same designated stops, the internal travel cost is independent of \(t\). Its coefficient after summing over types is \(\sum_{t\in T}\mu_t=1\). Therefore the displayed decomposition into \(A(v_1)\), internal distances, and \(B(v_k)\) is exact. There is no unjustified replacement of a common itinerary by separate type-specific itineraries.

• The dynamic-programming recurrence is correct.

The stated interpretation of \(F_j(v)\) supplies a precise invariant. The initialization establishes it for \(j=1\). For each later layer, partitioning feasible prefixes by their penultimate stop accounts for every feasible prefix. The added cost depends only on that stop and \(v\), so the recurrence follows from the invariant.

The converse extension argument establishes attainability, not merely a lower bound. Recording predecessors therefore recovers a valid minimizing tuple. Adding \(B(v_k)\) yields the full objective.

• Feasibility and edge cases are addressed.

Finite, nonempty categories ensure that each minimum exists. Connectivity ensures finite distances. The explicit treatment of \(k=1\) is correct, with no transitions required. Zero-length edges, incidental PoI visits, and repeated road vertices do not invalidate the recurrence under the task’s travel conventions.

• The integer scaling is exact and has polynomial encoding size.

The products \(D\) and \(M\) are positive integers whose bit lengths are bounded by the combined bit lengths of their input denominators. Thus their bit lengths are \(O(L)\), even though their numerical values may be large.

Each \(a_e=Dw_e\) and \(b_t=M\mu_t\) is an integer of polynomial bit length. Uniform positive scaling gives \(\delta(x,y)=D\,d_G(x,y)\), and the displayed expression for \(DM\,J_\mu(P)\) is algebraically correct. The integer endpoint and transition costs consequently preserve all minimizers.

• The numerical bounds are sufficient.

Nonnegative edge lengths permit cycle deletion without increasing cost, so a shortest path can be chosen simple. Its length is at most \(nH\); this bound also covers the zero-length path when its endpoints coincide.

Since \(\sum_t b_t=M\), each endpoint cost is at most \(MnH\). A prefix value at layer \(j\) contains one endpoint cost and \(j-1\) transition costs, and the final candidate adds the second endpoint cost. Hence the stated uniform bound \(M(k+1)nH\) is valid. Its bit length is \(O(L+\log n+\log(k+1))\), as claimed.

• The running-time conclusion follows.

Floyd–Warshall applies to these finite graphs with nonnegative integer lengths, including zero-length edges. Its distance computations use polynomially many operations on integers of polynomial bit length. The stated endpoint computation count \(O(\tau n)\) and dynamic-programming count \(O(kn^2)\) are valid upper bounds. Scaling and predecessor recovery likewise require polynomial time.

The algorithm processes the support directly and does not expand rational masses into replicated agents. It therefore answers the requested complexity question for the given encoding.

No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩