Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas

Till Fluschnik

cs.DSAug 10, 2026

Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas

Authors: Till Fluschnik

Organizations: Humboldt-Universität zu Berlin, Department of Computer Science, Algorithm Engineering Group, Germany

Abstract

We introduce the \emph{Safe Bicycle Network with Bounded Detours} (\emph{SBNBD}) problem, motivated by upgrading rural road networks for bicycle traffic. Given an undirected graph with safe and unsafe edges, edge lengths, upgrade costs, terminal pairs, a budget, and a detour factor $α$ , the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path of length at most $α$ times its shortest-path distance in the original network. We study SBNBD from a parameterized perspective. We prove strong NP-hardness on restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three, and complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. We show fixed-parameter tractability for the number of unsafe edges and prove matching SETH-based lower bounds, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main structural result maps any instance to an equivalent instance with $O(\mathrm{fes}+p)$ vertices and edges, where $\mathrm{fes}$ is the feedback edge number and $p$ the number of terminal pairs; this yields fixed-parameter tractability for $\mathrm{fes}+p$ . Finally, we evaluate ILP-based algorithms on OpenStreetMap road networks for small German municipalities and their surroundings. The instances have small treewidth upper bounds and moderate feedback edge structure. Preprocessing based on the $\mathrm{fes}+p$ reduction and tree-decomposition-based cut generation both improve exact solving, especially on harder instances. Experiments with different detour factors show that increasing $α$ can reduce the upgraded-edge length, revealing trade-offs between upgrade cost and allowed relative detours. Overall, structural graph parameters provide a useful algorithmic lens for safe bicycle-network design.

Explore similar work

May 13, 2026cs.LG

Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

The multicut problem is an NP-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural networks have been defined for the multicut problem but can be adapted further to its specific objective function and constraints. In this article, we introduce such an adapted graph neural network architecture in which features are assigned only to edges, and the computation of messages is based on triangles in the underlying graph. Experiments with synthetic and real-world instances with up to 200 nodes show that our method outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. For some instances, our method finds optimal solutions in seconds whereas exact solvers need hours to find and certify optimal solutions.

Jannik Irmai, Lucas Fabian Naumann, Bjoern Andres

Maximum Independent Set Graph Neural Networks Combinatorial Optimization Np-Hard Edge

Ask PDF

May 27, 2026cs.AI

AlphaTransit: Learning to Design City-scale Transit Routes

Designing a transit network requires many sequential route extension decisions, but their quality is often visible only after the full network is assembled. This delayed-feedback challenge lies at the heart of the Transit Route Network Design Problem (TRNDP), where route interactions can be deceptive: an extension that appears useful locally can create transfer bottlenecks, produce redundant overlap, or reduce overall throughput. To guide route construction under delayed simulator feedback, we introduce AlphaTransit, a search-based planning framework for cityscale bus network design. AlphaTransit couples Monte Carlo Tree Search (MCTS) with a neural policy-value network: the policy proposes route extensions, the value estimates downstream design quality, and search uses these predictions to refine each decision. This provides decision-time lookahead during route construction without running simulator rollouts inside the search tree. We evaluate AlphaTransit on a new Bloomington TRNDP benchmark with realistic road topology and censusderived demand, under mixed and full transit demand settings. In the Bloomington network, AlphaTransit attains the highest service rate in both demand settings, reaching 54.6% and 82.1%, respectively. Relative to reinforcement learning without search, these correspond to 9.9% and 11.4% service rate gains; relative to MCTS without learned guidance, they correspond to 2.5% and 11.2% gains. These results suggest that coupling learned guidance with MCTS is more effective than using either approach alone for transit network design. Our code and data are publicly available in https://github.com/poudel-bibek/AlphaTransit.

Bibek Poudel, Sai Swaminathan, Weizi Li

Transit Network Design Monte Carlo Tree Search

Ask PDF

Jul 26, 2026cs.CC

Maximum Satisfiability of Simple Temporal Problems

The Simple Temporal Problem (STP) is a core framework for quantitative temporal constraints. As STP data can be inconsistent, we study MAXSTP: compute a maximum-cardinality consistent subset of constraints. This extension is NP-hard, and we analyze its parameterized complexity under measures that capture practically relevant instance features: the number of variables

n

(instance scale), the maximum coefficient magnitude

k

(numeric range), and structural parameters of the constraint graph such as treewidth

tw

(decomposability) and vertex cover size

vc

(density). We show that MAXSTP is W[1]-hard parameterized by

n

, implying that

n

and parameters that depend on

n

(including

tw

and

vc

) are insufficient for fixed-parameter tractability. For combined parameters, we give an

O^*(k^n)

-time algorithm, yielding single-exponential solvability for fixed

k

. While

k+tw

remains W[1]-hard, MAXSTP is in XP via an

O^*((n\cdot k)^{tw})

algorithm. Our results suggest that MAXSTP is often computationally harder than optimizing qualitative CSPs. We verify that many such problems (including RCC-8 and Allen's algebra) are FPT when parameterized by

n

tw

. However, we also demonstrate that FPT algorithms for MAXSTP are indeed possible but with other parameters such as

k + vc

Johannes K. Fichte, Johanna Groven, Peter Jonsson +2

Satisfiability

Ask PDF