2026/02/28 by Martin Bullinger, Edith Elkind, Kassian Köck
Computer Science · #cs.GT #cs.MA
arxiv created 2026/07/30 · arxiv updated 2026/07/31
We study a stylized model of infrastructure investment in public transportation. In our model, each agent travels between a pair of terminals in a network captured by a weighted graph, where edge weights represent distances. The central planner can improve the travel time along a fixed number of edges, with the goal of maximizing the utilitarian or egalitarian welfare. When there is only one agent, we provide a polynomial-time algorithm that combines Dijkstra's algorithm with a dynamic program. We then demonstrate how to use this algorithm as a subroutine to solve the problem for two agents. Generalizing this idea, we present an XP algorithm parameterized by the number of agents. However, our problem turns out to be W[1]-hard with respect to the number of agents. Nevertheless, we obtain a fixed-parameter tractability result for the special case where all agents travel to a common hub. If the number of agents is variable, we obtain NP-completeness and inapproximability results. We discuss implications of our results for a related model of railway network design.