Paper deep dive
The Influence of Agent Models on the Complexity of Bus Routing
Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 8/19/2026, 3:47:59 AM
Summary
This paper analyzes the computational complexity of the Multi Bus Stop Problem (MBSP), which involves planning a bus route with k stops to minimize costs for agents traveling between sources and destinations. The study examines how different agent cost models (arbitrary, consistent, unit, unweighted) and network structures (general graphs, trees, paths, stars) affect complexity. Key findings include that MBSP is generally NP-hard and parameterized intractable (W[1]- or W[2]-hard) with respect to the number of stops k, even on simple structures like stars or paths, depending on the objective function (energy vs. time) and whether agents can choose to walk directly.
Entities (20)
Relation Signals (18)
Eva Deltl → affiliatedwith → TU Clausthal
confidence 95% · Eva Deltl ... Affiliation: TU Clausthal
Christian Komusiewicz → affiliatedwith → Friedrich Schiller University
confidence 95% · Christian Komusiewicz ... Affiliation: Friedrich Schiller University
Multi Bus Stop Problem → hascomplexity → W[2]-hard
confidence 95% · MBSP with objective function fenergy... is W[2]-hard for k on general graphs
Multi Bus Stop Problem → hascomplexity → NP-hard
confidence 95% · Consequently, MBSP is NP-hard and also intractable in the parameterized sense
Multi Bus Stop Problem → isevaluatedon → NYC-M15
confidence 90% · we optimize the energy objectives on the NYC-M15 bus corridor
Multi Bus Stop Problem → ishardon → Star Graph
confidence 90% · allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars.
Multi Bus Stop Problem → usesagentmodel → Arbitrary Agent Model
confidence 90% · Arbitrary: each agent has its own weight function wa
Multi Bus Stop Problem → usesagentmodel → Consistent Agent Model
confidence 90% · Consistent: all agents share the same weight function.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents' cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents' walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter $k$, the number of bus stops.
Tags
Links
- Source: https://arxiv.org/abs/2608.17733v1
- Canonical: https://arxiv.org/abs/2608.17733v1
Trouble viewing inline? Open PDF directly →
Full Text
90,323 characters extracted from source content.
Expand or collapse full text
The Influence of Agent Models on the Complexity of Bus Routing Eva Deltl OrcID: https://orcid.org/0000-0003-0431-2733 Affiliation: TU Clausthal , Clausthal-Zellerfeld , Germany email: eva.deltl@tu-clausthal.de , Christian Komusiewicz OrcID: https://orcid.org/0000-0003-0829-7032 Affiliation: Friedrich Schiller University , Jena , Germany email: c.komusiewicz@uni-jena.de , Jurek Rostalsky OrcID: https://orcid.org/0009-0009-8818-4337 Affiliation: Friedrich Schiller University , Jena , Germany email: jurek.rostalsky@uni-jena.de , Johannes Schröder OrcID: https://orcid.org/0009-0003-8135-5785 Affiliation: TU Berlin , Berlin , Germany email: j.schroeder.1@tu-berlin.de and Luca Pascal Staus OrcID: https://orcid.org/0009-0004-3020-1011 Affiliation: Friedrich Schiller University , Jena , Germany email: luca.staus@uni-jena.de Abstract. In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents’ cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents’ walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter k, the number of bus stops. 1. Introduction Consider a city planner who wants to establish a bus line to serve transportation demands in a spatial network. In this planning task, numerous objectives and constraints need to be considered to reach a good solution. For example, the number of stops k on the bus line could be limited. Moreover, one would like to find a fast or energy-efficient route connecting these stops, which can be modelled by assigning edge weights wbw_b in the city’s road network. Finally, to model the demands of the population, one would need to know the sources and destinations of the potential users of the bus line, called agents in the following. Ideally, we would also know how difficult or costly it is for each agent a to reach a given bus stop. This can be captured by an individual weight function waw_a for each agent a. These costs may vary drastically as some users may walk, with possibly drastically different walking speeds, while others use bicycles or scooters. With this information and an objective function f for weighing the different costs at hand, we face the following problem. Multi Bus Stop Problem (MBSP) Input: An undirected graph G=(V,E)G=(V,E), a set of agents A with weight function wa:E→ℝ≥0w_a:E _≥ 0 for each a∈Aa∈ A, a bus weight function wb:E→ℝ≥0w_b:E _≥ 0, an integer k∈ℕk , and an objective function f. Task: Compute a bus route B with k stops minimizing f(B)f(B). The first variant of this problem was stated by Reza et al. (23) for the case where the route has only two bus stops and the task is to minimize the cost of the bus route plus the costs of the agents for the commute from source to the start of the bus route and from the end of the bus route to their destination. Since there are only two bus stops which are frequented by all agents, this cost function, later referred to as the energy cost function, can fully incorporate the agent’s travel time into the bus weight function wbw_b. Recently, Proissl and Koch (22) extended Reza et al.’s model by allowing bus routes with up to k stops. In this setting, agents typically use the bus for only part of their journey, so their travel time cannot be incorporated into wbw_b. Proissl and Koch therefore proposed the time objective, which minimizes the total agent travel cost, including access to the boarding stop, travel along the bus route, and access from the exit stop to the destination. As we will see, allowing multiple bus stops makes MBSP computationally hard in most settings. To address this, Proissl and Koch fix, for each agent a, the indices of the stops where a boards and leaves the bus. Under this assumption, optimal bus stop placements can be computed in polynomial time (23; 22). Of course, it seems premature to fix the first and last bus stop for each agent, when it is not clear at all which route the bus will take. Motivated by this observation, we consider models where the agents enjoy greater freedom of choice. More precisely, in our setting the agents choose optimal stops for entering and leaving the bus after the bus stops have been placed. Since the resulting bus route may not be convenient for every agent, we also consider a second variant of each objective function in which agents are not required to take the bus and may instead walk directly to their destinations. Altogether, this yields four objective functions fenergyf_energy, ftimef_time, genergyg_energy, and gtimeg_time, where the latter two functions model the case in which agents can walk directly. With these extensions, MBSP becomes closely related to problems such as k-Median (13) and Facility Location (5; 10), which roughly correspond to the case where the bus weight wbw_b is zero for all edges. Consequently, MBSP is NP-hard and also intractable in the parameterized sense with respect to the number k of bus stops. Thus, algorithms with running time f(k)⋅n(1)f(k)· n^O(1) for input size n are unlikely. We therefore study how the complexity of MBSP depends on two factors: the structure of the underlying spatial network and the mobility model of the agents. In our setting, the input graph represents a transportation network, and agents represent origin-destination demands. We analyze general graphs, trees, paths, and stars, and identify which combinations of network structure and agent model admit efficient exact algorithms. To illustrate that the objectives lead to different spatial stop patterns in practice, we optimize the energy objectives on the NYC-M15 bus corridor, using existing stops as candidates.11 1 To support reproducibility, code, preprocessing scripts, and the processed NYC-M15 instance are available at https://github.com/evamichelle30/ComplexityBusRouting 1.1. Our Results We use paths, stars, and trees as abstractions of common spatial network structures: paths model corridor-like routes, stars model access through a central hub, and trees model branching networks. In a nutshell, we show that natural variants of MBSP are already hard on paths and stars and even for restricted agent mobility models, while combining network restrictions with simple mobility models can lead to tractability; see Figure 1. Theorem 1 Theorem 1 Theorem 4 Theorem 2 fenergyf_energy Theorem 1 Theorem 4 Theorem 3 genergyg_energy Theorem 1 Theorem 8 Theorem 9 Theorem 10 Theorem 1 Theorem 7 ftimef_time Prop 2 Theorem 9 Theorem 1 gtimeg_time arbitrary consistent unit unweighted NP-h and W[2]-h wrt. k NP-h and W[1]-h wrt. k NP-h Poly-time GeneralTreesPathsStarsGeneralTreesPathsStarsGeneralTreesPathsStarsGeneralTreesPathsStarsGraph restriction Figure 1. Overview of our results. In terms of agent mobility models, represented formally by agent-specific weight functions, we consider four cases. • Arbitrary: each agent has its own weight function waw_a and wbw_b is arbitrary. • Consistent: all agents share the same weight function. • Unit: all agent edge weights are equal to a constant c∈ℕc (equivalently, wa≡1w_a≡ 1 up to scaling). • Unweighted: all agent and bus edge weights are 11. For gtimeg_time, the unweighted case is uninteresting since it is optimal for all agents to walk directly to their destination; we exclude this case from the following discussion. For all other objective functions, we show that the unweighted case is hard on general graphs. Note that this hardness does not follow from the above-mentioned connection to k-Center, since that connection applies to the case where all bus weights are zero. This hardness motivates us to consider restricted input graphs and assess, for each, how realistic the agent models can be before facing intractability. We show for example that for fenergyf_energy, MBSP is polynomial-time solvable on trees for consistent agent weights and hard for arbitrary agent weights. In contrast, for ftimef_time all weight function models yield hard problems on trees. This indicates that minimizing fenergyf_energy is easier than minimizing ftimef_time. The same can be observed for the more restricted cases where the input is a path or a star. Allowing agents to choose whether to take the bus also makes the problem harder: minimizing genergyg_energy is already hard on stars in the unweighted case. On paths, however, fenergyf_energy and genergyg_energy are tractable even for arbitrary weight models. This case is particularly interesting because it corresponds to optimizing bus stop placement along an existing bus route. To illustrate this application, we consider the NYC-M15 corridor, showing that the two objectives can lead to different stop sets. 1.2. Further Related Work The k-Median problem in graphs asks to select k vertices in a graph (corresponding to the bus stops) such that the sum of the minimum distances of the graph vertices to the selected vertices is minimized. In network analysis, this problem is also known as Group Closeness Centrality (9). It is polynomial-time solvable on trees (26) but W[2]-hard with respect to k on bounded-degree graphs (25). The most crucial differences to our setting are that there are no costs for connecting the selected vertices, in other words, no bus route; every graph vertex is an agent that needs to reach one of the selected vertices; and all agents have the same weight function. The Facility Location problem, in particular Connected Facility Location (16) with fixed number k of facilities is also closely related. Here, the selected facilities correspond to our bus stops but the connection between them is established via a Steiner Tree, not a route. Even more crucially, agents only seek to reach a facility; travel time is not modeled. A more agent-centric study on Facility Location was undertaken by Aziz et al. (2); unlike our work they consider the problem with capacity constraints on the facilities and problem versions where the agents do not reveal their locations. Another line of related work concerns set covering routing problems (19), where one must choose which vertices to visit and how to connect them. Among the most studied variants are the Travelling Purchaser Problem (TPP) and the Ring Star Problem (RS). TPP asks for a minimum-cost tour visiting markets where all required products can be bought (17; 27). MBSP with fenergyf_energy is a special case: markets correspond to potential bus stops, purchase costs encode agents’ contributions, and the tour encodes the bus route. Since the reduction preserves the underlying graph structure, our hardness results for restricted graph classes, such as stars, transfer directly to TPP. In contrast, RS asks for a cycle through selected vertices, assigning all remaining vertices to them at minimum routing and assignment cost (15). Unlike MBSP, it uses a cycle rather than a route and does not model individual source–destination pairs or travel-time preferences. As we consider agents with start point and destination, the problem can also be considered as a pick up and delivery problem; for a survey see (3). A further related problem is School Bus Routing (21) which often addresses the case where many routes must be planned simultaneously and considers a plethora of additional aspects such as distribution of the students to bus routes, adjustment of bus timeplans and school bells. These problems are considerably harder than our setting and solved with heuristics (1; 24). Finally, MBSP can be viewed as a stylized variant of transit network design, which studies the design of public transport routes, stops, frequencies, and schedules (12; 20; 7). More specifically, it is also related to work on bus-stop location and spacing (11). In contrast, we study the computational complexity of a single-route stop-selection problem with source–destination agents and agent-specific access costs. 2. Preliminaries For n∈ℕn , we denote by [n][n] the set 1,2,…,n\1,2,…,n\. Graphs and Shortest Walks We use standard notation from graph theory. Let G=(V,E)G=(V,E) be an undirected graph. A walk in G is a sequence of vertices P=(v1,…,vℓ)P=(v_1,…,v_ ) such that vi,vi+1∈E\v_i,v_i+1\∈ E for all i∈[l−1]i∈[l-1]. We say that P starts at v1v_1 and ends at vℓv_ . A path is a walk in which each vertex appears at most once. Let w:E→ℝ≥0w:E _≥ 0 be an edge-weight function. The weight of a walk P=(v1,…,vℓ)P=(v_1,…,v_ ) is w(P):=∑i=1ℓ−1w(vi,vi+1).w(P)\ :=\ _i=1 -1w(\v_i,v_i+1\). For vertices s,t∈Vs,t∈ V, we denote by Π(s,t,w) (s,t,w) a minimum-weight walk from s to t under weights w. Note that Π(s,t,w) (s,t,w) can always be chosen to be a path. We write π(s,t,w):=w(Π(s,t,w))π(s,t,w)\ :=\ w( (s,t,w)) for the corresponding minimum weight. Agents and Bus Routes An agent is a tuple a=(s,t,w)a=(s,t,w) with s,t∈Vs,t∈ V and w:E→ℝ≥0w:E _≥ 0, where s is the agent’s start vertex, t is the agent’s destination, and w is the agent’s edge-weight function. We use sas_a, tat_a, and waw_a to refer to the attributes of a, respectively. A bus route with k stops is a sequence of vertices B=(v1,…,vk)B=(v_1,…,v_k). Consecutive stops in B need not be adjacent in G and vertices may repeat. We write B[i]B[i] for the iith stop of B. Given indices i,j∈[k]i,j∈[k] and bus weights wbw_b, we define ΠB(i,j)≔Π(B[i],B[j],wb) _B(i,j) (B[i],B[j],w_b) as a minimum-weight walk that starts at B[i]B[i], ends at B[j]B[j], and visits the stops of the route in order along the subsequence from B[i]B[i] to B[j]B[j]. More precisely, the walk must visit in order B[i],B[i+1],…,B[j]orB[i],B[i−1],…,B[j]B[i],B[i+1],…,B[j] B[i],B[i-1],…,B[j] depending on whether i≤ji≤ j or i>ji>j. We write πB(i,j):=wb(ΠB(i,j)) _B(i,j)\ :=\ w_b( _B(i,j)) for the minimum weight of such a constrained walk. For an agent a∈Aa∈ A, the walking cost of boarding at B[i]B[i] and leaving at B[j]B[j] is πa(B,i,j):=π(sa,B[i],wa)+π(B[j],ta,wa). _a(B,i,j):=π(s_a,B[i],w_a)+π(B[j],t_a,w_a). Objective Functions We study the following two objectives. The energy objective, considered in (23) and (22), consists of the bus travel cost along the full route plus the sum of walking costs to and from the bus of all agents: fenergy(B):=πB(1,k)+∑a∈Amini,j∈1,…,k(πa(B,i,j)).f_energy(B)\ :=\ _B(1,k)\ +\ _a∈ A\ _i,j∈\1,…,k\ ( _a(B,i,j) ). The time objective models that each agent additionally experiences the bus travel time between its boarding and exit stops: ftime(B):=∑a∈Amini,j∈1,…,k(πa(B,i,j)+πB(i,j)).f_time(B)\ :=\ _a∈ A\ _i,j∈\1,…,k\ ( _a(B,i,j)+ _B(i,j) ). Note that ftimef_time as defined above differs from all time objective functions of Proissl and Koch (22). They model time as average travel time including pre-departure waiting, assuming that all agents start simultaneously towards a fixed start stop and that the bus departs only after the last agent arrives. In our setting, agents choose boarding and exit stops autonomously, so we do not model such agent coordination and aggregate per-agent travel times. Variants allowing direct walking. We also consider variants in which an agent may be faster by walking directly to its destination: • genergyg_energy is the same as fenergyf_energy, except that each agent may alternatively prefer π(sa,ta,wa)π(s_a,t_a,w_a); • gtimeg_time is the same as ftimef_time, except that each agent may alternatively prefer π(sa,ta,wa)π(s_a,t_a,w_a). Parameterized Complexity All four objective functions can clearly be computed in polynomial time for a given bus route, which means that for each variant there is a brute-force algorithm with running time nk+(1)n^k+O(1). For large n, this running time becomes prohibitively large even for rather small values of k. In contrast, FPT-algorithms for k, that is, algorithms running in time f(k)⋅n(1)f(k)· n^O(1) are more desirable in practice. To exclude not only polynomial running times in our lower bounds, but also FPT-running times, we use the framework of parameterized complexity (8; 6) where each input instance consists of the classical instance and a problem-specific parameter k. Basic classes of intractability are W[1]-hardness and W[2]-hardness. In other words, it is assumed that W[1]-hard and W[2]-hard problems do not admit FPT-algorithms. To show W[1]-hardness or W[2]-hardness of a problem, one describes a parameterized reduction from a W[1]-hard or W[2]-hard problem, respectively. A parameterized reduction is a reduction that runs in FPT-time and for which the parameter of the constructed instance depends only on the parameter of the input instance; for a formal definition, we refer the reader to the standard textbooks on parameterized complexity (8; 6). 3. Hardness on General Unweighted Graphs To motivate the subsequent studies where we look at the hardness of MBSP on trees, stars, and paths, we first show that all objective functions except gtimeg_time are W[2]-hard for the parameter k on general graphs even in the unweighted case. For this we use reductions from Hitting Set. A Hitting Set instance consists of a hypergraph ℋ=(V,ℰ)H=(V,E) and a budget k. The goal is to decide if there is a hitting set S⊆VS V with |S|=k|S|=k and S∩e≠∅S∩ e≠ for all e∈ℰe . Hitting Set is W[2]-hard for the parameter k (8). Theorem 1. MBSP with objective function fenergyf_energy, genergyg_energy, or ftimef_time is W[2]-hard for k on general graphs in the unweighted case. Proof. We first show the statement for genergyg_energy. Given an instance (ℋ=(V,ℰ),k)(H=(V,E),k) We construct an MBSP instance on a graph G=(V′,E)G=(V ,E) as follows: For each vertex v∈Vv∈ V there is a vertex xv∈V′x_v∈ V , and we connect all those vertices to form a clique in G. Furthermore, for each edge e∈ℰe we add a vertex ses_e to V′V and for all v∈ev∈ e we add edges se,xv\s_e,x_v\ to E. Additionally, we introduce a destination vertex t, which is connected to xvx_v for each v∈Vv∈ V. There is an agent aea_e for each edge e∈ℰe who travels from ses_e to t. We consider the unweighted case, that is, we set all edge weights for the agents and the bus to 11. We set the number of bus stops to k′≔k+1k k+1. We next show the correctness of the reduction. Claim: ℋH has a hitting set of size k if and only if the MBSP instance has a solution B with genergy≤|ℰ|+kg_energy≤|E|+k. (⇒)( ) Let S be a hitting set of size k in ℋH. Then, by placing a bus stop at t and at every xvx_v with v∈Sv∈ S, we obtain a bus route B with k+1k+1 bus stops. The objective function value of B is at most |ℰ|+k|E|+k: for every agent walking one edge suffices to reach the closest bus stop and drive to t, and k edges connect the k+1k+1 bus stops. (⇐)( ) Let B be an optimal solution of the MBSP instance. We show that t is a bus stop and that for each edge e∈ℰe at least one of the vertices in N(se)∪seN(s_e)∪\s_e\ is a bus stop. Then, we can construct a hitting set of size at most k by first adding v∈Vv∈ V to the hitting set if xvx_v is a bus stop and then adding one vertex from each edge e∈ℰe if ses_e is a bus stop. Suppose some vertex is the location of two bus stops. Then either all agents are adjacent to a bus stop and t is a bus stop, or we can move a duplicate bus stop to a vertex adjacent to an agent who is not yet adjacent to a bus stop or to t without increasing the objective value since we save a cost of at least 1 for the agents while prolonging the bus tour by at most 1. We can repeat this process until there are no duplicate bus stop locations or all agents are adjacent to a bus stop and t is a bus stop. For the rest of the proof we assume that there are no two bus stops at the same vertex. If for some edge e∈ℰe there is a bus stop at ses_e but not in N(se)N(s_e), then we can move the bus stop from ses_e to an arbitrary vertex in N(se)N(s_e). This increases the cost of agent aea_e by 11 but decreases the bus cost by at least 11. Connecting the k+1k+1 bus stops contributes at least k to the objective function. Hence, the total contribution of the agents is at most |ℰ||E|. If there is an agent aea_e who contributes more than 11 to the objective function value, then there must be another agent ae′a_e who contributes 00 to the objective function value. Note that this implies that there must be a bus stop in se′s_e and therefore also in N(se′)N(s_e ). We can move this bus stop from se′s_e to a neighbor of ses_e without increasing the objective function value because the contribution of at least agent aea_e is decreased by at least 11 and the contribution of agent ae′a_e is increased by 11. If there are no more agents who contribute more than 11 to the objective function value, then for every edge e∈ℰe there must be at least one bus stop in N(se)∪seN(s_e)∪\s_e\. To construct a hitting set of size at most k we need to look at two cases. In the first case t is a bus stop and we are done. In the second case t is not a bus stop. This implies that for all e∈ℰe the vertex ses_e is a bus stop since the agent aea_e contributes exactly 11 to the objective function by walking over an edge that leads to t. The bus route must therefore contribute at most k to the objective function which is only possible if every agent aea_e has a bus stop in N(se)N(s_e). This implies that there are at most k edges in ℰE which gives us a trivial solution. Altogether, this shows the correctness of the reduction. Since the construction of the MBSP instance forces all agents to use the bus in the optimal solution, the result carries directly over to fenergyf_energy. To show hardness for ftimef_time, we slightly modify the construction: First, each agent aea_e now has its own destination vertex tet_e which has the same neighborhood as ses_e. Second, we set the number k′k of bus stops to k. It remains to show the following. Claim: ℋH has a hitting set of size k if and only if the MBSP instance has a solution B with ftime≤2|ℰ|f_time≤ 2|E|. (⇒)( ) Let S be a hitting set of size k in ℋH. Then, placing a bus stop at xv∈V′x_v∈ V for all v∈Sv∈ S is a solution to the MBSP with k bus stops on G. By construction of the MBSP instance on G and the definition of S each agent contributes 22 to the objective function value, which sums up to 2|ℰ|2|E|. (⇐)( ) Let B be an optimal solution of the MBSP instance. Because no agent can contribute less than 22 to the objective function value, all agents must contribute exactly 22. This implies that for each agent aea_e at least one of the vertices in N(se)∪se,teN(s_e)∪\s_e,t_e\ must be a bus stop. We can use this to easily construct a hitting set of size at most k by adding xvx_v to S if xvx_v is a bus stop and adding a vertex from N(se)N(s_e) to S whenever ses_e or tet_e is a bus stop. ∎ In contrast to Theorem 1, MBSP is trivial with the gtimeg_time objective function. This is because in the unweighted case an agent never benefits from using the bus as they can always just walk directly to their end point. Consequently, any bus route with k stops is an optimal solution, which gives the following. Proposition 2. MBSP with objective function gtimeg_time can be solved in polynomial time on general graphs in the unweighted case. 4. Minimizing Energy on Trees rraabbccdd (a) After rooting the tree at r. rrcrc_raabbccccc_cd (b) After adding dummy children. rrcrc_rx2x_2aax1x_1bbccccc_cd (c) After binarizing the tree. Figure 2. Example of the input preprocessing in the proof of Theorem 1. The hollow vertices are the newly added vertices and the dashed edges have weight 00 for both weight functions waw_a and wbw_b. Motivated by the hardness on general graphs, we now consider the two energy objective functions on trees. We start by showing that fenergyf_energy can be solved in polynomial time on trees if we have consistent agent weights. Theorem 1. MBSP with objective function fenergyf_energy can be solved in (n4k2+|A|)O(n^4k^2+|A|) time on trees with consistent agent weights. Proof. We describe a dynamic programming algorithm. First, for fenergyf_energy and consistent weights, we can simplify the problem by turning each agent a=(sa,ta,wa)a=(s_a,t_a,w_a) into two agents as=saa_s=s_a and at=taa_t=t_a that both only have a starting point. This is because the agent always needs to enter the bus and it does not matter how far the agent travels in the bus. We write AvA_v to denote the set of agents that have v as their start vertex. We can precalculate all of these sets in time (n+|A|)O(n+|A|). For the algorithm to work we modify the input tree so that it becomes a rooted and binary tree where we only need to place bus stops at leaves: Let T=(V,E)T=(V,E) be the input tree. We start by rooting T at an arbitrary vertex r as shown in Figure 2(a). For each vertex v∈Vv∈ V with at least one child in T we add a new dummy child cvc_v, and we set the weight of the edge v,cv\v,c_v\ to zero for both waw_a and wbw_b. An example of this is shown in Figure 2(b). Notice that placing a bus stop at v is now equivalent to placing a bus stop at cvc_v. This already ensures that at least one optimal solution exists where all bus stops are at leaves. Next, we binarize the tree. Let v be a vertex with at least three children v1,v2,v3v_1,v_2,v_3. We add a new child x to v and change v2v_2 and v3v_3 such that they are now children of x instead of v. We set the weight of the edge v,x\v,x\ to zero for both waw_a and wbw_b and we set the weights of the edges x,v2\x,v_2\ and x,v3\x,v_3\ to the weights of the old edges v,v2\v,v_2\ and v,v3\v,v_3\, respectively. In Figure 2(c) two extra vertices were added since the vertex r had four children. Note that these changes only lead to a linear increase in the size of the tree. Let T be the final binarized tree. We write L to denote the set of leaf vertices in T and LvL_v to denote the set of leaf vertices in the subtree with root v. We also order the tree, meaning each non-leaf vertex v has a fixed left and right child. As a final preparation we calculate all pairwise distances in the tree for waw_a. We now define the arguments of the dynamic programming table D[v,k′,bin,bout,p]D[v,k ,b_in,b_out,p] as follows: • v: the root of the subtree we are currently looking at. • k′k : the number of bus stops in the subtree of v. • binb_in: a bus stop in the subtree of v where π(v,bin,wa)π(v,b_in,w_a) is minimal, it is ⊥ if there is no such bus stop. • boutb_out: a bus stop outside the subtree of v where π(v,bout,wa)π(v,b_out,w_a) is minimal, it is ⊥ if there is no such bus stop. • p: the number of stops in the subtree of v where the overall bus route starts or ends, can either be 00, 11, or 22. Each entry in the table is the sum of two parts. First, for all agents in the subtree of v, the sum of their distances to their closest bus stop (even if this bus stop is outside the subtree). Second, the sum over the bus weights of each edge e in the subtree of v multiplied by how often the bus traverses e. To calculate the first part we may need to calculate the distance π(v,b,wa)π(v,b,w_a) between a vertex v and a bus stop b. For simplicity, if b=⊥b= we set π(v,b,wa)=∞π(v,b,w_a)=∞. To calculate the table entries D[ℓ,k′,bin,bout,p]D[ ,k ,b_in,b_out,p] for a leaf ℓ we only need to consider two cases. If ℓ is a bus stop, then the agents that start at ℓ do not need to walk anywhere. If ℓ is not a bus stop, then the agents that start at ℓ walk to boutb_out. The second part is always 00 since leaves do not have any children: 0if k′=1,bin=ℓ,p≤k′,|Aℓ|⋅π(ℓ,bout,wa)if k′=0,bin=⊥,bout≠⊥,p=0,∞otherwise. cases0&if k =1,b_in= ,p≤ k ,\\ |A_ |·π( ,b_out,w_a)&if k =0,b_in= ,b_out = ,p=0,\\ ∞&otherwise. cases We now look at a non-leaf vertex v with left child ℓ and right child r. We can immediately set the table entry to ∞ if k′<pk <p or k′=0k =0 but bin≠⊥b_in = since there is no feasible solution with these properties. Otherwise, we use the following recurrence to calculate the table entry D[v,k′,bin,bout,p]D[v,k ,b_in,b_out,p]. We will explain each part of it in the following paragraphs: minkℓ∈0,…,k′(binℓ,boutℓ,binr,boutr)∈valid(⋅)pℓ∈0,…,p(D[vℓ,kℓ,binℓ,boutℓ,pℓ]+D[vr,k′−kℓ,binr,boutr,p−pℓ]+|Av|⋅minb∈bout,binπ(v,b,wa)+δ(v,kℓ,k′−kℓ,pℓ,p−pℓ)) _ subarrayck ∈\0,…,k \\\ (b _in,b _out,b^r_in,b^r_out)∈ valid(·)\\ p ∈\0,…,p\ subarray ( aligned &D[v ,k ,b _in,b _out,p ]\\ +&D[v^r,k -k ,b^r_in,b^r_out,p-p ]\\ +&|A_v|· _b∈\b_out,b_in\π(v,b,w_a)\\ +&δ(v,k ,k -k ,p ,p-p ) aligned ) The general idea is to go through all combinations of table entries for the left and right child of v that fulfill the constraints of the table entry we are trying to calculate. Once we have fixed the table entries of the two children, we can calculate where the agents that start at v walk to and how many times the bus traverses the edges between v and its two children. To check all relevant table entries of the two children, we first go through all possible values of kℓk and pℓp , thereby distributing the k′k bus stops and the p end stops between the two child subtrees. Since k′≤k ≤ k and p≤2p≤ 2, there are only (k)O(k) ways to do this. Next, we go through all tuples (binℓ,boutℓ,binr,boutr)(b _in,b _out,b^r_in,b^r_out) of relevant binb_in and boutb_out bus stops for the two children. We call the set of these tuples valid(⋅)valid(·). In the following, we show that there are only (n)O(n) such tuples. Without loss of generality, assume that binb_in is in the subtree of ℓ ; the case where it lies in the subtree of r is symmetric. We can now set binℓ=binb _in=b_in for all tuples since any bus stop that would be closer to ℓ would also be closer to v. For binrb^r_in we can choose any vertex that is in the subtree of r and is not closer to v than binb_in, meaning π(binr,v,wa)≥π(bin,v,wa)π(b^r_in,v,w_a)≥π(b_in,v,w_a). Additionally, we can choose brin=⊥b^r_in= for the case that there is no bus stop in the subtree of r. Once we have fixed binℓb _in and binrb^r_in we can uniquely determine boutℓb _out and boutrb^r_out as follows: boutℓ=argminb∈binr,boutπ(ℓ,b,wa) b _out= _b∈\b^r_in,b_out\π( ,b,w_a) boutr=argminb∈binℓ,boutπ(r,b,wa) b^r_out= _b∈\b _in,b_out\π(r,b,w_a) In total this shows that |valid(⋅)|∈(n)|valid(·)| (n). Once the two child entries are fixed, both parts of the current entry can be computed in constant time. The agents starting at v walk either to binb_in or to boutb_out, so their contribution is obtained from the precomputed distances and |Av||A_v|. It remains to account for the two edges from v to its children. We denote this contribution by δ(v,kℓ,kr,pℓ,pr)δ(v,k ,k^r,p ,p^r). For the edge v,ℓ\v, \, the contribution is 00 if kℓ=0k =0 or kℓ=k =k. Otherwise, the bus traverses this edge once if pℓ=1p =1, and twice if pℓ∈0,2p ∈\0,2\. The contribution of v,r\v,r\ is defined analogously, and δ(v,kℓ,kr,pℓ,pr)δ(v,k ,k^r,p ,p^r) is the sum of the two contributions. Overall, this gives a running time of (nk)O(nk) for calculating each of the (n3k)O(n^3k) table entries. Combined with the time to precalculate all pairwise distances and the values |Av||A_v|, this gives a total running time of (n4k2+|A|)O(n^4k^2+|A|). ∎ In contrast to Theorem 1 we show that allowing arbitrary agent weight functions makes the problem W[2]-hard even if we further restrict the input graphs to stars. For this we again use a reduction from Hitting Set. Given a Hitting Set instance (ℋ,k)(H,k), we construct an MBSP instance on a star G. Let c∈V(G)c∈ V(G) be the center vertex of the star. For each vertex v∈V(ℋ)v∈ V(H), we add a leaf vertex xvx_v to V(G)V(G). Then we add a leaf vertex xex_e to V(G)V(G) for each edge e∈ℰ(ℋ)e (H). We set all bus-weights to zero. For each v∈V(G)v∈ V(G) we add a vertex-agent ava_v with start and end vertex xvx_v. These agents have an edge weight of 1 on the edge xv,c\x_v,c\ and 00 on all other edges. For each e∈ℰ(G)e (G) we add an edge-agent aea_e with start and end vertex xex_e. These agents have weight 00 on xe,c\x_e,c\ and c,xv\c,x_v\ for all v∈ev∈ e and weight 11 on all other edges. The parameter k is the same. Theorem 2. MBSP with objective function fenergyf_energy or ftimef_time is W[2]-hard for parameter k on stars with arbitrary agent weights. Proof. Since we set the bus weights to zero, the objective functions fenergyf_energy and ftimef_time coincide, and we refer to them as f. We can prove the statement by showing the following claim: Claim: There exists a hitting set of size k in ℋH if and only if the MBSP instance has a solution B with f(B)≤2(n−k)f(B)≤ 2(n-k). (⇒)( ) Let S be a hitting set of size k in ℋH. Then by placing a bus stop at each vertex xvx_v for v∈Sv∈ S, we obtain a solution where we have n−kn-k vertex agents contributing a cost of 22 to the objective function value each. By construction of the MBSP instance on G, each edge-agent aea_e has weight 00 on all walks from xex_e to a vertex xvx_v for v∈ev∈ e. By definition of S for each e∈ℰe we have S∩e≠∅S∩ e≠ and hence aea_e can reach a bus stop at 00 cost from xex_e. Subsequently, edge-agents do not contribute to the objective function value. (⇐)( ) Consider a solution to the MBSP instance with objective value at most 2(n−k)2(n-k). Because each vertex-agent which is not at a bus stop contributes 22 to the objective function value, each of the k bus stops must be placed at a leaf vertex xvx_v for some v∈V(ℋ)v∈ V(H). Since all other vertex-agents contribute 22 to f, the edge-agents must contribute 00. Thus, for all e∈ℰe there must be a weight-zero walk from xex_e to a bus stop xvx_v for some vertex v∈ev∈ e. Therefore, S≔v∈V(ℋ)∣xv is bus stopS \v∈ V(H) x_v is bus stop\ is a hitting set of size k. ∎ Next, we look at the cases covered by Theorems 1 and 2 for the genergyg_energy function. Surprisingly, allowing agents to directly walk to their destination makes all of these cases W[1]-hard. We show this with a reduction from Clique which is W[1]-hard for k (8). Theorem 3. MBSP with objective function genergyg_energy is W[1]-hard on stars in the unweighted case. Proof. We use a reduction from the Clique problem, where we are given a graph G and an integer k, and we want to know if G contains a clique of size k. Our reduction works as follows: Let (G,k)(G,k) be an instance of Clique. We create a new graph T. First, we add a center vertex c. For each vertex v∈V(G)v∈ V(G) we add the two vertices svs_v and tvt_v to T. Since we are creating a star graph, all of these vertices are directly connected to the center vertex c. Let M>4k+2|E(G)|M>4k+2|E(G)|. For each vertex v∈V(G)v∈ V(G) we add M vertex agents with start vertex svs_v and end vertex tvt_v. We call the set of these agents AvA_v. For each edge e=u,v∈E(G)e=\u,v\∈ E(G) we add one edge agent aea_e with start vertex sus_u and end vertex svs_v. Finally, we set the number of allowed bus stops to k′=2k =2k. This gives us the MBSP instance (T,A,k′)(T,A,k ). Note, that we can ignore the weight functions since we are in the unweighted case. We now show that (G,k)(G,k) is a yes-instance if and only if (T,A,k′)(T,A,k ) has a bus route B with genergy(B)≤4k−2+2|E(G)|−2(k2)+2M⋅(|V(G)|−k)g_energy(B)≤ 4k-2+2|E(G)|-2 k2+2M·(|V(G)|-k). (⇒ ) Let C be the vertex set of a clique in G with |C|=k|C|=k. For each vertex v∈Cv∈ C we add a bus stop at svs_v and a bus stop at tvt_v. We put all bus stops into an arbitrary order to create a bus route B. The bus route itself contributes 4k−24k-2 to the value of the objective function. This is because we have to first drive from the first bus stop to the center vertex. Then we have to visit the next 2k−22k-2 bus stops by driving to them and then back to the center vertex. Finally, we drive from the center vertex to the last bus stop. For each vertex v∈V(G)v∈ V(G) the agents AvA_v contribute 2M2M to the objective function if v∉Cv∉ C since each agent needs to walk two edges from svs_v to tvt_v. Otherwise, the agents can take the bus and have a contribution of zero. This gives us a total contribution of 2M⋅(|V(G)|−k)2M·(|V(G)|-k). For each edge e=u,v∈E(G)e=\u,v\∈ E(G) the agent aea_e contributes 22 to the objective function if at most one of u and v is a bus stop, and it contributes zero if both vertices are bus stops. Since we selected the vertices of a clique of size k, these agents have a total contribution of 2|E(G)|−2(k2)2|E(G)|-2 k2. (⇐ ) Let B be a bus route with genergy(B)≤4k−2+2|E(G)|−2(k2)+2M⋅(|V(G)|−k)g_energy(B)≤ 4k-2+2|E(G)|-2 k2+2M·(|V(G)|-k). We start by showing that the center vertex c cannot be a bus stop. For this, let us assume that the center vertex is a bus stop. We will look at how much the vertex agents contribute to the objective function under this assumption. Let v∈V(G)v∈ V(G). If neither svs_v nor tvt_v are bus stops, then the agents in AvA_v have a total contribution of 2M2M. If exactly one of these vertices is a bus stop then the agents have a total contribution of M. And if both are bus stops, then the contribution is zero. This means every non-center vertex in T that becomes a bus stop reduces the contribution of the vertex agents by M. Since the center vertex is already a bus stop, we can only select at most 2k−12k-1 of these vertices for a total contribution of 2M⋅|V(G)|−M⋅(2k−1)=M+2M⋅(|V(G)|−k)2M·|V(G)|-M·(2k-1)=M+2M·(|V(G)|-k). By the definition of M this is bigger than 4k−2+2|E(G)|−2(k2)+2M⋅(|V(G)|−k)4k-2+2|E(G)|-2 k2+2M·(|V(G)|-k). Hence, the center vertex cannot be a bus stop. Next, we show that there must be exactly k vertices in V(G)V(G) for which both svs_v and tvt_v are bus stops. For this, we again look at the contribution of the vertex agents. Let v∈V(G)v∈ V(G). If at most one of svs_v and tvt_v is a bus stop, then the agents in AvA_v contribute 2M2M to the objective function since the center vertex is not a bus stop, meaning they have to always walk at least two edges. If both vertices are bus stops, then the contribution is zero. This means, the only way to reduce the contribution of the vertex agents is to select both their starting point and their end point. We can do this at most k times which gives us a total contribution of 2M⋅(|V(G)|−k)2M·(|V(G)|-k). Doing this only k−1k-1 times would lead to a contribution that is bigger than 4k−2+2|E(G)|−2(k2)+2M⋅(|V(G)|−k)4k-2+2|E(G)|-2 k2+2M·(|V(G)|-k). Hence, there must be exactly k vertices in V(G)V(G) for which both svs_v and tvt_v are bus stops. We will call these k vertices the vertices that were selected by B. The only thing left to show is that the vertices selected by B must form a clique in G. For this, notice that the contribution of the bus route and the vertex agents is now fixed to 4k−24k-2 and 2M⋅(|V(G)|−k)2M·(|V(G)|-k), respectively. This means that the remaining edge agents must have a contribution of at most 2|E(G)|−2(k2)2|E(G)|-2 k2. As we explained in the (⇒)( ) part of the proof, the contribution of an edge agent aea_e can only be reduced if both end points of e are selected by the bus route. This means the minimum contribution is reached if the bus route selects a clique. We already saw in the (⇒)( ) part that this leads to a contribution of 2|E(G)|−2(k2)2|E(G)|-2 k2 which shows that the bus route must select a clique of size k in G. ∎ Finally, we restrict the input graphs to paths and show that MBSP can be solved efficiently for both energy objectives, even with arbitrary agent weights. As in Theorem 1, our approach is based on dynamic programming. The idea is to fix the rightmost bus stop so far and consider all possibilities for the next bus stop. This determines how agents traverse the edges between the two stops. Theorem 4. MBSP with objective function fenergyf_energy or genergyg_energy can be solved in (n3k⋅|A|)O(n^3k·|A|) time on paths with arbitrary weights. Proof. We first describe the algorithm for genergyg_energy and then show how it can be modified to work for fenergyf_energy. Let (P,A,wb,k)(P,A,w_b,k) be the input. The graph P=(V,E)P=(V,E) is a path on n vertices (v1,…,vn)(v_1,…,v_n). We say that viv_i is to the left of vjv_j and that vjv_j is to the right of viv_i if i<ji<j. We assume that each agent in A has start vertex vℓv_ and end vertex vrv_r with ℓ≤r ≤ r. We define a dynamic programming based algorithm to solve MBSP for this input. A table entry D[k′,vj]D[k ,v_j] assumes that vjv_j is a bus stop and that there are exactly k′k bus stops to the left of vjv_j. The entry contains the objective function value of an optimal bus route that fulfills these conditions while only counting the contribution of edges that are to the left of vjv_j. In the base cases with k′=0k =0 the bus route contributes 00 to the objective function. This means we only need to count the contribution of the agents. If an agent starts and ends to the left of vjv_j, then it is optimal for that agent to walk directly to their endpoint. Else if the agent only starts to the left of vjv_j, then that agent will always walk to vjv_j. If the agent does not start to the left of vjv_j, then the agent has a contribution of 00 since it does not make sense for the agent to walk to the left of vjv_j: D[0,vj]=∑(vℓ,vr,w)∈Aπ(vℓ,vr,w)if r<j,π(vℓ,vj,w)if ℓ<j≤r,0otherwise.D[0,v_j]= _(v_ ,v_r,w)∈ A casesπ(v_ ,v_r,w)&if r<j,\\ π(v_ ,v_j,w)&if <j≤ r,\\ 0&otherwise. cases If k′>0k >0, then we need to check all possible positions viv_i of the closest bus stop to the left of vjv_j. For each of those we need to add up the previous table entry D[k′−1,vi]D[k -1,v_i], the contribution of the bus between viv_i and vjv_j, and the contribution of the agents between viv_i and vjv_j. This can be expressed as follows, where fA(vi,vj)f_A(v_i,v_j) is the agent contribution between viv_i and vjv_j. mini∈[j−1](D[k′−1,vi]+π(vi,vj,wb)+fA(vi,vj)) _i∈[j-1] (D[k -1,v_i]+π(v_i,v_j,w_b)+f_A(v_i,v_j) ) To calculate fA(vi,vj)f_A(v_i,v_j) we need to sum up the contribution of each individual agent. For this we consider four different types of agents (vℓ,vr,w)∈A(v_ ,v_r,w)∈ A. Case 11: i≤ℓ≤r≤ji≤ ≤ r≤ j. In this case the agent starts and ends between viv_i and vjv_j. Here the agent either directly walks to their end point or they walk from their start point to viv_i, use the bus to get to vjv_j, and then walk from vjv_j to their end point. The contribution of such an agent is min(π(vℓ,vr,w),π(vi,vℓ,w)+π(vr,vj,w)) (π(v_ ,v_r,w),π(v_i,v_ ,w)+π(v_r,v_j,w)). Case 22: ℓ<i≤r≤j <i≤ r≤ j. In this case only the end point is between viv_i and vjv_j. Here we can assume that the agent sits in the bus at viv_i, meaning they either walk from viv_i to their end point or they use the bus to get to vjv_j and then walk from there. The contribution of such an agent is min(π(vi,vr,w),π(vr,vj,w)) (π(v_i,v_r,w),π(v_r,v_j,w)). Case 33: i≤ℓ≤j<ri≤ ≤ j<r. In this case only the start point is between viv_i and vjv_j. Analogously to Case 22, the agent either walks to viv_i or vjv_j. The contribution of such an agent is min(π(vi,vℓ,w),π(vℓ,vj,w)) (π(v_i,v_ ,w),π(v_ ,v_j,w)). Case 44: ℓ<i≤j<r <i≤ j<r. In this case neither start nor end point are between viv_i and vjv_j. Here we can assume that the agent uses the bus to get from viv_i to vjv_j, meaning the contribution is 00. Finally, to find the globally optimal objective function value we need to consider each vertex as the rightmost bus stop. Similar to the case for k′=0k =0 we also need to deal with agents that have their end point to the right of the rightmost bus stop. Overall we can calculate the optimal objective function value as follows: minj∈[n](D[k,vj]+∑(vℓ,vr,w)∈Aπ(vℓ,vr,w)if j<ℓ,π(vj,vr,w)if ℓ≤j<r,0otherwise.) _j∈[n] (D[k,v_j]+Σ _(v_ ,v_r,w)∈ A casesπ(v_ ,v_r,w)&if j< ,\\ π(v_j,v_r,w)&if ≤ j<r,\\ 0&otherwise. cases ) The table has size (nk)O(nk), calculating the table entries for k′=0k =0 takes (n⋅|A|)O(n·|A|) time because of the shortest path calculation for each agent, and calculating the table entries for k′>0k >0 takes (n2⋅|A|)O(n^2·|A|) time because of the shortest path calculation for each agent and each next bus stop. In total this gives us a running time of (n3k⋅|A|)O(n^3k·|A|). For the algorithm to work for the fenergyf_energy objective function we only need to change two things. First, agents that start and end to the left of the leftmost bus stop or to the right of the rightmost bus stop can no longer walk directly to their end point and must instead walk to the leftmost or rightmost bus stop. Second, in the calculation of fA(vi,vj)f_A(v_i,v_j) agents that have their start and end point between viv_i and vjv_j can no longer walk directly to their end points. Instead, they have the option of either not using the bus and walking to one of the bus stops and back again, or they can walk to viv_i, use the bus to get to vjv_j, and walk to their end point from there. None of these changes affect the asymptotic running time bound. ∎ 5. Minimizing Time on Trees We now consider the time objectives on trees. We first show that ftimef_time and gtimeg_time are W[1]-hard on stars, even with unit agent weights. The key difficulty is that, for the time objectives, the effect of selecting one bus stop depends on which other stops are selected. We exploit this interaction to prove W[1]-hardness for this variant of MBSP. Theorem 1. MBSP with objective function ftimef_time or gtimeg_time is W[1]-hard on stars with unit agent weights. Proof. We use a reduction from Independent Set to MBSP. Let (G=(V,E),k)(G=(V,E),k) be an instance of Independent Set where |V|=n>max4,k|V|=n> \4,k\. The following proofs use the variables α, β and γ. These variables are chosen such that they are separated by orders of magnitude. We define α,βα,β and γ as follows: γ γ =4⋅n2, =4· n^2,\ \ \ β β =3n3γ, =3n^3γ,\ \ \ α α =2n⋅β+2n2⋅γ+4n2. =2n·β+2n^2·γ+4n^2. We construct an instance (G′,A∗,wb,wa,3k)(G ,A^*,w_b,w_a,3k) of MBSP as follows: V(G′)= V(G )= c∪V1∪V2 \c\∪ V_1∪ V_2 V1= V_1= Xv∣v∈V \X_v v∈ V\ V2= V_2= Xi∣i∈[k] \X_i i∈[k]\ E(G′)= E(G )= c,v′,∣v′∈V(G′)∖c \\c,v \, v ∈ V(G ) \c\\ wb(e)= w_b(e)= α,wa(e)=α+1 for e∈E(G′) α,\ \ \ w_a(e)=α+1 for e∈ E(G ) A∗= A^*= AN∪A∪AE A_N∪ A_A∪ A_E AN= A_N= av′,i=(c,v′,wa)∣v′∈V(G′)∖c,i∈[β] \a_v ,i=(c,v ,w_a) v ∈ V(G ) \c\,i∈[β]\ A= A_A= av,j,i=(Xv,Xj,wa)∣v∈V,j∈[k],i∈[γ] \a_v,j,i=(X_v,X_j,w_a) v∈ V,j∈[k],i∈[γ]\ AE= A_E= au,v=(Xv,Xu,wa)∣u,v∈E \a_u,v=(X_v,X_u,w_a) \u,v\∈ E\ ∪au,v,i=(Xv,c,wa)∣u,v∉E,u≠v, ∪\a_u,v,i=(X_v,c,w_a) \u,v\∉ E,u≠ v, u,v∈V,i∈[2] u,v∈ V,i∈[2]\ Thus, G′G is a star where c is the center vertex which is connected to a vertex Xv∈V1X_v∈ V_1 for v∈Vv∈ V and a vertex Xi∈V2X_i∈ V_2 for each i∈[k]i∈[k]. The agents in AEA_E represent the edges in G. The instance is constructed such that any bus route minimizing the objective function will have a specific structure. Any such route will be made up of k bus stops in V1V_1, k bus stops in c and k bus stops in V2V_2, always alternating between them in the same order. The only vertex that should be visited multiple times is c while every single one of the k vertices in V2V_2 should be visited exactly once. If an independent set exists, the k vertices Xv∈V1X_v∈ V_1 in the route represent k vertices in G which form such an independent set. As we show in Lemma 3, the agent and bus weights are so similar, that it never pays off to travel more edges than necessary. For a bus route B=(b1,…,b3k)B=(b_1,…,b_3k), we say bus stops bi,bj∈Bb_i,b_j∈ B are neighboring if the distance between bib_i and bjb_j in G′G is 11 and |i−j|=1|i-j|=1. For two pairs bi,bj∈Bb_i,b_j∈ B and bl,bm∈Bb_l,b_m∈ B, we say they are distinct if neither bi=blb_i=b_l and bj=bmb_j=b_m nor bi=bmb_i=b_m and bj=blb_j=b_l. The set ANA_N is constructed to maximize the number of neighboring bus stops. We call the agents in ANA_N neighbor agents. We call the agents in A_A alternation agents as the set A_A is constructed to ensure that an optimal bus route alternates between vertices in V1V_1 and V2V_2. The set AEA_E is constructed to ensure the vertices of V1V_1 in the route represent an independent set in G. The total numbers of agents by set are |AN|=(n+k)⋅β,|A|=n⋅k⋅γ|A_N|=(n+k)·β,|A_A|=n· k·γ and |AE|=4⋅(n2)−2⋅|E||A_E|=4· n2-2·|E|. The distance by agent is 11 for ANA_N and 22 for A_A while AEA_E contains agents with paths of length 11 and 22. This results in the sum of the distance between the endpoints for each agent in A∗A^* being Δ=(n+k)⋅β+2n⋅k⋅γ+4⋅(n2) =(n+k)·β+2n· k·γ+4· n2. The total distance agents travel by bus in the desired solution is Θ=2k⋅β+(2k−1+n⋅k)⋅γ+k⋅2(n−1) =2k·β+(2k-1+n· k)·γ+k· 2(n-1). Lemma 2. The independent set instance has a solution if and only if the objective function ftimef_time for this instance is at most Σ=α⋅Δ+Δ−Θ =α· + - . We call a bus route B which fulfills ftime≤Σf_time≤ a certifying solution. To prove Lemma 2, we will first lay some groundwork. Lemma 3. In every certifying solution the total number of edges travelled by agents is Δ . Proof. The sum of the distance between the endpoints for all agents is Δ thus Δ is the minimum amount of edges the agents can travel in any solution.Since α>Δα> it holds, that Σ<α⋅(Δ+1) <α·( +1) and more than Δ edges being travelled by agents in B would result in ftime(B)≥(Δ+1)⋅α>Σf_time(B)≥( +1)·α> . ∎ For the following lemma we introduce some further vocabulary, for a bus route B, we say a bus stop blb_l is between bib_i and bjb_j if i<l<ji<l<j or j<l<ij<l<i, and we further say two vertices u′,v′∈V(G′)∖cu ,v ∈ V(G ) \c\ are connected by B if there exist bi=u′,bj=v′b_i=u ,b_j=v such that all bus stops between bib_i and bjb_j are c. Lemma 4. If there exists an independent set X of G with |X|=k|X|=k, then there exists a certifying solution B. Proof. Let X→=(x1,…,xk) X=(x_1,…,x_k) be any permutation of X. The following bus route B satisfies the lemma. b3i−2= b_3i-2= Xxi∈V1 X_x_i∈ V_1 for i∈[k] for i∈[k] b3i−1= b_3i-1= c c for i∈[k] for i∈[k] b3i= b_3i= Xi∈V2 X_i∈ V_2 for i∈[k] for i∈[k] Notice that every bus stop that is not c has c as a neighboring bus stop. Furthermore, every agent has c on its shortest path meaning that no agent has to take a detour to visit a bus stop. Since xi≠xjx_i≠ x_j for i≠ji≠ j and ve∉Xv_e∉ X, it follows that bi≠bjb_i≠ b_j, for i≠j,bi≠c,bj≠ci≠ j,b_i≠ c,b_j≠ c. We will now show for how many edges agents can use the bus by differentiating the types of agents. ANA_N: There are exactly 2k2k distinct pairs of neighboring bus stops in B. There are exactly β neighbor agents in ANA_N for every edge e′∈E(G′)e ∈ E(G ). Thus, 2k⋅β2k·β neighbor agents av′,i∈ANa_v ,i∈ A_N use the bus for their one station. AEA_E: Since X is an independent set of G and since every bus stop other than c neighbors c, every agent in AEA_E with an endpoint bi∈B,bi≠cb_i∈ B,b_i≠ c uses the bus for the edge bi,c\b_i,c\. Since 22 such agents exist for every pair of vertices bi,v′∈V1b_i,v ∈ V_1 there are 2(n−1)2(n-1) such agents for every bus stop bi∈V1b_i∈ V_1. Since k vertices in V1V_1 are visited by B, this represents a total of k⋅2(n−1)k· 2(n-1) edges travelled by bus for the agents in AEA_E. A:A_A: Since every vertex in V2V_2 has c as a neighboring bus stop every alternation agent can use the bus between its endpoint in V2V_2 and c for a length of 11. Furthermore, alternation agents whose endpoints are connected by B use the bus for both edges. This is the case for (2k−1)(2k-1) such pairs of bus stops each with γ corresponding agents in A_A resulting in a total of (n⋅k+2k−1)⋅γ(n· k+2k-1)·γ edges travelled by bus by alternation agents. If every agent travels its shortest path and at least Θ=2k⋅β+k⋅2(n−1)+2k⋅(n−1)⋅γ =2k·β+k· 2(n-1)+2k·(n-1)·γ edges among them are travelled by bus, then ftime(B)≤α⋅Θ+(α+1)⋅(Δ−Θ)=Σf_time(B)≤α· +(α+1)·( - )= . ∎ Lemma 5. A certifying solution contains exactly 2k2k distinct pairs of neighboring bus stops along the route. Proof. We first show that no certifying solution contains less than 2k2k such pairs. Every neighbor agent av′,i∈ANa_v ,i∈ A_N uses the bus if and only if there exist neighboring bus stops along the bus route between Xv′X_v and c. Less than 2k2k distinct pairs of neighboring bus stops means at least (|V(G′)|−2k)⋅β(|V(G )|-2k)·β neighbor agents taking the bus. Thus, any such bus route cannot achieve an objective function any lower than α⋅(Δ−(|V(G′)|−2k)⋅β)+(α+1)⋅(|V(G′)|−2k)⋅βα·( -(|V(G )|-2k)·β)+(α+1)·(|V(G )|-2k)·β. (Δ−Θ)= ( - )= (|V(G′)|−1)⋅β+n⋅(n−1)⋅2⋅γ (|V(G )|-1)·β+n·(n-1)· 2·γ +(n2)⋅(n−3)⋅γ+4⋅(n2)−Θ + n2·(n-3)·γ+4· n2- < < (|V(G′)|−1)⋅β+3n3⋅γ−2k⋅β (|V(G )|-1)·β+3n^3·γ-2k·β = = (|V(G′)|−2k)⋅β (|V(G )|-2k)·β Since (|V(G′)|−2k)⋅β>Δ−Θ(|V(G )|-2k)·β> - , and Δ−Γ - is an upper bound for the number of edges travelled by bus in a certifying solution, no solution with 2k−12k-1 or fewer distinct pairs of neighboring bus stops is certifying. To prove that no route can contain more than 2k2k distinct pairs of neighboring bus stops, we show that there are never 33 consecutive such pairs. Toward contradiction, let bib_i be a bus stop such that the pairs (bi,bi+1),(b_i,b_i+1), (bi+1,bi+2)(b_i+1,b_i+2) and (bi+2,bi+3)(b_i+2,b_i+3) are all distinct and neighboring for i∈[3k−3]i∈[3k-3]. Since bi+1b_i+1 and bi+2b_i+2 are neighboring one of them is c. Without loss of generality bi+1=cb_i+1=c. Since c is the only neighbor of of bi+2b_i+2 in G′G , it follows that c=bi+3c=b_i+3. Thus, the pairs (bi+1,bi+2)(b_i+1,b_i+2) and (bi+2,bi+3)(b_i+2,b_i+3) are not distinct; a contradiction. Since every certifying solution contains at least 2k2k distinct pairs of neighboring bus stops along the route but never more than 22 consecutive pairs of neighboring bus stops, a certifying solution contains exactly k sequences of 22 consecutive instances of distinct neighboring bus stops along the route resulting in exactly 2k2k distinct pairs of neighboring bus stops. ∎ Lemma 6. A certifying solution B contains exactly 2k−12k-1 distinct pairs of connected bus stops bi,bjb_i,b_j such that bi,bj∩V1\b_i,b_j\∩ V_1 and bi,bj∩V2\b_i,b_j\∩ V_2 are non-empty. Proof. By Lemma 5, a certifying solution contains exactly k sequences of 22 consecutive instances of distinct neighboring bus stops along the route. All such sequences start and end with a vertex in V1∪V2V_1∪ V_2 while the middle bus stop of such a sequence is c. Thus, a certifying solution contains c exactly k times. This means that, for a certifying bus route B, there are exactly 2k−12k-1 distinct pairs of connected vertices u′,v′∈V1∪V2u ,v ∈ V_1∪ V_2. Assume towards contradiction that at most 2k−22k-2 of those pairs are between V1V_1 and V2V_2. Then at most (2k−2)⋅γ(2k-2)·γ agents in ANA_N can travel both edges by bus. Since at most 2k⋅β2k·β edges are travelled by bus by neighbor agents even if all edges for agents in AEA_E are travelled by bus this leaves at most 2k⋅β+(2k−2+n⋅k)⋅γ+4⋅(n2)2k·β+(2k-2+n· k)·γ+4· n2 edges to be travelled by bus in B. Θ= = 2k⋅β+(2k−1+n⋅k)⋅γ+2k⋅(n−1) 2k·β+(2k-1+n· k)·γ+2k·(n-1) > > 2k⋅β+(2k−1+n⋅k)⋅γ 2k·β+(2k-1+n· k)·γ > > 2k⋅β+(2k−2+n⋅k)⋅γ+4⋅(n2) 2k·β+(2k-2+n· k)·γ+4· n2 Since 2k⋅β+(2k−2+n⋅k)⋅γ+4⋅(n2)<Θ2k·β+(2k-2+n· k)·γ+4· n2< , it follows that ftime(B)>Σf_time(B)> ; a contradiction. ∎ We will now prove Lemma 2. Proof of Lemma 2. (⇒)( ) By Lemma 4, for any graph with an independent set of size at least k, there exists a certifying solution. (⇐)( ) Let B be a certifying solution. To prove that we can construct an independent set of size k in G from B, we will go through the properties of a certifying solution. By Lemma 5, every certifying solution contains exactly 2k2k distinct pairs of neighboring bus stops along the route. Thus, at most 2k⋅β2k·β edges are travelled by bus by neighbor agents. By Lemma 6 there are exactly 2k−12k-1 distinct pairs of connected vertices between V1V_1 and V2V_2. First, this means that B contains exactly k vertices in V1V_1 and V2V_2 respectively. Second, since at most (2k−1)⋅γ(2k-1)·γ alternation agents can travel both edges by bus, even if every agent in A_A travels at least one edge by bus at most (2k−1+n⋅k)⋅γ(2k-1+n· k)·γ edges are travelled by bus by alternation agents. Since ftime(B)≤Σf_time(B)≤ at least Θ edges in B are travelled by bus. This leaves at least Θ−2k⋅β−(2k−1+n⋅k)⋅γ=k⋅2(n−1) -2k·β-(2k-1+n· k)·γ=k· 2(n-1) edges to be travelled by bus by agents in AEA_E. Let X=v∈V∣Xv∈BX=\v∈ V X_v∈ B\ be the set of vertices in G represented by the bus route. Since there are k bus stops in V1V_1 and none of them are connected, every agent in AEA_E travels at most one edge by bus and |X|=k|X|=k. For every bus stop Xv∈V1X_v∈ V_1, we define AvA_v as the set of agents in AEA_E that have XvX_v as an endpoint. For every bus stop Xv∈V1X_v∈ V_1, there are exactly 2(n−1)2(n-1) agents in AEA_E with one endpoint in XvX_v. As such |Av|=2(n−1)|A_v|=2(n-1) for all Xv∈B,Xv∈V1X_v∈ B,X_v∈ V_1. Agents in AEA_E can only use the bus if one of their endpoints in V1V_1 is also in B. Since agents in AEA_E travel at least k⋅2(n−1)k· 2(n-1) edges by bus, every agent in AEA_E travels at most one edge by bus and every agent in AEA_E that uses the bus is in some AvA_v it follows that |⋃v∈XAv|≥k⋅2(n−1)| _v∈ XA_v|≥ k· 2(n-1). Since ∑v∈XAv=k⋅2(n−1) _v∈ XA_v=k· 2(n-1) and |⋃v∈XAv|≥k⋅2(n−1)| _v∈ XA_v|≥ k· 2(n-1), this means that the sets AvA_v are pairwise disjoint. Since the sets AvA_v are pairwise disjoint there is no agent in AEA_E with endpoints Xv,Xu∈BX_v,X_u∈ B. By the definition of AEA_E this means that there exist no vertices u,v∈Xu,v∈ X such that u,v∈E\u,v\∈ E. Thus, X is an independent set. ∎ Since c is a bus stop in every bus route and between the endpoints for every agent, the proof above works for gtimeg_time as well. ∎ Theorem 1 and Proposition 2 cover all cases for stars and general trees except ftimef_time in the unweighted case. Theorem 7 shows that this can be solved in polynomial time on stars while Theorem 8 shows that it is NP-hard on general trees. Theorem 7. MBSP with objective function ftimef_time can be solved in polynomial time on stars in the unweighted case. Proof. In the unweighted star setting, the order of the bus stops is irrelevant. Although every agent must use the bus, an agent may board and leave at the same stop. Hence, for any selected stop set, each agent can realize its best possible cost by choosing a suitable single stop from that set. Consequently, we regard a solution simply as a set of stops. Let (G,A,k)(G,A,k) be an instance of MBSP on an unweighted star G with center c and leaf set L. For each leaf v∈Lv∈ L, let nvn_v be the number of agents whose start and destination are both v. Sort the leaves such that nv1≥⋯≥nv|L|n_v_1≥·s≥ n_v_|L| . Consider the two candidate solutions Bc≔c,v1,…,vk−1B_c \c,v_1,…,v_k-1\ and Bℓ≔v1,…,vkB_ \v_1,…,v_k\. We compute ftime(Bc)f_time(B_c) and ftime(Bℓ)f_time(B_ ) and return the better of the two. We prove correctness. First consider solutions that contain the center c. Then every agent whose endpoints are distinct vertices can realize its shortest-path distance by using c as its chosen stop. Thus the only part depending on the selected leaves is the contribution of agents with both endpoints at the same leaf. Such agents contribute 00 if their leaf is selected and 22 otherwise. Hence, among all solutions containing c, an optimal solution selects the k−1k-1 leaves with largest values nvn_v, namely BcB_c. It remains to consider solutions not containing c. Let S⊆LS L be a set of k selected leaves. Let x∈Sx∈ S be a selected leaf with minimum nxn_x. Compare S with the center-containing solution S′:=(S∖x)∪cS :=(S \x\)∪\c\. We analyze how the objective changes when x is replaced by c. The agents located at x increase their contribution from 00 to 2nx2n_x. For every leaf v∉Sv∉ S, the agents located at v decrease their contribution from 4nv4n_v to 2nv2n_v. Finally, every agent with distinct endpoints neither of which lies in S decreases its contribution from 44 to 22. Let q(S)q(S) denote the number of such agents. It follows that ftime(S′)−ftime(S)=2nx−2∑v∉Snv−2q(S)f_time(S )-f_time(S)=2n_x-2 _v∉ Sn_v-2q(S). Consequently, if nx≤∑v∉Snv+q(S)n_x≤ _v∉ Sn_v+q(S), then S′S is no worse than S. Now suppose that S is strictly better than every solution containing c. Then the above inequality must be false, and therefore nx>∑v∉Snv+q(S)≥∑v∉Snvn_x> _v∉ Sn_v+q(S)≥ _v∉ Sn_v. In particular, every selected leaf has strictly larger nvn_v than every unselected leaf. Hence S must be exactly the set of the k leaves with largest values nvn_v, that is, S=BℓS=B_ up to ties. If there is a tie between a selected and an unselected leaf, then nx≤∑v∉Snvn_x≤ _v∉ Sn_v, making the center-containing solution optimal. Thus every optimal solution is either the best solution containing the center, namely BcB_c, or the solution BℓB_ using the k leaves with largest values nvn_v. Both objective values can be computed in polynomial time, hence MBSP with objective ftimef_time is polynomial-time solvable on unweighted stars. ∎ Theorem 8. MBSP with objective function ftimef_time is NP-hard on trees in the unweighted case. Proof. We reduce from a Vertex Cover (14) instance (G,k)(G,k). We construct a tree T as follows. Add a root r. For every vertex v∈V(G)v∈ V(G), add two vertices v and v′v to T, connect v to r, and connect v′v to v. This yields a tree of height two. We now define the agent set A. Choose integers M>2|E(G)|M>2|E(G)| and N>2M⋅(|V(G)|−k)+2|E(G)|N>2M·(|V(G)|-k)+2|E(G)|. For every v∈V(G)v∈ V(G), add M agents whose start and end vertex is v (vertex agent set AvA_v), and N agents whose start and end vertex is v′v (prime agent set Av′A_v ). For every edge e=u,v∈E(G)e=\u,v\∈ E(G), add one agent aea_e starting at u and ending at v. Set the allowed number of bus stops to k′=|V(G)|+k =|V(G)|+k. This gives an instance (T,A,k′)(T,A,k ) of MBSP. We now show that (G,k)(G,k) is a yes-instance if and only if (T,A,k′)(T,A,k ) has a bus route B with ftime(B)≤2|E(G)|+2M⋅(|V(G)|−k)f_time(B)≤ 2|E(G)|+2M·(|V(G)|-k). (⇒ ) Let S be a vertex cover of G with |S|=k|S|=k. Place bus stops at all v′v and at all v∈Sv∈ S, using |V(G)|+k|V(G)|+k stops. The order of stops is irrelevant for the objective, since for ftimef_time an empty bus has no costs and in the unweighted case there is no difference between agents walking and agents taking the bus. For every v∉Sv∉ S, all agents in AvA_v must walk two edges to reach the corresponding prime bus stop and therefore contribute 2M2M. For v∈Sv∈ S the contribution is 00. Hence, the vertex agents contribute 2M⋅(|V(G)|−k)2M·(|V(G)|-k) in total. Furthermore, since we place bus stops at all v′∈V(T)v ∈ V(T) prime agents also have contribution 00. For every edge e=u,ve=\u,v\, at least one endpoint is a bus stop, so aea_e can take its shortest path and incurs cost 22. Hence, the edge agents contribute 2|E(G)|2|E(G)|. Thus, ftime(B)=2|E(G)|+2M⋅(|V(G)|−k)f_time(B)=2|E(G)|+2M·(|V(G)|-k). (⇐ ) Let B be a bus route with ftime(B)≤2|E(G)|+2M⋅(|V(G)|−k)f_time(B)≤ 2|E(G)|+2M·(|V(G)|-k). Since N>2M⋅(|V(G)|−k)+2|E(G)|N>2M·(|V(G)|-k)+2|E(G)|, any v′v not chosen as a bus stop would force each of its N agents to walk to a bus stop and back, thus leading to a cost of at least 22 per agent. By definition 2N>2M⋅(|V(G)|−k)+2|E(G)|2N>2M·(|V(G)|-k)+2|E(G)| exceeding the objective bound. Thus, all v′v must be bus stops. Furthermore, the root r cannot be a bus stop. Otherwise, only k−1k-1 vertices from V(G)V(G) could be chosen, and the vertex agents would contribute 2M⋅|V(G)|−2M(k−1)=2M+2M(|V(G)|−k)2M·|V(G)|-2M(k-1)=2M+2M(|V(G)|-k), which is larger than the allowed objective value since M>2|E(G)|M>2|E(G)|. Next, since all v′v are bus stops, each AvA_v agent contributes 2M2M unless v itself is a bus stop, in which case its contribution is 00. To reach the required total of 2M(|V(G)|−k)2M(|V(G)|-k), exactly k vertices of V(G)V(G) must be selected as bus stops. Let this set be SBS_B. The vertex-agent contribution is now fixed, so the edge agents must contribute at most 2|E(G)|2|E(G)|. An edge agent has cost 22 if at least one endpoint of its edge is a bus stop, and cost at least 44 otherwise (since r is not a bus stop and any detour increases distance). Thus, to keep the cost at most 2|E(G)|2|E(G)|, every edge must have at least one endpoint in SBS_B. Thus, SBS_B is a vertex cover of size k and (G,k)(G,k) is a yes-instance. ∎ Finally, we consider the case where the input graph is a path. Designing an efficient algorithm becomes challenging when agent weights are arbitrary. Intuitively, for an agent it may not be optimal to board and leave the bus at the stops closest to their start and end points, since other stops may lie in between. Thus, determining where an agent uses the bus may require knowing the full set of bus stop locations. We use this observation to prove the following. Theorem 9. MBSP with objective function ftimef_time or gtimeg_time is W[1]-hard on paths with arbitrary agent weights. Proof. We use a reduction from Independent Set which is W[1]-hard for the parameter k (8) to MBSP. An Independent Set instance consists of a graph G=(V,E)G=(V,E) and a budget k. The goal is to decide if there is an independent set X⊆VX V with |X|=k|X|=k and v,u∉E\v,u\∉ E for all v,u∈Xv,u∈ X. Let (G=(V,E),k)(G=(V,E),k) be an instance of Independent Set. Let n=|V|n=|V|. Let V→=(v1,v2,…,vn) V=(v_1,v_2,…,v_n) be any permutation of V. Let << be the strict linear order on V defined by V→ V. We construct an instance (G′,A,wb,wa,2k)(G ,A,w_b,w_a,2k) of MBSP as follows: V(G′)= V(G )= Xv∘∣v∈V,∘∈−,+ \X_v v∈ V, ∈\-,+\\ E(G′)= E(G )= E1∪E2 E_1∪ E_2 E1= E_1= Xvi−,Xvi+∣i∈[n] \\X_v_i^-,X_v_i^+\ i∈[n]\ E2= E_2= Xvi+,Xvi+1−∣i∈[n−1] \\X_v_i^+,X_v_i+1^-\ i∈[n-1]\ A= A= au,v(0)=(Xu−,Xv+,wuv)∣u,v∈E,u<v \a^(0)_u,v=(X_u^-,X_v^+,w_uv) \u,v\∈ E,u<v\ ∪ ∪ au,v(1)=(Xv−,Xv+,wuv),au,v(2)=(Xu−,Xu+,wuv) \a^(1)_u,v=(X_v^-,X_v^+,w_uv),a^(2)_u,v=(X_u^-,X_u^+,w_uv) ∣u,v∈V,u<v,u,v∉E u,v∈ V,u<v,\u,v\∉ E\ wb(e)= w_b(e)= 0 for e∈E1,wb(e)=3 for e∈E2 0 for e∈ E_1,\ \ \ w_b(e)=3 for e∈ E_2 wuv(e)= w_uv(e)= 1 for e∈Xu,−,Xu,+,Xv,−,Xv,+,u<v 1 for e∈\\X_u,-,X_u,+\,\X_v,-,X_v,+\\,u<v wuv(e)= w_uv(e)= 0 otherwise 0 otherwise In this construction G′G is a path between Xv1−X_v_1^- and Xvn+X_v_n^+. Every vertex v of the original graph G is represented by an edge Xvi−,Xvi+\X_v_i^-,X_v_i^+\ in G′G . Every agent incurs a cost of at most two when travelling by foot since they travel over up to two edges of weight 11. The only way to reduce that cost is to make them travel one of those edges by bus. The construction ensures that exactly k such edges can be chosen to be travelled by bus. Since each of those edges represents a vertex in G, those chosen k edges satisfy the objective function if and only if they represent an independent set of size k in G. Claim 0. The independent set instance has a solution if and only if the objective function gtimeg_time for instance constructed above is at most Σ=(n−k)⋅(n−1) =(n-k)·(n-1). Proof of the claim. We say an edge e∈E(G′)e∈ E(G ) is necessary for an agent a if e is on the unique path between the terminals of a and wa(e)≠0w_a(e)≠ 0. We say a needs the edge e. Every necessary edge contributes to the cost of a if and only if it is not traversed by bus. For every agent au,v(i)a^(i)_u,v the total cost to travel its entire path without the bus is at most 22. Thus, in all solutions minimizing gtimeg_time no agent uses the bus to travel over an edge e∈E2e∈ E_2. Since every path of length 22 or more in G′G contains an edge in E2E_2, in all solutions minimizing gtimeg_time, no agent uses the bus for more than one edge e∈E1e∈ E_1. Each edge Xw−,Xw+\X_w^-,X_w^+\ in E1E_1 is necessary for n−1n-1 agents. One per pair w≠v∈Vw≠ v∈ V. Namely, it is necessary for an agent a if a∈av,w(0),aw,v(0),av,w(1),aw,v(2)∣v∈V(G)a∈\a_v,w^(0),a_w,v^(0),a_v,w^(1),a_w,v^(2) v∈ V(G)\. The total cost of necessary edges is 2⋅(n2)=n⋅(n−1)2· n2=n·(n-1). To use the bus to travel exactly one edge e=Xv−,Xv+∈E1e=\X_v^-,X_v^+\∈ E_1 both Xv−X_v^- and Xv+X_v^+ have to be bus stops. Furthermore, every vertex is only part of one edge in E1E_1 meaning that at most k edges in E1E_1 can be travelled by bus. Thus, there remain n−kn-k edges in E1E_1 who have to be travelled by foot by the n−1n-1 agents who need them. The minimum cost of a solution is (n−k)⋅(n−1)(n-k)·(n-1). As a result, the only way to achieve gtime(B)≤(n−k)⋅(n−1)g_time(B)≤(n-k)·(n-1) is to choose k edges in E1E_1 such that every agent for whom those edges are necessary travels over that edge by bus. For a route B, let the up to k edges e∈E1e∈ E_1 that can individually be travelled by bus be called EBE_B. We define VB=v∈V∣Xv−,Xv+∈EBV_B=\v∈ V \X_v^-,X_v^+\∈ E_B\ as the set of corresponding vertices in G. B satisfies gtime(B)≤(n−k)⋅(n−1)g_time(B)≤(n-k)·(n-1) if |EB|=k|E_B|=k and every agent with 2 necessary edges(au,v(0)a_u,v^(0)) has at most one of them in EBE_B. Let B be a bus route B such that |EB|=k|E_B|=k and VBV_B is an independent set in G. Then since VBV_B is an independent set, there is no agent au,v(0)a_u,v^(0) such that u,v∈VBu,v∈ V_B. In contrast, if VBV_B is not an independent set in G, there exists an edge u,v∈E,u,v∈VB\u,v\∈ E,u,v∈ V_B and thus both edges necessary for au,v(0)a_u,v^(0) are in EBE_B, meaning that B does not satisfy gtime(B)≤(n−k)⋅(n−1)g_time(B)≤(n-k)·(n-1). ⋄ The proof extends to ftimef_time by adding bus stops at both ends of the path, ensuring that every agent can reach some stop without incurring cost. ∎ If we further restrict the problem to the unweighted case then we can solve MBSP in polynomial time. The case for gtimeg_time is covered by Proposition 2 while the case for ftimef_time is covered by Theorem 10. Theorem 10. MBSP with objective function ftimef_time can be solved in polynomial time on paths in the unweighted case. Proof. To obtain an algorithm for ftimef_time on unweighted paths we can slightly modify the dynamic programming algorithm for fenergyf_energy from Theorem 4. Since the bus costs are now counted per agent instead of once globally, we only need to change the main recurrence to the following: mini∈[j−1](D[k′−1,vi]+fA′(vi,vj)) _i∈[j-1] (D[k -1,v_i]+f _A(v_i,v_j) ). To calculate fA′(vi,vj)f _A(v_i,v_j) we need to sum up the contribution of each individual agent. For this we consider four different types of agents (vℓ,vr,w)∈A(v_ ,v_r,w)∈ A. Note that, since wa=wbw_a=w_b, an agent never needs to actually take the bus. They just need to walk to any bus stop and then to their end point. Case 11: i≤ℓ≤r≤ji≤ ≤ r≤ j. In this case the agent starts and ends between viv_i and vjv_j. Here the agent needs to walk to one of the two bus stops viv_i and vjv_j. The contribution of such an agent is min(π(vℓ,vi,w)+π(vi,vr,w),π(vℓ,vj,w)+π(vj,vr,w)) (π(v_ ,v_i,w)+π(v_i,v_r,w),π(v_ ,v_j,w)+π(v_j,v_r,w)). Case 22: ℓ<i≤r≤j <i≤ r≤ j. In this case only the end point is between viv_i and vjv_j. Here the agent can take the direct path from vℓv_ to vrv_r since viv_i is on the way. The contribution of such an agent is π(vi,vr,w)π(v_i,v_r,w). Case 33: i≤ℓ≤j<ri≤ ≤ j<r. In this case only the start point is between viv_i and vjv_j. Analogously to Case 22, the agent can take the direct path. The contribution of such an agent is π(vr,vj,w)π(v_r,v_j,w). Case 44: ℓ<i≤j<r <i≤ j<r. In this case neither start nor end point are between viv_i and vjv_j. Here the agent can also take the direct path. The contribution of such an agent is π(vi,vj,w)π(v_i,v_j,w). The rest of the algorithm works the same as in Theorem 4. ∎ 6. Experiments We evaluate the stop-selection algorithms on the NYC-M15 corridor (18), restricting the candidate set to existing stops. This models a setting common in public transport planning: the underlying corridor already exists, and the task is to choose which stops should be visited by an additional express line. Origin-destination pairs for the agents are obtained from Citi Bike NYC Trip History (4). We consider the scenario of adding an express line with k=10k=10 stops, where each agent has walking costs that are a factor w larger than the bus route costs and w is drawn uniformly at random from [1,2][1,2]. We compare three k=10k=10 selections: one minimizing genergyg_energy, one minimizing fenergyf_energy, and one using uniform spacing. Both optimized selections substantially outperform uniform spacing, reducing their respective objective costs by about 16.5%16.5\% and 16.8%16.8\%. Figure 3 shows that the selected stop sets depend on the objective. The two optimized solutions overlap in parts of the corridor, but they are not identical, illustrating that the two objectives capture different aspects of the stop-selection problem. In particular, genergyg_energy, which allows agents to walk directly, gives a more compact stop placement because it does not produce artificially high costs for areas without bus stops. Since the preferred stop set changes with the objective, both objectives are important to consider when evaluating stop-selection quality. genergyg_energy-optimalfenergyf_energy-optimaluniformexisting stops Figure 3. Comparison of three k=10k=10 stop selections on the NYC-M15 corridor, restricted to existing stops. 7. Conclusion There are several possibilities to expand our results. Clearly, the complexity of the four remaining path cases still needs to be resolved. Another direction is to generalize the positive results obtained for paths to larger classes of graphs. However, for all objective functions except fenergyf_energy we have hardness already for stars, which excludes positive results for graphs with pathwidth 2, the most obvious next step beyond paths. Thus, even stronger restrictions such as bounded maximum degree seem necessary to extend the positive results. Another and possibly more fruitful direction could be to consider further types of agent models, for example the case where edge weights for the agents are never smaller than bus-edge weights. One could also study an intermediate model between arbitrary weights and consistent weights, where there is only a bounded number of distinct agent weight functions. Finally, a parameter that is typically large in the instances constructed by our reductions is the number of agents. Thus, it remains unclear whether the problem is still hard when this parameter is small. From a theoretical perspective, it would be interesting to determine whether FPT algorithms parameterized by the number of agents exist. Acknowledgements Jurek Rostalsky and Luca Pascal Staus were supported by the Carl Zeiss Foundation, Germany, within the project “Interactive Inference”. Eva Deltl acknowledges her support by the Deutsche Forschungsgemeinschaft (German Research Foundation, DFG), project COMSOC-MPMS (grant agreement No. 465371386) and project MaMu (grant agreement No. 392018064). References Avilés-González et al. (2020) J. F. Avilés-González, J. Mora-Vargas, N. R. Smith, and M. G. Cedillo-Campos Artificial intelligence and DOE: an application to school bus routing problems. Wireless Networks 26 (7), p. 4975–4983. Cited by: §1.2. Aziz et al. (2020) H. Aziz, H. Chan, B. Lee, B. Li, and T. Walsh Facility location problem with capacity constraints: algorithmic and mechanism design perspectives. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, p. 1806–1813. External Links: Link, Document Cited by: §1.2. Çağrı Koç et al. (2020) Çağrı Koç, G. Laporte, and İ. Tükenmez A review of vehicle routing with simultaneous pickup and delivery. Computers & Operations Research 122, p. 104987. External Links: ISSN 0305-0548, Document, Link Cited by: §1.2. [4] Citi BikeCiti bike system data(Website) Note: https://citibikenyc.com/system-data External Links: Link Cited by: §6. Cornuéjols et al. (1983) G. Cornuéjols, G. Nemhauser, and L. Wolsey The uncapacitated facility location problem. Technical report Cornell University Operations Research and Industrial Engineering. Cited by: §1. Cygan et al. (2015) M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh Parameterized algorithms. Springer. Cited by: §2. Derrible and Kennedy (2011) S. Derrible and C. Kennedy Applications of graph theory and network science to transit network design. Transport Reviews 31 (4), p. 495–519. External Links: Document Cited by: §1.2. Downey and Fellows (2013) R. G. Downey and M. R. Fellows Fundamentals of parameterized complexity. Texts in Computer Science, Springer. External Links: Link, Document, ISBN 978-1-4471-5558-4 Cited by: §2, §3, §4, §5. Everett and Borgatti (1999) M. G. Everett and S. P. Borgatti The centrality of groups and classes. The Journal of Mathematical Sociology 23 (3), p. 181–201. External Links: Document, Link, https://doi.org/10.1080/0022250X.1999.9990219 Cited by: §1.2. Fellows and Fernau (2011) M. R. Fellows and H. Fernau Facility location problems: a parameterized view. Discrete Applied Mathematics 159 (11), p. 1118–1130. External Links: ISSN 0166-218X, Document, Link Cited by: §1. Furth and Rahbee (2000) P. G. Furth and A. B. Rahbee Optimal bus stop spacing through dynamic programming and geographic modeling. Transportation Research Record 1731 (1), p. 15–22. External Links: Document Cited by: §1.2. Guihaire and Hao (2008) V. Guihaire and J. Hao Transit network design and scheduling: a global review. Transportation Research Part A: Policy and Practice 42 (10), p. 1251–1273. External Links: Document Cited by: §1.2. Hakimi and Kariv (1979) S. Hakimi and O. Kariv An algorithmic approach to network location problems i: the p-medians. SIAM Journal on Applied Mathematics 37 (3), p. 539–560. Cited by: §1. Karp (1972) R. M. Karp Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, p. 85–103. Cited by: §5. Labbé et al. (2004) M. Labbé, G. Laporte, I. R. Martín, and J. J. S. González The ring star problem: polyhedral analysis and exact algorithm. Networks 43 (3), p. 177–189. External Links: Document, Link, https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.10114 Cited by: §1.2. Ljubić (2020) I. Ljubić Connected facility location problems. In Encyclopedia of Optimization, p. 1–11. External Links: ISBN 978-3-030-54621-2, Document, Link Cited by: §1.2. Manerba et al. (2017) D. Manerba, R. Mansini, and J. Riera-Ledesma The traveling purchaser problem and its variants. European Journal of Operational Research 259 (1), p. 1–18. External Links: ISSN 0377-2217, Document, Link Cited by: §1.2. [18] Metropolitan Transportation AuthorityMTA developer resources(Website) Note: https://w.mta.info/developers External Links: Link Cited by: §6. Moradi et al. (2024) N. Moradi, F. Mafakheri, and C. Wang Set covering routing problems: a review and classification scheme. Computers & Industrial Engineering 198, p. 110730. External Links: ISSN 0360-8352, Document, Link Cited by: §1.2. Owais (2026) M. Owais Transit network design problem: a half century of methodological research. Innovative Infrastructure Solutions 11 (3). External Links: Document Cited by: §1.2. Park and Kim (2010) J. Park and B. Kim The school bus routing problem: A review. European Journal of Operational Research 202 (2), p. 311–319. External Links: Link, Document Cited by: §1.2. Proissl and Koch (2024) C. Proissl and D. Koch Revisiting the bus stop problem in road networks. In Proceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’24, Atlanta, GA, USA, p. 80–90. Cited by: §1, §2, §2. Reza et al. (2017) R. M. Reza, M. E. Ali, and M. A. Cheema The optimal route and stops for a group of users in a road network. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL’17, New York, NY, USA. External Links: ISBN 9781450354905, Link, Document Cited by: §1, §1, §2. Schittekat et al. (2013) P. Schittekat, J. Kinable, K. Sörensen, M. Sevaux, F. C. R. Spieksma, and J. Springael A metaheuristic for the school bus routing problem with bus stop selection. European Journal of Operational Research 229 (2), p. 518–528. External Links: Link, Document Cited by: §1.2. Staus et al. (2023) L. P. Staus, C. Komusiewicz, N. Morawietz, and F. Sommer Exact algorithms for group closeness centrality. In SIAM Conference on Applied and Computational Discrete Algorithms, ACDA 2023, Seattle, WA, USA, May 31 - June 2, 2023, J. W. Berry, D. B. Shmoys, L. Cowen, and U. Naumann (Eds.), p. 1–12. External Links: Link, Document Cited by: §1.2. Tamir (1996) A. Tamir An O(pn2)O(pn^2) algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett. 19 (2), p. 59–64. Cited by: §1.2. Xiao et al. (2022) M. Xiao, J. Zhang, and W. Lin Parameterized algorithms and complexity for the traveling purchaser problem and its variants. Journal of Combinatorial Optimization 44 (4), p. 2269–2285. External Links: ISSN 1382-6905, Link, Document Cited by: §1.2.