d4-conf-ijcai-2021-0375 (d4-conf-ijcai-2021-0375)

Given a finite road graph \(G=(V,E)\), a time horizon, a finite support \(\Theta\) of rider types \(\theta=(o,d,\gamma)\) with rational masses \(\mu_\theta\ge 0\) summing to \(1\), and a fleet with initial locations and capacities measured in normalized mass units, choose feasible vehicle routes and type-level assignments \(x_{\theta p}\ge 0\) to feasible travel plans \(p\), with \(\sum_p x_{\theta p}=\mu_\theta\). Each unit of mass must receive an integral travel plan, assignments must match vehicle routes and respect capacity at every time, and taxi plans have the paper’s taxi cost. What is the complexity of finding a feasible solution minimizing \(\sum_{\theta,p}x_{\theta p}c_\theta(p)+\beta\sum_k T^c_k\), under a stated normalization of fleet supply and route costs?

A society is given by its support: the list of \(\tau\) types \(\theta=(o,d,\gamma)\) with positive masses \(\mu_\theta\), each a binary rational, summing to \(1\); \(\tau\) is the support size, not the number of possible types.
The input includes a finite directed graph \(G=(V,E)\), with waiting allowed at every vertex, and a positive unary-encoded horizon \(H\). Each non-loop edge takes one time step and has distance one; waiting has distance zero. Write \(m=|V|+|E|\).
There are \(K\geq1\) individually listed autonomous vehicles with given initial vertices and common positive binary-rational capacity \(q\) in rider-mass units. Each vehicle follows one integral route over times \(0,\ldots,H\), may move empty, and has unrestricted final location. Fleet supply is \(Kq\), with no fixed supply-to-demand ratio.
All riders are ready at time zero. For every supported type, \(o,d\in V\), \(\gamma\in[0,\gamma_{\max}]\) is rational, and the shortest-path distance \(D_\theta\) from \(o\) to \(d\) is finite and at most \(H\). The rational inputs satisfy \(\gamma_{\max}\geq0\), \(\alpha\geq0\), and \(\beta>0\).
An integral rider plan starts at \(o\) and ends at \(d\) by \(H\). It either takes an unlimited-supply taxi immediately along a shortest path, or waits and traverses every moving edge aboard exactly one fleet vehicle following that same edge at that time. Transfers at a common vertex are instantaneous; taxi and fleet travel cannot be combined.
Types may split among whole plans: \(x_{\theta p}\geq0\) and \(\sum_p x_{\theta p}=\mu_\theta\). At every time, the total mass aboard each vehicle is at most \(q\); vehicle routes themselves cannot split.
Let \(A(p)\) be first arrival time at the destination and \(T^c_k\) the number of moving edges traversed by vehicle \(k\). Set \(c_\theta(p)=(\alpha+\beta+\gamma)D_\theta\) for taxi plans and \(c_\theta(p)=\gamma A(p)\) otherwise. The normalized objective is \(C=\sum_{\theta,p}x_{\theta p}c_\theta(p)+\beta\sum_{k=1}^K T^c_k\): vehicle fuel costs are charged per whole vehicle, without a further population factor.

Is deciding whether a feasible allocation has \(C\leq B\), for a binary-rational input threshold \(B\), in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? State running times in \(m,\tau,K,H,L\), where \(L\) is the total input bit length.

The finite-rider optimization problem is \(\mathrm{NP}\)-hard, even with one autonomous vehicle capable of carrying every rider, a common destination, and zero rider time values ([Iwase, Stein and Gerding](https://arxiv.org/pdf/2105.11292)).
No verified complexity result for exactly the continuous formulation above was identified.

1. Result

The decision problem is \(\mathrm{NP}\)-complete. Hardness holds already when \( K=1,\quad q=1,\quad \beta=1,\quad \gamma_{\max}=0 \), and every supported type has the same destination, equal to the vehicle’s initial vertex.

For fixed vehicle routes, the continuous rider allocation can be computed in \(\operatorname{poly}(m,\tau,K,H,L)\) time. Enumerating vehicle routes gives an exact deterministic algorithm with running time
\[ (m+1)^{KH}\operatorname{poly}(m,\tau,K,H,L). \]
Thus a polynomial-time algorithm for unrestricted inputs would imply \(\mathrm{P}=\mathrm{NP}\).

2. Hardness reduction

We reduce from directed Hamiltonian cycle, whose \(\mathrm{NP}\)-completeness is established in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

We may restrict the source problem to strongly connected, loopless directed graphs with at least two vertices. Indeed, a graph admitting a Hamiltonian cycle is strongly connected. A graph that is not strongly connected can therefore be replaced by a fixed strongly connected no-instance: the three-vertex path with both orientations of each edge. Removing loops does not affect Hamiltonian cycles on at least two vertices. The finitely many smaller instances can be decided directly.

Let \( F=(W,J) \) be such a source instance, with \( n=|W|\geq2 \). Choose a vertex \( w\in W \), and enumerate the remaining vertices as \( v_1,\ldots,v_\tau \), where \( \tau=n-1 \).

Use \( G=F \) as the road graph. The single vehicle starts at \( w \). Set
\[ H=n,\qquad K=1,\qquad q=1,\qquad \beta=1,\qquad \gamma_{\max}=0,\qquad B=n. \]

There is one supported type \( \theta_i=(v_i,w,0) \) for each \( i\in\{1,\ldots,\tau\} \).

To ensure that the masses are dyadic rationals, let \( r=2^{\lceil\log_2\tau\rceil} \) and define
\[ \mu_{\theta_i}= \begin{cases} 1/r,&i<\tau,\\ 1-(\tau-1)/r,&i=\tau. \end{cases} \]
These masses sum to \( 1 \), are positive, and satisfy \( \mu_{\theta_i}\geq1/r \). Set
\[ \alpha=r(n+1). \]

Strong connectivity guarantees that every type has finite shortest-path distance, with \( 1\leq D_{\theta_i}\leq n-1<H \). Hence the constructed instance satisfies all input promises.

The construction has polynomial size. Specifically, \( r<2\tau \), \( \alpha=O(n^2) \), the unary horizon has length \( n \), and every mass has \( O(\log n) \) bits.

3. Correctness of the reduction

A Hamiltonian cycle gives an allocation of cost \(\boldsymbol{n}\).

Suppose the source graph has a Hamiltonian cycle
\[ w,u_1,\ldots,u_{n-1},w. \]
The vehicle follows this cycle, picking up the entire mass originating at each visited vertex and delivering everyone to \( w \) at time \( n \).

The onboard mass never exceeds the total population mass \( 1=q \). Every rider has zero time value, and no rider uses a taxi. The vehicle traverses exactly \( n \) moving edges, so \( C=\beta n=n=B \).

An allocation of cost at most \(\boldsymbol{n}\) gives a Hamiltonian cycle.

Suppose a feasible allocation satisfies \( C\leq n \). Sending the entire mass of any type \( \theta_i \) by taxi would alone cost
\[ \mu_{\theta_i}(\alpha+1)D_{\theta_i} \geq \frac{\alpha+1}{r} =n+1+\frac1r >n. \]
All objective terms are nonnegative. Therefore, every type must receive a strictly positive amount of fleet service.

For each \( i \), positive fleet service implies that the vehicle visits \( v_i \) and subsequently visits \( w \). To justify this implication, choose any positive-mass fleet plan of that type. Its first moving edge departs from \( v_i \) aboard the single vehicle. Its first arrival at \( w \) also occurs aboard that vehicle on a moving edge, since \( v_i\neq w \) and waiting cannot change location.

Let \( t_* \) be the vehicle’s last visit to \( w \) within the horizon. The route prefix ending at \( t_* \) starts and ends at \( w \) and visits every other vertex.

Delete all waiting steps from this prefix. The resulting closed walk has vertex sequence \( z_0,\ldots,z_s \), where \( z_0=z_s=w \). Its \( s-1 \) interior positions must contain all \( n-1 \) other vertices. Consequently,
\[ s-1\geq n-1,\qquad\text{so}\qquad s\geq n. \]
On the other hand,
\[ s\leq t_*\leq H=n. \]
Thus \( s=n \). Its \( n-1 \) interior positions contain each vertex other than \( w \) exactly once. The walk is therefore a directed Hamiltonian cycle.

This argument permits arbitrary mass splitting: even a very small positive fleet-served fraction forces the necessary origin visit.

The reduction proves \(\mathrm{NP}\)-hardness for the stated restricted instances.

4. Fixed vehicle routes admit a polynomial-size linear program

Fix integral vehicle routes \( s_{k,0},\ldots,s_{k,H} \). Write each type as \( \theta=(o_\theta,d_\theta,\gamma_\theta) \).

For each type, construct a time-expanded directed network with nodes \( (v,t) \), for \( v\in V \) and \( 0\leq t\leq H \), and a terminal sink. Include:

• Waiting arcs \( (v,t)\to(v,t+1) \).
• For every moving vehicle slot \( (k,t) \), an arc labelled by that vehicle from \( (s_{k,t},t) \) to \( (s_{k,t+1},t+1) \).
• Arrival arcs from \( (d_\theta,t) \) to the terminal sink.

Delete waiting and moving arcs leaving destination nodes. Thus fleet flow terminates upon first arrival at its destination.

Let \( y_\theta\in[0,\mu_\theta] \) denote taxi mass. Require a nonnegative flow of value \( \mu_\theta-y_\theta \) from \( (o_\theta,0) \) to the terminal sink, with flow conservation at every other node.

For every moving vehicle slot, impose the shared capacity constraint
\[ \sum_\theta f_{\theta,k,t}\leq q. \]
Here \( f_{\theta,k,t}=0 \) when that vehicle arc is absent from the type’s network.

Let \( z_{\theta,t} \) be flow on the arrival arc at time \( t \), and let \( M \) be the total number of moving vehicle slots. Impose
\[ \sum_\theta (\alpha+\beta+\gamma_\theta)D_\theta y_\theta +\sum_\theta\sum_{t=0}^{H}\gamma_\theta t\,z_{\theta,t} +\beta M \leq B. \]

Exactness of the formulation.

Every feasible allocation induces these flows: terminate each fleet plan at first arrival, and represent all waiting as waiting at the vertex. Removing onboard waiting cannot increase any vehicle’s load.

Conversely, each type’s time-expanded network is acyclic. Its nonnegative flow decomposes into weighted source-to-sink paths: repeatedly subtract the smallest positive flow along a positive-flow source-to-sink path; each subtraction eliminates an arc, and acyclicity excludes residual circulations. Each path specifies a whole fleet plan, including the vehicle used on every moving edge. Transfers are valid because consecutive arcs meet at the same vertex and time.

The capacity constraints bound onboard mass during each moving step. During waiting steps, everyone may wait outside the vehicle. At integer times, riders may alight and then board instantaneously, consistently with the transfer rule. Arrival-arc costs equal the specified first-arrival costs. Taxi mass uses only the taxi option.

Hence the linear program is feasible exactly when the fixed routes admit an allocation with \( C\leq B \).

The program has \( O\bigl(\tau(H+1)(m+K)\bigr) \) variables and constraints. Its rational coefficients have bit length \( O(L+\log(KH+1)) \). The standard polynomial-time theorem for rational linear-program feasibility therefore applies, giving running time \( \operatorname{poly}(m,\tau,K,H,L) \).

5. Membership and running times

A certificate consists solely of the vehicle routes. Its length is \( O(K(H+1)\log(m+1)) \) bits. Because vehicles are individually listed and \( H \) is unary encoded, this length is polynomial in the input length.

A deterministic verifier checks the route edges and initial vertices, then decides feasibility of the preceding rational linear program in polynomial time. This proves membership in \(\mathrm{NP}\). Combined with the reduction, the decision problem is \(\mathrm{NP}\)-complete.

For an explicit exact algorithm, each vehicle has at most \( m+1 \) choices per time step, including waiting. Enumerating all route profiles and solving their linear programs takes
\[ (m+1)^{KH}\operatorname{poly}(m,\tau,K,H,L) \]
time. Shortest-path distances can be precomputed in \( O(\tau m) \) graph operations.

⟨structured verdict parsed — rendered above⟩

The prover resolves the stated continuous problem: its reduction establishes \(\mathrm{NP}\)-hardness, and its fixed-route linear program establishes membership in \(\mathrm{NP}\). No major or minor mathematical issues were found.

1. Source problem and restriction

The cited source establishes completeness of directed Hamiltonian cycle. The prover uses that result for finite directed graphs, then justifies the additional restrictions itself. [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)

The restriction to strongly connected, loopless graphs with at least two vertices is valid:

• A graph containing a Hamiltonian cycle is strongly connected.
• The proposed replacement graph—the three-vertex path with both orientations—is strongly connected and has no Hamiltonian cycle.
• Removing loops preserves Hamiltonian cycles on graphs with at least two vertices.
• Instances with fewer vertices form finitely many cases that can be handled directly.

These operations preserve the decision answer and take polynomial time.

2. Constructed instance and input promises

The construction uses the support size correctly: there are exactly \(\tau=n-1\) distinct supported types, one for each vertex other than \(w\).

The mass calculations are correct. Since \(\tau\leq r<2\tau\), the last mass satisfies
\[ 1-\frac{\tau-1}{r}=\frac{r-\tau+1}{r}\geq\frac1r. \]
All masses are positive dyadic rationals and sum to one. The case \(\tau=1\) also works: \(r=1\), and the sole mass equals one.

Strong connectivity gives
\[ 1\leq D_{\theta_i}\leq n-1<H=n. \]
Thus the origins and destinations satisfy the distance promise. All other parameters satisfy their required signs and domains.

The size bounds are valid: \(\alpha=r(n+1)=O(n^2)\), the unary horizon has length \(n\), and each mass needs \(O(\log n)\) bits. The reduction therefore produces an instance of polynomial total bit length.

3. Hamiltonian cycle implies a feasible allocation

The proposed route starts at the required initial vertex, traverses \(n\) edges, and finishes within the horizon.

Every rider can wait at its origin until pickup. The vehicle carries at most the total population mass, which is \(1=q\). All riders reach the common destination at time \(n\), use no taxi, and have \(\gamma=0\).

Consequently, the rider-cost contribution is zero and the whole-vehicle fuel contribution is exactly \(n=B\). This direction is correct.

4. Low cost forces service from every origin

The critical bound is correct:
\[ \mu_{\theta_i}(\alpha+1)D_{\theta_i} \geq\frac{\alpha+1}{r} =n+1+\frac1r>n. \]

If a type received no fleet service, all its mass would use taxis, so this bound would contradict \(C\leq n\). Nonnegativity of the other objective terms justifies considering this contribution alone.

The conclusion is precisely that every type receives strictly positive fleet service. The argument does not incorrectly infer that taxis are entirely absent. Arbitrary mass splitting therefore does not undermine this step.

5. Positive fleet service forces the required visits

For each type, a positive-mass fleet plan exists. The construction is loopless and its origin differs from its destination.

The plan’s first moving edge must depart its origin aboard the single vehicle. Its first arrival at \(w\) must likewise occur on a vehicle edge. Waiting cannot produce either change of location.

Thus the vehicle visits every origin and subsequently visits \(w\). Its prefix through its last visit to \(w\) starts and ends at \(w\) and contains every other vertex. This implication is valid.

6. The route prefix is a Hamiltonian cycle

Deleting waiting steps preserves the moving edges and produces a closed directed walk.

Its \(s-1\) interior positions contain all \(n-1\) vertices other than \(w\), giving
\[ s\geq n. \]
Every moving edge consumes a time step, so
\[ s\leq t_*\leq H=n. \]
Hence \(s=n\). The interior positions must contain each other vertex exactly once, with no additional repetition or interior occurrence of \(w\).

The extracted walk is therefore a directed Hamiltonian cycle. This completes both directions of the reduction.

7. Fixed-route linear program

The time-expanded formulation correctly represents the allowed fleet plans:

• Waiting arcs allow riders to remain at vertices.
• Vehicle-labelled moving arcs preserve the identity of the vehicle used on each edge.
• Shared constraints sum all types’ mass on each vehicle’s moving slot.
• Arrival arcs record first-arrival time.
• Removing outgoing travel and waiting arcs at destination nodes prevents subsequent travel from changing that interpretation.
• The separate taxi variable prevents taxi and fleet travel from being combined.

The objective inequality also charges vehicle fuel correctly: \(\beta M\) depends on the fixed whole-vehicle routes, including empty movements.

The standard terminology “flow of value” specifies the source and sink balances; conservation applies to the remaining nodes.

8. Exactness and capacity at every time

The forward direction is valid. Truncating a rider’s plan at first arrival preserves its specified cost and only removes later vehicle occupancy. Representing onboard waiting as waiting outside also cannot increase any load.

The converse decomposition is valid because every ordinary arc advances time and every arrival arc enters the terminal sink. The network is acyclic, so the stated subtraction procedure leaves no residual circulation and produces whole source-to-sink paths.

Consecutive vehicle arcs meet at a common vertex and time, as required for transfers. During waiting intervals, riders can remain outside vehicles. At integer times, alighting before boarding avoids transient overload and is consistent with instantaneous transfers.

Thus constraints on moving slots suffice for the feasible allocations reconstructed by the prover.

The destination-equals-origin case is also covered: flow can use the arrival arc at time zero, with first-arrival cost zero.

9. Linear-program size and theorem applicability

The variable and constraint bound
\[ O\bigl(\tau(H+1)(m+K)\bigr) \]
is valid. It covers time-expanded nodes, waiting arcs, vehicle-slot arcs, arrival arcs, taxi variables, and shared capacity constraints.

The coefficient bit bound is also valid. The only additional arithmetic involves rational input parameters, bounded integer distances and times, and \(M\leq KH\).

The invoked theorem applies to an explicitly encoded finite system of rational linear equalities and inequalities and decides feasibility in polynomial time in its total binary encoding length. These hypotheses hold here; no integrality restriction remains in the fixed-route allocation problem. The polynomial-time linear-feasibility result is standard. [Nemirovski’s treatment, Section 4.2](https://www2.isye.gatech.edu/~nemirovs/Lec_EMCO.pdf)

10. Membership and running times

The route certificate has the claimed polynomial size because vehicles are individually listed and \(H\) is unary encoded. A deterministic verifier can check the routes and then run the polynomial-time linear-program feasibility algorithm. A separate rider-allocation certificate is unnecessary.

The enumeration bound
\[ (m+1)^{KH}\operatorname{poly}(m,\tau,K,H,L) \]
is a valid upper bound: each vehicle has at most \(m+1\) possible transitions per step, including waiting.

Shortest-path preprocessing in \(O(\tau m)\) graph operations is valid for unit-length moving edges.

Feedback

No repair or additional clarification is required to establish the claimed complexity classification. The output proves \(\mathrm{NP}\)-completeness for the continuous formulation itself, including the stated restricted instances.

⟨structured verdict parsed — rendered above⟩