Paper deep dive
Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas
Till Fluschnik
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 8/13/2026, 3:30:45 AM
Summary
This paper introduces the Safe Bicycle Network with Bounded Detours (SBNBD) problem, aiming to upgrade rural road networks for safe bicycle traffic by selecting unsafe edges to upgrade within a budget, ensuring terminal pairs are connected by safe paths with detours bounded by a factor α. The authors analyze the computational complexity, proving strong NP-hardness on restricted graph classes (planar graphs, treewidth 2, max degree 3) and establishing fixed-parameter tractability for parameters like the number of unsafe edges and the combined feedback edge number plus terminal pairs (fes+p). Experimental results on OpenStreetMap data from German rural areas demonstrate that structural graph parameters like treewidth and feedback edge number are small, and that preprocessing based on fes+p reduction and tree-decomposition-based cut generation significantly improve exact ILP solving performance.
Entities (7)
Relation Signals (6)
SBNBD → hascomplexity → NP-hardness
confidence 95% · We prove strong NP-hardness on restricted graph classes, including planar graphs of treewidth two...
SBNBD → isfptfor → fes+p
confidence 95% · this yields fixed-parameter tractability for fes+p
SBNBD → isappliedto → OpenStreetMap
confidence 90% · Finally, we evaluate ILP-based algorithms on OpenStreetMap road networks for small German municipalities
German municipalities → hasgraphproperty → small treewidth
confidence 85% · The instances have small treewidth upper bounds
ILP → isimprovedby → preprocessing
confidence 85% · Preprocessing based on the fes+p reduction and tree-decomposition-based cut generation both improve exact solving
detour factor → affects → upgrade cost
confidence 80% · increasing α can reduce the upgraded-edge length, revealing trade-offs between upgrade cost and allowed relative detours
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\alpha$, the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path of length at most $\alpha$ 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 $\alpha$ 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.
Tags
Links
- Source: https://arxiv.org/abs/2608.09472v1
- Canonical: https://arxiv.org/abs/2608.09472v1
Trouble viewing inline? Open PDF directly →
Full Text
95,302 characters extracted from source content.
Expand or collapse full text
Humboldt-Universität zu Berlin, Department of Computer Science, Algorithm Engineering Group, Germanytill.fluschnik@hu-berlin.dehttps://orcid.org/0000-0003-2203-4386Funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), project PACS (FL 1247/1-1, 522475669). . Fluschnik [500]Theory of computation Design & analysis of algorithms [500]Mathematics of computing Combinatorial optimization [500]Social & professional topics Sustainability and data for the experiments are available at https://github.com/buhtig-tf/Safe-Bicycle-Network-Design-with-Bounded-Detours. Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas Till Fluschnik Abstract We introduce the Safe Bicycle Network with Bounded Detours (SBNBD) problem, a network-design problem motivated by the upgrade of rural road networks for bicycle traffic. Given an undirected graph whose edges have length and are classified as safe or unsafe with unsafe edges carrying upgrade costs, a set of terminal pairs, an upgrade budget, and a detour factor α, the task is to upgrade unsafe edges so that every terminal pair is connected by a safe path whose length is at most α times its shortest-path distance in the original network. We study the computational complexity of SBNBD from a parameterized perspective. We prove strong NP-hardness even on highly restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three. We complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. For parameterized complexity, we show fixed-parameter tractability for the number of unsafe edges and prove matching lower bounds under SETH, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main positive structural result is an algorithm that maps any instance to an equivalent instance with O(fes+p)O(fes+p) vertices and edges, where fesfes is the feedback edge number and p is the number of terminal pairs; this yields fixed-parameter tractability for the combined parameter fes+pfes+p. Finally, we construct and evaluate exact ILP-based algorithms on road networks derived from OpenStreetMap data for small German municipalities and their surrounding rural regions. The experiments show that these networks have small treewidth upper bounds and moderate feedback edge structure. We introduce a preprocessing routine based on the reduction algorithm for the parameter fes+pfes+p and a heuristic cut generation based on tree decompositions. Both improve exact solving performance, in particular for harder instances. Our results for different detour-factor bounds show that a moderate increase in α can substantially reduce the total length of the upgraded network, revealing practical trade-offs between upgrade budget and the maximum allowed relative detour. Our results indicate that structural graph parameters provide a useful algorithmic lens for safe bicycle-network design in rural areas. keywordsParameterized Algorithms, NP-hardness, Pairwise weighted spanners, Preprocessing, Integer linear programming, Cut generation category 1 Introduction Improving bicycle networks for urban and rural areas can help to reduce pollution [35], promote physical activity [37], and mitigate transport poverty [45]. Compared with urban areas, both public transport and bicycle infrastructure are often insufficient in rural regions [46]. Since improving public transport in rural areas is often economically challenging [17] and people use cars even for short-distance rides [2, 23], cost-effective improvement of bicycle networks becomes a central planning task. In Germany, 54% of respondents living in rural areas with less than 20,000 inhabitants report that they would like to use bicycles more frequently in the future [42]. High-quality, connected cycling infrastructure could roughly triple cycling use by 2035 (up to 45% modal share on short trips), with significant untapped potential also in rural areas [12]. Other mobility solutions like bike-sharing for rural areas [38] benefit from such infrastructure. Safety and bounded detour length [20, 40] are key criteria for a network’s quality. This paper treats the problem of cost-optimal infrastructure upgrades in a given network to enable safe bicycle trips for specified terminal pairs with only small detours. Herein, the network’s edges are classified either as safe or unsafe, corresponding to low- and high-stress segments [21]. Our model is based on the bicycle network improvement problem due to Lim et al. [32]. They optimize an aggregate objective over weighted origin-destination pairs, while we impose hard relative detour constraints. They study the problem from an OR perspective, while we study the problem from a computational and parameterized complexity perspective, with a focus on graph-theoretical properties derived from the applications on rural areas. Several models similar to ours are already studied in the scientific literature, yet a fine-grained computational and parameterized complexity analysis seems to be missing to date. We complement our complexity analysis with experimental algorithmics. 1.1 Our Model and Decision Problem We model the street network as an undirected graph G with a set V of vertices (representing junctions or points of interest like schools) and a set E⊆(V2)E V2 of edges (representing street segments), where the edge set E is partitioned into two sets EsE_s and EuE_u of safe and unsafe edges. Each edge is equipped with a (travel) length θ:E→ℕθ E , representing the length of or the time needed to traverse the street segment. Moreover, each unsafe edge is equipped with a cost c:Eu→ℕc E_u , representing the cost to make it safe (e.g, by constructing a bike lane on this street segment). For an edge subset F⊆EuF E_u, we denote by G⟨F⟩G F the graph G with edge set partitioned into Es′=Es∪FE_s =E_s∪ F and Eu′=Eu∖FE_u =E_u F. A terminal pair consists of two distinct vertices from V, representing the endpoints of a requested bicycle trip. For two distinct vertices s,t∈Vs,t∈ V, an s-t path P is a sequence (v0,v1,…,vℓ)(v_0,v_1,…,v_ ) of distinct vertices from V with v0=sv_0=s and vℓ=tv_ =t such that vi−1,vi∈E\v_i-1,v_i\∈ E for all i∈[ℓ]i∈[ ]. The length len(P) (P) of P is ∑i=1ℓθ(vi−1,vi) _i=1 θ(\v_i-1,v_i\). With distG(s,t) _G(s,t) we denote the smallest length of an s-t path in G. We call path P safe if vi−1,vi∈Es\v_i-1,v_i\∈ E_s for all i∈[ℓ]i∈[ ], and unsafe otherwise. We often drop the graph from the notation when it is clear from the context. The detour factor of an s-t path P in G is len(P)/dist(s,t)∈ℚ≥1 (P)/ (s,t) _≥ 1. Problem 1 (Safe Bicycle Network with Bounded Detours (SBNBD)). Given a network G=(V,E,c,θ)G=(V,E,c,θ) with E=Es⊎EuE=E_s E_u, a set of p∈ℕp terminal pairs =si,ti∣i∈[p]P=\\s_i,t_i\ i∈[p]\ from V, a budget k∈ℕ0k _0, and a number α∈ℚ≥1α _≥ 1, the question is whether there is a solution F⊆EuF E_u with c(F)=∑e∈Fc(e)≤kc(F)= _e∈ Fc(e)≤ k such that for each i∈[p]i∈[p], there is a safe sis_i-tit_i path in G⟨F⟩G F of detour factor at most α. 1.2 Our Contributions Our contributions are two-fold. First, we provide a computational and parameterized complexity analysis for SBNBD. Second, we study exact ILP-based algorithms experimentally, focusing on the impact of reduction rules and treewidth-based cut generation. Computational and parameterized complexity. Figure 1 arranges our complexity-theoretic results. We prove that SBNBD is NP-hard in very restricted settings, such as vertex cover number two, or treewidth two and maximum degree three. nnmm≡no iso iso≡p fes+p fes+p+Δ tw+ fvs vcn twΔ |Es||E_s| m_u c_u mcc_ukkp+kp+knnmm≡no iso iso≡p fes+p fes+p+Δ tw+ fvs vcn twΔ |Es||E_s| m_u c_u mcc_ukkp+kp+kpara-NP-hardW-hardFPTopenA001122334455 mcc_u c_u|Es||E_s| tw fvs vcnΔ +Δ tw+ (a)(b) Figure 1: (a) Hasse diagram of our studied parameters with their complexity classification assuming unary encoding. Number n of vertices and number m of edges are parameterized equivalent when there are no isolated vertices. A parameter x points to another parameter y if there is a function f such that x≤f(y)x≤ f(y) holds for every instance. Thus, fixed-parameter tractability for x transfers to y, while hardness for y transfers to x. (b) Overview of the polynomial-time solvability (green) versus NP-hardness (red) borders for para-NP-hard parameters. ( m_u: number of unsafe edges; c_u: number of components in the graph induced by all unsafe edges; mcc_u: size of the largest component in the graph induced by all unsafe edges.) Each of our para-NP-hardness results is tight in the sense that the next smaller parameter value leads to polynomial-time solvability. We prove W[1]-hardness when parameterized by number of terminal pairs combined with the budget. For binary-encoded edge lengths and costs, we prove NP-hardness already for one terminal pair. Finally, we show several reduction rules that transform any instance to an equivalent instance whose combinatorial size is linear in the number of terminal pairs and the feedback edge number, i.e., the size of a minimum feedback edge set. These reduction rules are also effective as preprocessing in our experiments. Experimental algorithmics. Using OpenStreetMap data, we extracted undirected road networks for 30 German villages and their 3 km3\,km surrounding rural areas. These villages were selected from a ranking of over 400 German villages according to their perceived bicycle friendliness. For these networks, we then computed the maximum degree, the size of a minimum feedback edge set, small upper bounds on the treewidth, and checked for planarity. Our main findings are that these networks have small maximum degree ≤5≤ 5, small treewidth upper bound ≤14≤ 14, and roughly 20% of the edges suffice on average as a feedback edge set. We tested a plain ILP against the ILP with preprocessing via reduction rules, with additional cuts derived from a tree decomposition (TD), and with both. Our results are: 1. Most instances obtained for villages are solvable within seconds by each of the solvers. 2. For the larger instances, preprocessing combined with cut generation performed best. 3. The total length of upgraded unsafe edges decreases by 7.87%7.87\% on average when α increases from 1.21.2 to 1.31.3, illustrating the trade-off between allowed detours and required upgrades. 2 Related Work Improving bicycle networks. One line of research develops computational optimization models for bicycle-network design and improvement. Lim et al. [32] consider weighted terminal pairs and optimize the weighted detour penalty aggregated over each trip. They formulate their problem as mixed integer program (MIP) and solve it via Benders decomposition on a case-study instance. Duthie and Unnikrishnan [15] study “retrofitting” segments at minimum cost to ensure a minimum safety level with a given bounded detour. Compared to our model, their segments can have several safety levels and they express their length-bound through a function of the shortest path. While structurally, their focus is on roadway quality, ours is on parameters observed in rural areas. Mauttone et al. [34] model user route choices in a multi-commodity-flow MIP solved heuristically, allowing routes to use segments without bicycle infrastructure at higher cost. In contrast, we require each terminal pair to have safe route of bounded relative detour. Natera et al. [36] use a greedy strategy to compute missing links to interconnect components of the bicycle network. Steinacker et al. [43] use greedy network sparsification to design efficient urban bicycle networks, incorporating cycling demand and route choices based on safety preferences. To the best of our knowledge, computational or parameterized complexity analyses are missing for bicycle-network improvement problems with infrastructure upgrades under hard detour constraints. Another line of research analyzes existing bicycle networks and their growth. Szell et al. [44] argue that uncoordinated enhancement of bicycle networks can lead to higher cost and outline the need for careful planning. Schoner and Levinson [40] analyzed 74 bicycle networks from the US and found that connectivity and directness are important factors. Finally, Furth et al. [21] developed a framework to classify street segments as low- to high-stress segments. Algorithmics of related problems. By assigning zero cost to safe edges and positive cost to unsafe edges, our problem can be viewed as an undirected pairwise weighted spanner or as a distance-constrained Steiner-type problem. Cygan et al. [11] study sparse pairwise spanners in unweighted undirected graphs where the possible increase of a pairwise distance is controlled by a stretch function. They study existential bounds and give a polynomial-time construction for additive stretch functions. Approximation algorithms and hardness results for spanner-type problems have been studied on unweighted graphs [8] and weighted directed graphs [24]. Kobayashi [30] studies the all-pairs t-spanners in unweighted undirected graphs, where each pair’s distance is allowed to increase within a factor of t. They prove NP-hardness even in planar bounded-degree graphs. Moreover, they show an FPT algorithm when parameterized by the number of discarded edges (Kobayashi [31] proved such an algorithm to exist also for additive spanners). Regarding parameterized complexity, Feldmann and Lampis [18] study the related problem Steiner Forest with terminal pairs (which has no detour constraints). They focus on structural parameters and prove an EPAS with running time depending on treewidth (the problem is para-NP-hard already for =3 tw=3 [22]). They also prove an FPT algorithm when parameterized by the size of a feedback edge set. Simonov [41] study the problem of computing pairwise distance preservers in undirected unweighted graphs, where no increase in path length is allowed between any terminal pair. They prove W[1]-hardness when parameterized by the number of terminal pairs and NP-hardness for vertex cover number =3 vcn=3. Thus, we can view our problem as an undirected common-stretch pairwise weighted spanner problem with designated safe edges of zero cost and unsafe edges of positive cost; to the best of our knowledge, a systematic parameterized complexity study is missing for this variant. Structural parameters of real-world graphs. Maniu et al. [33] study the treewidth of 25 networks from eight different domains, including infrastructure. They find that many of these networks have treewidth too large for a direct application of treewidth-based algorithms. In contrast, we show that the street networks derived from rural areas admit small treewidth upper bounds. Analyzing large-scale street networks using OSM data has become common [4, 5, 16]. Related to the feedback edge number, the meshedness coefficient of planar real-world street networks is studied [7], which relates the numbers of bounded faces of the network and of a maximally connected planar graph with the same number of vertices. In connected planar graphs, the number of bounded faces equals the feedback edge number. To the best of our knowledge, classic FPT parameters such as treewidth or feedback edge number have not been measured for larger datasets of rural street networks. 3 Preliminaries We denote by ℕN and ℕ0N_0 the natural numbers excluding and including zero, respectively. We denote by ℚQ and ℚ≥1Q_≥ 1 the rational numbers and the rational numbers at least one, respectively. We use basic notation from parameterized complexity [10]. We use common graph-theoretic notation and explain only notation that may be non-standard. For an undirected graph G=(V,E)G=(V,E), we denote the vertex and edge set of G by (G) V(G) and (G) E(G), respectively. For an edge subset E′⊆E E, we denote by G[E′]=(V′,E′)G[E ]=(V ,E ) with V′=v∈V∣∃e∈E′:v∈eV =\v∈ V ∃ e∈ E :v∈ e\ the edge-induced graph G induced on the edge set E′E . We write G−E′G-E for the graph (V,E∖E′)(V,E E ). For a vertex subset U⊆VU V, we denote by ∂G(U)=v,w∈E∣|v,w∩U|=1 _G(U)=\\v,w\∈ E |\v,w\∩ U|=1\ the cut for U in G, i.e., all edges in G with exactly one endpoint in U. 4 Tight Strong NP-hardness on Simple Graph Classes Theorem 4.1. SBNBD is NP-hard even on planar graphs with treewidth =2 tw=2, and (a) feedback vertex set size =1 fvs=1, =1 mcc_u=1, and the graph is bipartite. (b) feedback vertex set size =1 fvs=1, vertex cover number =2 vcn=2, and =1 c_u=1. (c) maximum degree Δ=3 =3, =1 mcc_u=1, and the graph is bipartite. Moreover, unless the ETH breaks, there is no 2o(n+m)⋅poly(|I|)2^o(n+m)· (|I|)-time algorithm. We give three polynomial-time many-one reductions, each from the NP-hard [28] Problem 1. Vertex Cover problem, where, given an undirected graph G=(V,E)G=(V,E) and an integer r, the question is whether there is a subset W⊆VW V with |W|≤r|W|≤ r such that e∩W≠∅e∩ W≠ for every e∈Ee∈ E. Problem 2. Vertex Cover admits no 2o(|V|+|E|)⋅poly(|I|)2^o(|V|+|E|)· (|I|)-time algorithm unless the ETH breaks [27, 26]. Construction 1. (a)C111|1 [rgb]0,0,01|14411111|1 [rgb]0,0,01|14411111|1 [rgb]0,0,01|14411111|1 [rgb]0,0,01|14411⋮ ⋮ ⋮ ⋮ (b)CuC_uCsC_s1|1 [rgb]0,0,01|1441|1 [rgb]0,0,01|1441|1 [rgb]0,0,01|1441|1 [rgb]0,0,01|14411⋮ ⋮ ⋮ (c)⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 11n|1 [rgb]0,0,0n|13n3n1111n|1 [rgb]0,0,0n|13n3n1111n|1 [rgb]0,0,0n|13n3n1111n|1 [rgb]0,0,0n|13n3n11111111111111⋯·s⋯·s⋯·s⋯·s Figure 2: Illustrations for 1(a), (b), and (c). An unsafe edge e is drawn red and marked with its length and cost as θ(e)|c(e)θ(e) [rgb]1,0,0|c(e). Frames depict terminal pairs, i.e., two vertices with the same frame (size and color) form a terminal pair. Let I=(G=(V,E),r)I=(G=(V,E),r) be an instance of Problem 3. Vertex Cover with η=|V|η=|V| vertices. In each construction, we construct a graph G′G that contains a vertex v∗v^* for each vertex v∈Vv∈ V, the set of terminal pairs is =v∗,w∗∣e=v,w∈EP=\\v^*,w^*\ e=\v,w\∈ E\, and we have k=rk=r. See Figure 2 for an illustration to each of the three constructions. (a) Add a central vertex C. For each vertex v∈Vv∈ V, add two vertices vu,vsv_u,v_s, and add unsafe edge vu,v∗\v_u,v^*\ of length 1 and cost 1, and safe edge v∗,vs\v^*,v_s\ of length 4. Make C adjacent to each of vu,vsv_u,v_s for each v∈Vv∈ V via a safe edge of length 1. Let α≔2α 2. (b) There are two central vertices Cs,CuC_s,C_u (which form the vertex cover of the constructed graph) connected by a safe edge of length 11. For each vertex v∈Vv∈ V, connect v∗v^* with CsC_s via a safe edge of length 4, and with CuC_u via an unsafe edge of length 1 and cost 1. Let α≔3α 3. (c) We can assume that η≔|V|=2qη |V|=2^q for some q∈ℕq and 2log(η)+4<η2 (η)+4<η (by padding isolated vertices). Let G′G be initially a binary tree TηT_η with set ℓv∣v∈V\ _v v∈ V\ of η leaves. For each vertex v∈Vv∈ V, add two vertices vu,vsv_u,v_s, and add unsafe edge vu,v∗\v_u,v^*\ of length η and cost 1, and safe edge v∗,vs\v^*,v_s\ of length 3η3η. Make ℓv _v adjacent with each of vu,vsv_u,v_s for each v∈Vv∈ V via a safe edge of length 1. Let α≔2α 2. ⋄ Each constructed network has treewidth at most two. For (a) and (b), removing C and CuC_u, respectively, leaves a forest. For (c), start with a tree decomposition of width 1 for TηT_η. For every v∈Vv∈ V, choose a node whose bag contains ℓv _v and append a node with bag ℓv,vu,vs\ _v,v_u,v_s\. To this new node, append another node with bag vu,vs,v∗\v_u,v_s,v^*\. Proof 4.2 (Proof of Theorem 4.1). Let I′=(G′=(V′,E′,c,θ),,k,α)I =(G =(V ,E ,c,θ),P,k,α) be the instance of SBNBD obtained in polynomial time from an instance I=(G=(V,E),r)I=(G=(V,E),r) of Problem 4. Vertex Cover via 1(a), (b), or (c). By construction, for each terminal pair s,t\s,t\, every s-t path with detour factor at most α must contain an unsafe edge. For (a), the shortest path is of length 44, and the shortest safe path is of length 10>8=α⋅410>8=α· 4. For (b), the shortest path is of length 22, and the shortest safe path is of length 8>6=α⋅28>6=α· 2. For (c), the shortest path is of length 2η+2+x2η+2+x, where x is the length of the shortest path through the binary tree, and the shortest safe path is of length 6η+2+x>4η+4+2x=α⋅(2η+2+x)6η+2+x>4η+4+2x=α·(2η+2+x), using x≤2log(η)x≤ 2 (η) and our assumption 2log(η)+4<η2 (η)+4<η. Consequently, for any solution F, every feasible safe s-t path in G′⟨F⟩G F must contain an edge of F. Define the following convention for a subset F of unsafe edges and a set W⊆VW V: the unsafe edge incident with v∗v^* is in F if and only if v∈Wv∈ W. Since in each of the three constructions (a), (b), and (c), each unsafe edge has cost one, the convention implies that F is of cost at most k=rk=r if and only if W is of size at most r. Now, for every terminal pair v∗,w∗∈\v^*,w^*\ , let v,w∈E\v,w\∈ E be the corresponding edge in the input graph. The following equivalences hold. There is a safe v∗v^*-w∗w^* path of detour factor at most α in G′⟨F⟩G F if and only if at least one of the two unsafe edges incident with v∗v^* or w∗w^* is in F. By our convention, we have that at least one of the two unsafe edges incident with v∗v^* or w∗w^* is in F if and only if at least one of v,wv,w is in W. Finally, at least one of v,wv,w is in W if and only if the edge v,w∈E\v,w\∈ E is covered by W. Thus, all terminal pairs admit a feasible safe path in G′⟨F⟩G F if and only if W is a vertex cover of G. Together with the cost correspondence, this proves that I is a yes-instance if and only if I′I is a yes-instance. Finally, note that in construction (b), G′G contains |V|+2|V|+2 vertices and 2|V|+12|V|+1 edges. Hence, the ETH-based lower bound follows. Remark 4.3. The graph from 1(b) also has neighborhood-diversity two: Cu,CsC_u,C_s form one type, and V′∖Cu,CsV \C_u,C_s\ forms the other type. In fact, adding sufficiently long safe edges between any two non-adjacent vertices turns the graph into clique while preserving correctness, which results in neighborhood diversity one (but unbounded vertex cover number). Remark 4.4. None of the reductions has unit lengths. Yet, (a) and (c) can be turned via subdivisions into unit length; this is false for (b) as it would increase the vertex cover number. In the remainder, we show that decreasing any of the bounds =2 vcn=2, =1 fvs=1, =2 tw=2, or Δ=3 =3 by one leads to graph classes on which SBNBD is polynomial-time solvable. Proposition 4.5. For every instance of SBNBD where the input graph is a tree, we can compute a minimum-cost solution in polynomial time. Thus, SBNBD is polynomial-time solvable on trees. The proof of Proposition 4.5 uses the following two reduction rules. Reduction Rule 1 (Irrelevant pair). If a terminal pair is connected by a safe path of detour factor at most α, delete the terminal pair. Reduction Rule 2 (Mandatory edge). Let terminal pair sr,tr\s_r,t_r\ be not connected by a safe path of detour factor at most α. If an unsafe edge e lies on all srs_r-trt_r paths of detour factor at most α, then make e safe. If c(e)c(e) exceeds the budget, then return a trivial no-instance, otherwise decrease the budget by c(e)c(e). The correctness of 1 is immediate. The correctness of 2 follows since every feasible solution must upgrade e: otherwise no safe srs_r-trt_r path of detour factor at most α can exist. Thus, if c(e)>kc(e)>k, then the instance is a no-instance; otherwise, upgrading e can be fixed in advance and its cost subtracted from the budget. Proof 4.6 (Proof of Proposition 4.5). Let I be an instance of SBNBD with G being a tree, budget k, and let κ be the sum of costs of all unsafe edges. Let I′I be the instance obtained from I by setting the budget to κ. Apply 1 and 2 exhaustively to I′I . Since each terminal pair has a unique path, each unsafe edge on this path is mandatory and is made safe by 2. Hence, every edge made safe by 2 is contained in every feasible solution. Consequently, once all unsafe edges on the unique path of a terminal pair have been made safe, this terminal pair is deleted by 1. It follows that no terminal pair is left. Let F∗F^* denote the set of all unsafe edges made safe by 2 during the exhaustive application, and let κ′κ denote the remaining budget in the final instance. Note that c(F∗)=κ−κ′c(F^*)=κ-κ . Since every edge in F∗F^* is mandatory and upgrading F∗F^* satisfies all terminal pairs, c(F∗)c(F^*) is the minimum cost of any solution. Return yes if c(F∗)≤kc(F^*)≤ k, and no otherwise. Using Proposition 4.5, we also handle graphs of maximum degree at most two: path components are immediate, and for each cycle component we either upgrade all unsafe edges or delete one unsafe edge that remains unsafe, reducing the component to a path. observation SBNBD is polynomial-time solvable on graphs of degree at most two. Proof 4.7 (Proof of 4.2). Let I be an instance of SBNBD with detour factor α where G has maximum degree at most two. Then, graph G decomposes into paths and cycles. If a terminal pair is not contained in the same connected component, then return no. Otherwise, solve each connected component independently. If a connected component is a path, compute a minimum-cost solution using Proposition 4.5. Now consider a connected component C that is a cycle. First, consider the solution that upgrades all unsafe edges of C. This is feasible for all terminal pairs contained in C. We compare this solution with possible solutions where at least one unsafe edge is not upgraded. Thus, for each unsafe edge e of C, consider the case where e remains unsafe and hence no feasible safe path can use e. Then, every terminal pair s,t\s,t\ contained in C must be connected along the unique s-t path in C−eC-\e\. This is feasible only if distC−e(s,t)≤α⋅distG(s,t) _C-\e\(s,t)≤α· _G(s,t) for every terminal pair s,t\s,t\ contained in C. If this condition holds, we delete e and compute a minimum-cost solution on the path C−eC-\e\ using Proposition 4.5. Among the solution upgrading all unsafe edges and all solutions obtained by deleting one unsafe edge, we keep one of minimum cost. This enumeration is exhaustive since every solution either upgrades all unsafe edges of C or leaves at least one unsafe edge e not upgraded. Finally, the optimal solution for I is composed of the optimal solutions for each of its connected components. If the total cost exceeds the budget, return no, otherwise return yes. 5 Number of Unsafe Edges observation SBNBD can be solved in 2⋅poly(|I|)2 m_u· (|I|) time and hence is in FPT when parameterized by the number m_u of unsafe edges. Section 5 corresponds to testing all possible solutions in polynomial-time for feasibility. We show next that, assuming the SETH to hold, we cannot do better than this. Theorem 5.1. SBNBD, even if all unsafe edges induce one component (=1 c_u=1) and the input graph has diameter at most four, admits no 2ε⋅poly(|I|)2 · m_u· (|I|)-time algorithm for any ε<1 <1 unless the SETH breaks and no problem kernel of size polynomial in m_u unless NP⊆coNP/poly NP coNP/ poly. Moreover, it is W[2]-hard when parameterized by the budget k. We reduce from the Problem 5. Hitting Set problem, where we are given a set X of elements, a set S of nonempty subsets of X, and an integer r∈ℕr , and ask whether there is a subset Y⊆XY X with |Y|≤r|Y|≤ r such that S∩Y≠∅S∩ Y≠ for every S∈S . Problem 6. Hitting Set is W[2]-hard when parameterized by the solution size r [14] and admits no problem kernel of size polynomial in |X||X| unless NP⊆coNP/poly NP coNP/ poly [13]. Moreover, unless the SETH breaks, Problem 7. Hitting Set admits no 2ε⋅|X|⋅poly(|I|)2 ·|X|· (|I|)-time algorithm for any ε<1 <1 [9]. Construction 2. Let I=(X,,r)I=(X,S,r) be an instance of Problem 8. Hitting Set. Construct the graph G with vertex set V≔vx∣x∈X∪wS∣S∈∪v∗V \v_x x∈ X\∪\w_S S \∪\v^*\, safe-edge set Es≔vx,wS∣x∈X,S∈:x∈SE_s \\v_x,w_S\ x∈ X,S :x∈ S\, and unsafe-edge set Eu≔vx,v∗∣x∈XE_u \\v_x,v^*\ x∈ X\. The length of each edge is one and the cost of each unsafe edge is one. Let ≔v∗,wS∣S∈P \\v^*,w_S\ S \ be the set of terminal pairs. Let α≔1α 1 and k≔rk r. ⋄ Since every unsafe edge is incident with v∗v^*, the subgraph induced by EuE_u is connected (=1 c_u=1). For every S∈S , since S is nonempty, wSw_S and v∗v^* have a common neighbor vxv_x with x∈Sx∈ S. Thus, every two vertices are connected by a path of length at most four, and so G has diameter at most four. Proof 5.2 (Proof of Theorem 5.1). Let I′=(G=(V,E,c,θ),,k,α)I =(G=(V,E,c,θ),P,k,α) be the instance of SBNBD obtained in polynomial time from an instance I=(X,,r)I=(X,S,r) of Problem 9. Hitting Set via 2. For every S∈S , we have distG(wS,v∗)=2 _G(w_S,v^*)=2. Moreover, wSw_S is adjacent to vxv_x if and only if x∈Sx∈ S. Since α=1α=1, for every F⊆EuF E_u, any safe wSw_S-v∗v^* path of detour factor 11 in G⟨F⟩G F must have length exactly 22. Hence, it contains exactly one inner vertex vxv_x with x∈Sx∈ S, and the edge vx,v∗\v_x,v^*\ must be made safe by F. We make the following convention for a set Y⊆XY X and a set F⊆EuF E_u: x∈Yx∈ Y if and only if v∗,vx∈F\v^*,v_x\∈ F. Since every unsafe edge has cost one, the convention implies that |Y|≤r|Y|≤ r if and only if c(F)≤kc(F)≤ k. The following equivalences hold. Set S∈S is hit by Y if and only if there exists x∈S∩Yx∈ S∩ Y. By our convention, for every x∈Sx∈ S, x∈Yx∈ Y if and only if v∗,vx∈F\v^*,v_x\∈ F. Moreover, v∗,vx∈F\v^*,v_x\∈ F for some x∈Sx∈ S if and only if there is a safe wSw_S-v∗v^* path of detour factor 1 in G⟨F⟩G F . It follows that every set S∈S is hit by Y if and only if every terminal pair admits a safe path of detour factor 1 in G⟨F⟩G F . Together with the cost correspondence, this proves that I is a yes-instance if and only if I′I is a yes-instance. Finally, note that =|X| m_u=|X|. Hence, both the SETH-based lower bound and the kernelization lower bound follow. W[2]-hardness transfers since k=rk=r. 6 Number of Terminal Pairs Theorem 6.1. SBNBD is weakly NP-hard even if the input graph is planar, of maximum degree at most four, and of treewidth two, all unsafe edges are pairwise disjoint (=1 mcc_u=1), and there is only one terminal pair. We reduce from the weakly NP-hard Problem 10. Partition problem, where, given a multiset X=x1,…,xNX=\x_1,…,x_N\ of at least two positive integers with sum ∑xi∈Xxi=2T _x_i∈ Xx_i=2T, the question is whether there is a partition (X1,X2)(X_1,X_2) of X such that ∑xi∈X1xi=∑xi∈X2xi=T _x_i∈ X_1x_i= _x_i∈ X_2x_i=T. Construction 3. Let I=(X=x1,…,xN)I=(X=\x_1,…,x_N\) be an instance of Problem 11. Partition with sum 2T2T. Construct the vertex set V=vi∣i∈[0,N]∪ai,bi∣i∈[N]V=\v_i i∈[0,N]\∪\a_i,b_i i∈[N]\ and the edge set as follows: For each i∈[N]i∈[N], add the safe edges vi−1,ai\v_i-1,a_i\ of length T and vi−1,bi\v_i-1,b_i\ of length 2T2T, the safe edge bi,vi\b_i,v_i\ of length 2Nxi2Nx_i, and the unsafe edge ai,vi\a_i,v_i\ of length T and cost xix_i. The set P of terminal pairs consists only of one terminal pair v0,vN\v_0,v_N\. Let k≔Tk T and α≔2α 2. ⋄ The graph is outerplanar: an outerplanar embedding is obtained by placing v0v_0 at (0,0)(0,0) and, for each i∈[N]i∈[N], placing viv_i at (2i,0)(2i,0), aia_i at (2i−1,1)(2i-1,1), and bib_i at (2i−1,−1)(2i-1,-1). Since the graph is outerplanar and contains a cycle, it has treewidth two. It has maximum degree four: as N≥2N≥ 2, each vertex viv_i with i∈[N−1]i∈[N-1] has degree four, whereas each vertex aia_i and bib_i with i∈[N]i∈[N], as well as v0v_0 and vNv_N, has degree two. Finally, the set ai,vi∣i∈[N]\\a_i,v_i\ i∈[N]\ of unsafe edges consists of pairwise vertex-disjoint edges, and hence =1 mcc_u=1. Proof 6.2 (Proof of Theorem 6.1). Let I′=(G=(V,E,c,θ),,k,α)I =(G=(V,E,c,θ),P,k,α) be the instance of SBNBD obtained in polynomial time from an instance I=(X=x1,…,xN)I=(X=\x_1,…,x_N\) of Problem 12. Partition with sum 2T2T via 3. The shortest v0v_0-vNv_N path is of length 2NT2NT by using the unsafe branch when traversing from vi−1v_i-1 to viv_i via aia_i for each i∈[N]i∈[N]. Hence, since α=2α=2, every feasible path in a solution must be of length at most 4NT4NT. We show that I is a yes-instance if and only if I′I is a yes-instance. For the forward direction, let (X1,X2)(X_1,X_2) be a solution to I. We claim that F≔ai,vi∣xi∈X1F \\a_i,v_i\ x_i∈ X_1\ is a solution to I′I . We have that c(F)=∑xi∈X1c(ai,vi)=∑xi∈X1xi=T≤kc(F)= _x_i∈ X_1c(\a_i,v_i\)= _x_i∈ X_1x_i=T≤ k. Moreover, consider the shortest safe v0v_0-vNv_N path in G⟨F⟩G F . For each xi∈X1x_i∈ X_1, it uses the branch traversing from vi−1v_i-1 to viv_i via aia_i, since the unsafe edge ai,vi\a_i,v_i\ is upgraded by F; this branch has length 2T2T. For each xi∈X2x_i∈ X_2, it uses the branch traversing from vi−1v_i-1 to viv_i via bib_i, which has length 2T+2Nxi2T+2Nx_i. Altogether, the path has length 2NT+2N∑xi∈X2xi=4NT2NT+2N _x_i∈ X_2x_i=4NT. Thus, F is a solution to I′I . For the backward direction, let F be a solution to I′I . We claim that (X1,X2)(X_1,X_2), where X1≔xi∣ai,vi∈FX_1 \x_i \a_i,v_i\∈ F\ and X2≔X∖X1X_2 X X_1, is a solution to I. Since F is a solution, the shortest safe v0v_0-vNv_N path in G⟨F⟩G F is of length 2NT+2N∑xi∈X2xi≤4NT2NT+2N _x_i∈ X_2x_i≤ 4NT. It follows that ∑xi∈X2xi≤T _x_i∈ X_2x_i≤ T. Moreover, we know that ∑xi∈X1xi=∑ai,vi∈Fc(ai,vi)=c(F)≤k=T _x_i∈ X_1x_i= _\a_i,v_i\∈ Fc(\a_i,v_i\)=c(F)≤ k=T. Finally, since ∑xi∈X2xi+∑xi∈X1xi=2T _x_i∈ X_2x_i+ _x_i∈ X_1x_i=2T, (X1,X2)(X_1,X_2) is a solution to I. Remark 6.3. Note that fvs, and hence fes, is unbounded in the constructed graph. Yet, the graph has cutwidth two, witnessed by an ordering such as (…,vi−1,ai,bi,vi,…)(…,v_i-1,a_i,b_i,v_i,…), with exactly two edges between any two consecutive vertices. Note that in the previous reduction there is only one terminal pair. For unary encodings, the reduction no longer applies; however, we obtain W[1]-hardness in this case. Theorem 6.4. SBNBD is W[1]-hard when parameterized by the number p of terminals combined with the budget k, even if =1 c_u=1, all edges are unsafe, and all shortest terminal paths are of length three. We reduced from the Problem 13. Multicolored Clique problem, which asks, given a graph G=(V,E)G=(V,E) where V=V1⊎⋯⊎VrV=V_1 ·s V_r is partitioned into r color classes and at least one vertex from ViV_i is adjacent to a vertex from VjV_j for every distinct i,j∈[r]i,j∈[r], whether there is a vertex set W such that W forms a clique in G and |W∩Vi|=1|W∩ V_i|=1 for every i∈[r]i∈[r]. Problem 14. Multicolored Clique is W[1]-hard when parameterized by r [19]. Construction 4. Let I=(G=(V=V1⊎⋯⊎Vr,E))I=(G=(V=V_1 ·s V_r,E)) be an instance of Problem 15. Multicolored Clique. Let G′G be initially a copy of G. Make each edge in G′G unsafe with cost 1 and length 1. For each color class add a verifier vertex wiw_i and make it adjacent by unsafe edges of cost r3r^3 and length 1 with all vertices from ViV_i. Let ≔wi,wj∣1≤i<j≤rP \\w_i,w_j\ 1≤ i<j≤ r\ be the set of terminal pairs. Let α≔1α 1 and k≔r⋅r3+(r2)k r· r^3+ r2. ⋄ Proof 6.5 (Proof of Theorem 6.4). Let I′=(G′=(V′,E′,c,θ),,k,α)I =(G =(V ,E ,c,θ),P,k,α) be the instance of SBNBD obtained in polynomial time from an instance I=(G=(V=V1⊎⋯⊎Vr,E))I=(G=(V=V_1 ·s V_r,E)) of Problem 16. Multicolored Clique via 4. We show that I is a yes-instance if and only if I′I is a yes-instance. For the forward direction, let W=v1∗,…,vr∗W=\v_1^*,…,v_r^*\ be solution to I with vi∗∈Viv_i^*∈ V_i for each i∈[r]i∈[r]. We claim that F≔wi,vi∗∣i∈[r]∪vi∗,vj∗∣i,j∈[r],i<jF \\w_i,v_i^*\ i∈[r]\∪\\v_i^*,v_j^*\ i,j∈[r],\,i<j\ is a solution to I′I . We have that c(F)=∑i∈[r]c(wi,vi∗)+∑i,j∈[r],i<jc(vi∗,vj∗)=r⋅r3+(r2)=kc(F)= _i∈[r]c(\w_i,v_i^*\)+ _i,j∈[r],\,i<jc(\v_i^*,v_j^*\)=r· r^3+ r2=k. Moreover, for each i,j∈[r]i,j∈[r], i<ji<j, there is a safe wiw_i-wjw_j path in G′⟨F⟩G F of length three traversing from wiw_i to vi∗v_i^* to vj∗v_j^* to wjw_j of length distG′(wi,wj) _G (w_i,w_j). Hence, F is a solution to I′I . For the backward direction, let F be a solution to I′I . By construction, for each color class i∈[r]i∈[r], ViV_i separates wiw_i in G′G from the rest of the graph. Since wiw_i appears in at least one terminal pair, at least one edge incident with wiw_i must be upgraded by F at cost r3r^3. As there are r color classes, at least r⋅r3r· r^3 budget is spent on these upgrades. Thus, the remaining budget is at most (r2)<r3 r2<r^3, and hence no further edge incident with any wiw_i can be upgraded. Hence, for every i∈[r]i∈[r], there is exactly one upgraded edge incident with wiw_i in F. Let this edge be wi,vi∗\w_i,v_i^*\ with vi∗∈Viv_i^*∈ V_i. We claim that W≔v1∗,…,vr∗W \v_1^*,…,v_r^*\ is a solution to I. Consider distinct i,j∈[r]i,j∈[r]. By the assumption on the input instance, at least one vertex from ViV_i neighbors a vertex from VjV_j, and hence distG′(wi,wj)=3 _G (w_i,w_j)=3. Since α=1α=1, every feasible safe wiw_i-wjw_j path in G′⟨F⟩G F must have exactly three edges. Since wi,vi∗\w_i,v_i^*\ is the only upgraded edge incident with wiw_i and wj,vj∗\w_j,v_j^*\ is the only upgraded edge incident with wjw_j, the middle edge of such a path must be vi∗,vj∗\v_i^*,v_j^*\. Thus, vi∗,vj∗∈E\v_i^*,v_j^*\∈ E. Since this holds for every pair of distinct color classes, it follows that W induces a clique. Hence, W is a solution to I. Since ||=(r2)|P|= r2 and k=r⋅r3+(r2)k=r· r^3+ r2 depend only on r, W[1]-hardness for the combined parameter p+kp+k follows. 7 Feedback Edge Number Theorem 7.1. Any instance of SBNBD can be mapped in polynomial time to an equivalent instance of SBNBD with O(+p)O( fes+p) vertices and edges. Note that together with Section 5, it follows that SBNBD is FPT when parameterized by +p fes+p. Theorem 7.1 consists of carefully deleting leaves and compressing long paths in the tree G−XG-X, where X denotes a minimum feedback edge set. Such an approach has already proved useful (see, e.g., [18, 29]). We call a vertex in G=(V,E)G=(V,E) with terminal pairs P and a feedback edge set X⊆EX E important if it is contained in a terminal pair, incident with an edge of X, or is of degree at least three in G−XG-X, and unimportant otherwise. Reduction Rule 3 (Leaf). If a leaf in G−XG-X is unimportant, delete it. Proof 7.2 (Correctness proof of 3). Let v be an unimportant leaf of G−XG-X. Then, v is neither contained in a terminal pair nor incident with an edge of X. Thus, v is a non-terminal leaf of G and hence not contained in any path between terminals. Deleting v preserves all terminal-pair distances, all feasible safe paths, and the set of feasible solutions. For terminal pairs P and a feedback edge set X⊆EX E, we call a path P in G−XG-X a corridor if it contains at least three vertices, each of its endpoints is important, and all its inner vertices are unimportant and of degree two in G−XG-X. We exploit that any s-t path connecting a terminal pair s,t\s,t\ contains either all edges of such a corridor or none. Hence, we can replace such a corridor by a path with at most two edges thereby preserving all relevant information (lengths and costs) for the instance. However, we need to carefully distinguish the type of the corridor in terms of contained safe and unsafe edges and whether its endpoints are connected by a feedback edge. Note that since P is a subgraph of G−XG-X, if the endpoints of P are adjacent in G, then the edge belongs to X. Let v,wv,w be the endpoints of corridor P. We call P unsafe if it contains at least one unsafe edge, and safe otherwise. We prove next that we can replace corridors with many edges by paths with at most two edges. Lemma 7.3. Let I be an instance of SBNBD with graph G=(V,E)G=(V,E) and with feedback edge set X⊆EX E. Let P be a corridor with endpoints v,wv,w. Let I′I be the instance with graph G′=(V′,E′)G =(V ,E ) obtained from I only by replacing P with a path P′P with endpoints v,wv,w such that len(P′)=len(P) (P )= (P), and P′P consists of either two edges and one unimportant inner vertex if v,w∈E\v,w\∈ E, or of one edge otherwise. Moreover, P is safe if and only if P′P is safe, and if both are unsafe, ∑e∈(P)∩Euc(e)=∑e∈(P′)∩Eu′c(e) _e∈ E(P)∩ E_uc(e)= _e∈ E(P )∩ E_u c(e), where Eu′⊆E′E_u E is the set of unsafe edges in G′G . Then I is a yes-instance if and only if I′I is a yes-instance. Proof 7.4. Since every inner vertex of P and of P′P is unimportant, none of them is in a terminal pair. Since the inner vertices of P and P′P have degree two in G and G′G , respectively, every path connecting a terminal pair contains either all or none of the edges of P and P′P . Since len(P)=len(P′) (P)= (P ), it follows that distG(s,t)=distG′(s,t) _G(s,t)= _G (s,t) for every terminal pair s,t∈\s,t\ . Finally, note that G′G is a simple graph and hence a valid input to SBNBD since P′P has two edges in the case of v,w∈E\v,w\∈ E. For the forward direction, let F⊆EF E be a cost-minimal solution to I. Let FP≔F∩E(P)F_P F∩ E(P). We know that either FP=∅F_P= or FP=E(P)∩EuF_P=E(P)∩ E_u. Let FP′≔E(P′)∩Eu′F_P E(P )∩ E_u . Let F′F be F if FP=∅F_P= , and (F∖FP)∪FP′(F F_P)∪ F_P otherwise. By the cost equality for P and P′P , we have c(F′)=c(F)≤kc(F )=c(F)≤ k. We claim that F′F is a solution to I′I . Let s,t∈\s,t\ be a terminal pair. Let Q be a safe s-t path in G⟨F⟩G F of detour factor at most α. If Q contains no edge from P, then Q is also a safe s-t path in G′⟨F′⟩G F , since distG(s,t)=distG′(s,t) _G(s,t)= _G (s,t). If Q contains an edge from P, then P is a subpath of Q. Let Q′Q be the path in G′G obtained from Q by replacing P by P′P . Note that len(Q)=len(Q′) (Q)= (Q ). Moreover, Q′Q is safe since if all unsafe edges of P are upgraded by F, so are all unsafe edges of P′P upgraded by F′F . With distG(s,t)=distG′(s,t) _G(s,t)= _G (s,t), it follows that Q′Q is safe and of detour factor at most α. Since this holds for every terminal pair, F′F is a solution to I′I . For the backward direction, let F′⊆E′F E be a cost-minimal solution to I′I . Let FP′≔F′∩E(P′)F_P F ∩ E(P ). We know that either FP′=∅F_P = or FP′=E(P′)∩Eu′F_P =E(P )∩ E_u . Let FP≔E(P)∩EuF_P E(P)∩ E_u. Let F be F′F if FP′=∅F_P = , and (F′∖FP′)∪FP(F F_P )∪ F_P otherwise. By the cost equality for P and P′P , we have c(F)=c(F′)≤kc(F)=c(F )≤ k. We claim that F is a solution to I. Let s,t∈\s,t\ be a terminal pair. Let Q′Q be a safe s-t path in G′⟨F′⟩G F of detour factor at most α. If Q′Q contains no edge from P′P , then Q′Q is also a safe s-t path in G⟨F⟩G F , since distG(s,t)=distG′(s,t) _G(s,t)= _G (s,t). If Q′Q contains an edge from P′P , then P′P is a subpath of Q′Q . Let Q be the path in G obtained from Q′Q by replacing P′P by P. Note that len(Q′)=len(Q) (Q )= (Q). Moreover, Q is safe since if all unsafe edges of P′P are upgraded by F′F , so are all unsafe edges of P upgraded by F. With distG(s,t)=distG′(s,t) _G(s,t)= _G (s,t), it follows that Q is safe and of detour factor at most α. Since this holds for every terminal pair, F is a solution to I. If the endpoints of a corridor are connected by a feedback edge, we compare the corridor with this alternative connection. To this end, we introduce the following notation. We call a path R with endpoints v,wv,w and no important inner vertex irrelevant if there is another path R′R with endpoints v,wv,w in G−(V(R)∖v,w)G-(V(R) \v,w\) and no important inner vertex such that if R is safe, then R′R is safe and len(R′)≤len(R) (R )≤ (R); if R is unsafe, then len(R′)≤len(R) (R )≤ (R) and ∑e∈(R′)∩Euc(e)≤∑e∈(R)∩Euc(e) _e∈ E(R )∩ E_uc(e)≤ _e∈ E(R)∩ E_uc(e). Lemma 7.5. Let I be an instance of SBNBD with an irrelevant path R. Let I′I be the instance obtained from I by deleting all edges and inner vertices of R. Then, I is a yes-instance if and only if I′I is a yes-instance. Proof 7.6. Let v,wv,w denote the endpoints of R and let R′R be a witness such that R is irrelevant. Since no inner vertex of R is a terminal and every inner vertex has degree two, every terminal-to-terminal path contains either all or none of the edges of R. Let G′G denote the graph in I′I . Since G′G is a subgraph of G, we have distG(s,t)≤distG′(s,t) _G(s,t)≤ _G (s,t). Conversely, every path using R can replace it by R′R without increasing its length, as len(R′)≤len(R) (R )≤ (R). Thus, distG(s,t)=distG′(s,t) _G(s,t)= _G (s,t) for every terminal pair s,t∈\s,t\ . Next we show that I is a yes-instance if and only if I′I is a yes-instance. Regarding the backward direction: Since G′G is a subgraph of G and distances are preserved, any solution for I′I is also feasible for I. For the forward direction, let F be a solution to I. If R is safe, then every feasible safe path using R can replace R by the safe path R′R , which is no longer since len(R′)≤len(R) (R )≤ (R). All paths not using R remain unchanged. Thus, F is also a solution to I′I . Now assume that R is unsafe. If F does not contain all unsafe edges of R, then F′≔F∖(F∩(R))F F (F∩ E(R)) is also a solution to I′I since no safe path in G⟨F⟩G F uses an edge from R. Otherwise, let F′F be obtained from F by replacing all unsafe edges of R by all unsafe edges of R′R . Since ∑e∈(R′)∩Euc(e)≤∑e∈(R)∩Euc(e) _e∈ E(R )∩ E_uc(e)≤ _e∈ E(R)∩ E_uc(e), the cost of F′F is at most the cost of F. Since F is a solution to I, for every terminal pair s,t∈\s,t\ , there is a safe path Q in G⟨F⟩G F of detour factor at most α. If Q does not contain R, then it is also a safe path in G′⟨F′⟩G F . If Q contains R, then the s-t path Q′Q obtained from Q by replacing R by R′R is a safe path in G′⟨F′⟩G F of length at most len(Q) (Q), since len(R′)≤len(R) (R )≤ (R). Hence, F′F is also a solution to I′I . We proceed towards our reduction rules. We call a safe corridor P contractible if (i) v,w∉E\v,w\ ∈ E, (i) e=v,w∈X∩Ese=\v,w\∈ X∩ E_s, or (i) e=v,w∈X∩Eue=\v,w\∈ X∩ E_u and len(P)≤θ(e) (P)≤θ(e), and compressible if it contains at least four vertices, e=v,w∈X∩Eue=\v,w\∈ X∩ E_u, and len(P)>θ(e) (P)>θ(e). A safe corridor can be neither contractible nor compressible, that is, when it has three vertices, e=v,w∈X∩Eue=\v,w\∈ X∩ E_u, and len(P)>θ(e) (P)>θ(e). Reduction Rule 4 (Safe Corridor Contraction). Let P be a contractible safe corridor with endpoints v,wv,w. 1. If v,w∉E\v,w\ ∈ E, then remove all edges and inner vertices from P and add the edge e=v,we=\v,w\ to EsE_s and set θ(e)=len(P)θ(e)= (P). 2. If e=v,w∈X∩Ese=\v,w\∈ X∩ E_s, then remove e and all edges and inner vertices from P, add a new safe edge e′e and set θ(e′)=minθ(e),len(P)θ(e )= \θ(e), (P)\. 3. If e=v,w∈X∩Eue=\v,w\∈ X∩ E_u and len(P)≤θ(e) (P)≤θ(e), then remove e and all edges and inner vertices from P and add the edge e′=v,we =\v,w\ to EsE_s and set θ(e′)=len(P)θ(e )= (P). 4 is correct since an unsafe alternative not shorter than the safe corridor is irrelevant, and among two safe options, the longer is irrelevant. Proof 7.7 (Correctness proof of 4). The correctness of the first case follows directly from Lemma 7.3. For the second case, if θ(e)≤len(P)θ(e)≤ (P), then P is irrelevant and correctness follows from Lemma 7.5. Otherwise, the single-edge path e is irrelevant. Hence, the correctness follows from Lemma 7.5 together with Lemma 7.3. For the third case, since len(P)≤θ(e) (P)≤θ(e), the single-edge path e is irrelevant. Hence, the correctness follows from Lemma 7.5 together with Lemma 7.3. The next rule treats a shorter unsafe alternative to the safe corridor. In this case, we have to keep both, but can compress the safe corridor into a path with two edges that preserves the length of the corridor. The correctness follows directly from Lemma 7.3. Reduction Rule 5 (Safe Corridor Compression). Let P be a compressible safe corridor with endpoints v,wv,w and let e=v,w∈X∩Eue=\v,w\∈ X∩ E_u. Then remove all edges and inner vertices from P, add a new vertex xv,wx_v,w and the edges e′=v,xv,w,e′=xv,w,we =\v,x_v,w\,e =\x_v,w,w\ to EsE_s, and set θ(e′)=len(P)−1θ(e )= (P)-1 and θ(e′)=1θ(e )=1. Let P be an unsafe corridor with total cost M≔∑e∈(P)∩Euc(e)M _e∈ E(P)∩ E_uc(e). We call P contractible if (i) v,w∉E\v,w\ ∈ E, (i) e=v,w∈X∩Ese=\v,w\∈ X∩ E_s and len(P)≥θ(e) (P)≥θ(e), or (i) e=v,w∈X∩Eue=\v,w\∈ X∩ E_u and (len(P)≤θ(e)∧M≤c(e))∨(len(P)≥θ(e)∧M≥c(e)). ( (P)≤θ(e) M≤ c(e)) ( (P)≥θ(e) M≥ c(e)). (1) We call P compressible if it contains at least four vertices and either (i) e=v,w∈X∩Ese=\v,w\∈ X∩ E_s and len(P)<θ(e) (P)<θ(e), or (i) e=v,w∈X∩Eue=\v,w\∈ X∩ E_u and (1) does not hold. An unsafe corridor can be neither contractible nor compressible, that is, when it has three vertices and the conditions (i) or (i) for compressible corridors hold. Reduction Rule 6 (Unsafe Corridor Contraction). Let P be a contractible unsafe corridor with endpoints v,wv,w. Let M≔∑e∈(P)∩Euc(e)M _e∈ E(P)∩ E_uc(e) be the total cost of P. 1. If v,w∉E\v,w\ ∈ E, then remove all edges and inner vertices from P and add the edge e=v,we=\v,w\ to EuE_u and set θ(e)=len(P)θ(e)= (P) and c(e)=Mc(e)=M. 2. If e=v,w∈X∩Ese=\v,w\∈ X∩ E_s and len(P)≥θ(e) (P)≥θ(e), then remove e and all edges and inner vertices from P, add the safe edge e′=v,we =\v,w\ and set θ(e′)=θ(e)θ(e )=θ(e). 3. If e=v,w∈X∩Eue=\v,w\∈ X∩ E_u and (1) holds, then remove e and all edges and inner vertices from P, add a new unsafe edge e′e and let c(e′)≔minM,c(e)c(e ) \M,c(e)\ and θ(e′)≔minθ(e),len(P)θ(e ) \θ(e), (P)\. 6 is correct since when one unsafe connection weakly dominates the other (neither longer nor more costly), the dominated one is irrelevant for both shortest paths and upgrade costs. Proof 7.8 (Correctness proof of 6). The correctness of the first case follows directly from Lemma 7.3. For the second case, since len(P)≥θ(e) (P)≥θ(e), P is irrelevant and correctness follows from Lemma 7.5. Now consider the third case. If len(P)≤θ(e) (P)≤θ(e) and M≤c(e)M≤ c(e), then the single-edge path e is irrelevant. Hence, the correctness follows from Lemma 7.5 together with Lemma 7.3. If len(P)≥θ(e) (P)≥θ(e) and M≥c(e)M≥ c(e), then P is irrelevant and correctness follows from Lemma 7.5. These two cases are exactly the two alternatives in (1). The next rule treats two incomparable unsafe paths with the same endpoints. In this case, we have to keep both, but can compress the unsafe corridor into a path with two edges that preserves the length of the corridor and the cost to upgrade all of its unsafe edges. The correctness follows directly from Lemma 7.3. Reduction Rule 7 (Unsafe Corridor Compression). Let P be a compressible unsafe corridor with endpoints v,wv,w. Let M≔∑e∈(P)∩Euc(e)M _e∈ E(P)∩ E_uc(e) be the total cost of P. Then remove all edges and inner vertices from P, add a new vertex xv,wx_v,w and the edges e′=v,xv,we =\v,x_v,w\ to EuE_u and e′=xv,w,we =\x_v,w,w\ to EsE_s. Set θ(e′)=len(P)−1θ(e )= (P)-1, c(e′)=Mc(e )=M, and θ(e′)=1θ(e )=1. For easier reference, we summarize the four preceding reduction rules in the following reduction rule. Its correctness follows from the correctness of the four individual rules. Reduction Rule 8 (Corridor). Let P be a corridor. If P is safe, then apply 4 if it is contractible and 5 if it is compressible. If P is unsafe, then apply 6 if it is contractible and 7 if it is compressible. Each corridor replacement preserves the relevant v-w connections. Safe and unsafe corridors represent length-len(P) (P) connections that are already safe and that can be made safe at upgrade cost M, respectively. If the endpoints are joined by a feedback edge e, then e contributes a length-θ(e)θ(e) connection that is either already safe or that can be made safe at upgrade cost c(e)c(e). The contraction rules delete dominated connections, while the compression rules keep two incomparable connections by representing the corridor as a two-edge path. Since every s-t path for terminal pair s,t\s,t\ uses either the whole corridor or none of it, these replacements preserve feasibility and optimum cost. Proof 7.9 (Proof of Theorem 7.1). Let X be a minimum feedback edge set of G with |X|=|X|= fes and let T denote the forest obtained from G−XG-X when 3 is applied exhaustively. We mark all important vertices and keep these marks fixed throughout the reduction. Now, apply 8 exhaustively. Whenever a rule deletes an edge of X, we remove it from the current feedback edge set. New edges replacing subpaths of T are treated as forest edges. Let T′T denote the forest obtained from T by the above replacements, X′⊆X X the remaining feedback edges (recall that applying corridor contractions can delete feedback edges as well), and let G′G denote the graph T′T together with the edges from X′X . Let (T′)=V1∪V2+∪V2−∪V≥3 V(T )=V_1∪ V_2^+∪ V_2^-∪ V_≥ 3, where we denote by V1V_1 the set of leaves, by V2+V_2^+ the set of important degree-2 vertices, by V2−V_2^- the set of unimportant degree-2 vertices, and by V≥3V_≥ 3 the set of vertices of degree at least three. We know that |V1|+|V2+|≤2+2p|V_1|+|V_2^+|≤ 2 fes+2p, and it is well known that |V≥3|≤|V1||V_≥ 3|≤|V_1|. Next we show that |V2−|≤|V_2^-|≤ fes. After the execution, every remaining unimportant degree-two vertex is the unique inner vertex of a corridor with three vertices whose endpoints are important and adjacent by a remaining feedback edge. Since T′T is a forest, for each feedback edge v,w∈X′\v,w\∈ X there is at most one v-w path in T′T . Hence, this defines an injective mapping from unimportant degree-two vertices to feedback edges in X′X , and thus |V2−|≤|X′|≤|V_2^-|≤|X |≤ fes. Hence, we get that |(G′)|=|(T′)|=|V1|+|V2+|+|V2−|+|V≥3|≤|V1|+|V2+|+|V2−|+|V1|≤5+4p| V(G )|=| V(T )|=|V_1|+|V_2^+|+|V_2^-|+|V_≥ 3|≤|V_1|+|V_2^+|+|V_2^-|+|V_1|≤ 5 fes+4p. Finally, |(G′)|=|(T′)|+|X′|≤6+4p| E(G )|=| E(T )|+|X |≤ 6 fes+4p. 8 ILP, Preprocessing, and Cut Generation For every r∈[p]r∈[p], we denote by ArαA_r^α the set of all α-admissible arcs, where, for an edge e=v,we=\v,w\ and terminal pair sr,tr\s_r,t_r\, arc (v,w)(v,w) is α-admissible for terminal pair sr,tr\s_r,t_r\ if dist(sr,v)+θ(e)+dist(w,tr)≤α⋅dist(sr,tr) (s_r,v)+θ(e)+ (w,t_r)≤α· (s_r,t_r). For a vertex v∈Vv∈ V, we denote by outrα(v)out_r^α(v) and inrα(v)in_r^α(v) the sets of outgoing and incoming arcs at v in ArαA_r^α, respectively. We say that an edge is α-admissible for terminal pair sr,tr\s_r,t_r\ if at least one of its two associated arcs is α-admissible for terminal pair sr,tr\s_r,t_r\. Let ErαE_r^α denote the set of all α-admissible edges for terminal pair sr,tr\s_r,t_r\. Finally, let Grα≔G[Erα]G_r^α G[E_r^α] denote the α-admissible graph for terminal pair sr,tr\s_r,t_r\. We use the following ILP as our baseline exact formulation. min ∑e∈Euc(e)⋅xe _e∈ E_uc(e)· x_e (2a) s.t. ∑a∈outrα(v)far−∑a∈inrα(v)far=1,if v=sr,−1,if v=tr,0,otherwise, _a _r^α(v)f_a^r- _a _r^α(v)f_a^r= cases1,&if \ v=s_r,\\ -1,&if \ v=t_r,\\ 0,&otherwise, cases ∀r∈[p],∀v∈V, ∀ r∈[p],\ ∀ v∈ V, (2b) ∑a∈Arα∩(v,w),(w,v)far≤xe, _a∈ A_r^α∩\(v,w),(w,v)\f_a^r≤ x_e, ∀r∈[p],∀v,w∈Eu, ∀ r∈[p],\ ∀\v,w\∈ E_u, (2c) ∑a∈Arαθ(a)⋅far≤α⋅distG(sr,tr), _a∈ A_r^αθ(a)· f_a^r≤α· _G(s_r,t_r), ∀r∈[p], ∀ r∈[p], (2d) 0≤far≤1, 0≤ f_a^r≤ 1, ∀r∈[p],∀a∈Arα. ∀ r∈[p],\ ∀ a∈ A_r^α. (2e) xe∈0,1, x_e∈\0,1\, ∀e∈Eu, ∀ e∈ E_u, (2f) Constraints (2b)–(2e) ensure that for each terminal pair sr,tr\s_r,t_r\, a safe srs_r-trt_r path exists, that can use upgraded unsafe edges (2c), but must have detour factor at most α (2d). 8.1 FES-based Preprocessing We apply the reduction rules that we described before together with the following two, where the second is a direct combination of 1 and 2: Reduction Rule 9 (Irrelevant edge). If an edge is not α-admissible for any terminal pair, delete it. Reduction Rule 10 (Unique path). If a terminal pair is not connected by a safe path of detour factor at most α but connected by a unique path of detour factor at most α containing at least one unsafe edge, then let C denote the sum of costs of all unsafe edges on this path. If C exceeds the budget, return a trivial no-instance, otherwise make all unsafe edges on the path safe, decrease the budget by C, and delete the terminal pair. We apply each reduction rule exhaustively before moving to the next one. Since one reduction rule can make another rule applicable, their ordering matters. Figure 3 shows how we arrange our reduction rules. 1(Reduction Rule 1 (Irrelevant pair).)3(Reduction Rule 3 (Leaf).)10(Reduction Rule 10 (Unique path).)3(Reduction Rule 3 (Leaf).)8(Reduction Rule 8 (Corridor).)2(Reduction Rule 2 (Mandatory edge).)9(Reduction Rule 9 (Irrelevant edge).)start1st pass 2nd pass Figure 3: Flow chart of our shrink heuristic. Empirically, this two-round execution provides a good trade-off between running time and preprocessing effectiveness compared to an exhaustive application until every reduction rule becomes inapplicable. Before each of 3 and 8, we recompute a minimum feedback edge set. Notably, after applying the shrink heuristic, the treewidth of the obtained graph is not larger than the treewidth of the input graph, since deletion and edge contraction and compression do not increase the treewidth. 8.2 TD-separator Cuts Let (,Bii∈I)(T,\B_i\_i∈ I) with tree =(I,Y)T=(I,Y) be a tree decomposition of G. Our cut generation is based on the following, simple insight about cuts consisting only of unsafe edges. observation Let sr,tr∈\s_r,t_r\ be a terminal pair and U⊆(Grα)U V(G_r^α) such that |sr,tr∩U|=1|\s_r,t_r\∩ U|=1. If ∅≠∂Grα(U)⊆Eu ≠ _G_r^α(U) E_u, then |F∩∂Grα(U)|≥1|F∩ _G_r^α(U)|≥ 1 for every solution F. Proof 8.1. Since ∂Grα(U) _G_r^α(U) forms an srs_r-trt_r cut in GrαG_r^α, it intersects all srs_r-trt_r paths of detour factor at most α in G. Thus, every feasible srs_r-trt_r path must traverse an edge from ∂Grα(U) _G_r^α(U). Since ∂Grα(U) _G_r^α(U) contains only unsafe edges, every solution must upgrade at least one edge from ∂Grα(U) _G_r^α(U). It is well known that every edge i,j∈Y\i,j\∈ Y of T corresponds to a separator Si,j≔Bi∩BjS_\i,j\ B_i∩ B_j in the following sense. Let Iii,jI_i^\i,j\ and Iji,jI_j^\i,j\ denote all nodes of the connected component of −i,jT-\\i,j\\ containing i and j, respectively. Let Bxi,j=⋃y∈Ixi,jByB_x^\i,j\= _y∈ I_x^\i,j\B_y denote the corresponding set of vertices in G for each x∈i,jx∈\i,j\. Then Bii,j∖Si,jB_i^\i,j\ S_\i,j\ is disconnected from Bji,j∖Si,jB_j^\i,j\ S_\i,j\ in G−Si,jG-S_\i,j\. Now assume that T is rooted at some node. For an edge i,j∈Y\i,j\∈ Y, let min(i,j) _T(\i,j\) denote the endpoint of larger depth. Every X⊆Si,jX S_\i,j\ defines a candidate side Vi,jX≔(Bmin(i,j)i,j∖Si,j)∪XV_\i,j\^X (B_ _T(\i,j\)^\i,j\ S_\i,j\ )∪ X. Altogether, we consider the set =Vi,jX∣i,j∈Y,X⊆Si,jV=\V_\i,j\^X \i,j\∈ Y,\,X S_\i,j\\ of all candidate sides. For each terminal pair sr,tr\s_r,t_r\ and candidate side Vi,jX∈V_\i,j\^X , let Vi,j,rX≔Vi,jX∩(Grα)V_\i,j\,r^X V_\i,j\^X∩ V(G_r^α) be the candidate side when restricted to the vertices of the α-admissible graph for sr,tr\s_r,t_r\. If |sr,tr∩Vi,j,rX|=1|\s_r,t_r\∩ V_\i,j\,r^X|=1 and ∅≠∂Grα(Vi,j,rX)⊆Eu ≠ _G_r^α(V_\i,j\,r^X) E_u, then, due to Section 8.2, every feasible solution upgrades at least one edge of this cut. Hence, for this terminal pair and candidate side, we add the valid inequality ∑e∈∂Grα(Vi,j,rX)xe≥1 Σ _e∈ _G_r^α(V_\i,j\,r^X)x_e≥ 1 to the ILP. 9 Experiments Our experiments ran on Intel® Xeon® Silver 4310 CPU at 2.10GHz (12 cores), 125 GB RAM, Ubuntu 24.04.4 LTS (x86_64), using Gurobi(py) 13.0 for the ILPs. 9.1 Instances We considered 30 village networks and 30 region networks. For each network, we combined three safety models, three terminal-pair fractions, two random samples, and three detour factors. In total, we constructed 1620 village instances and 1620 region instances. Networks. We select municipalities based on the ADFC Bicycle Climate Test [1], a nationwide online cyclist satisfaction survey in which participants rate the perceived bicycle-friendliness of their municipality. From the ranking for towns of at most 20000 inhabitants, we took the subranking when filtered for towns of at most 10000 inhabitants. From this, we selected the top ten, bottom ten, and ten randomly sampled from the remaining towns. From OSM, we extracted the road network using type “drive”, made it undirected, kept only the largest connected component, and assigned the length in accordance with the OSM data. Herein, when two vertices are connected by two arcs, we only represent them separately (via paths with two edges) if they differ significantly in length or type. We set the cost of an unsafe edge to its length, assuming the cost to scale with length, thereby neglecting the type of the street segment and any further details. This abstracts from realistic costs, for which we did not find reliable comparable data. Analogously, for each of the selected towns, we computed the network corresponding to the 3 km3\,km radius region around the associated town’s center, mimicking inter-village networks. Table 1 gives an overview of selected statistics relevant to us for the derived networks. Type Vertices Edges m /m fes/m ¯ tw Δ Planar Village 355.43 [34165561_61^655] 443.67 [412.5087176_76^871] 0.2 [0.200.250.11_0.11^0.25] 6.00 [5113_3^11] 4.17 [454_4^5] 27/30 Region 738.63 [604.501929140_140^1929] 934.97 [7552623176_176^2623] 0.2 [0.200.280.14_0.14^0.28] 7.97 [7144_4^14] 4.43 [454_4^5] 20/30 Table 1: Structural statistics for our village and region networks as to the means with median, minimum (lower), and maximum (upper) in parentheses. ¯ tw denotes the width of a TD computed via minimum fill-in. Remarkably, on average, 20% of the edges suffice as a feedback edge set, and the maximum observed treewidth upper bound is 11 for villages and 14 for regions. We also point out that only two thirds of our region networks are planar. Safety models. For classifying edges as unsafe, we developed three models A, B, and C that are nested in spirit. Model A is an accommodating local-access model where local roads are generally considered bicycle-suitable. Model B is a balanced speed-aware model where local roads require low-speed evidence. Finally, model C is a conservative low-stress model where only clearly low-stress roads are considered safe. See Table 2 for further details. Model A Model B Model C Safe in all models Living streets, traffic-calmed roads, and extracted road segments with explicit bicycle infrastructure Residential roads Safe Safe if speed is missing or at most 30 km/h30\,km/h Safe if speed is missing or at most 30 km/h30\,km/h Service / unclassified roads Safe only if speed is at most 20 km/h20\,km/h Tertiary roads Safe only if speed is at most 30 km/h30\,km/h Unsafe by default Paths / pedestrian streets, if present Safe unless bicycles are explicitly forbidden Safe only if bicycles are explicitly allowed Average unsafe fraction 0.220.22 [0.210.320.10_0.10^0.32] 0.290.29 [0.280.510.12_0.12^0.51] 0.370.37 [0.360.580.15_0.15^0.58] 0.220.22 [0.220.300.14_0.14^0.30] 0.300.30 [0.280.560.15_0.15^0.56] 0.360.36 [0.350.570.15_0.15^0.57] Table 2: Summary of the three edge safety models. The first row gives rules that make an edge safe in all models; subsequent rows list additional rules specific to road classes. Last two rows report average unsafe-edge fractions, with median, minimum, and maximum in parentheses, for villages (top row) and regions (bottom row). Terminal pairs and detour-factors. For each network, we randomly sampled x⋅nx· n many (distinct) terminal pairs for x∈0.25,0.5,0.75x∈\0.25,0.5,0.75\ for villages and for x∈0.15,0.3,0.45x∈\0.15,0.3,0.45\ for regions, where n denotes the number of vertices. For each network and such setup, we constructed two instances. Finally, for each of those, we chose detour factors α∈1.2,1.3,1.5α∈\1.2,1.3,1.5\, where α=1.2α=1.2 [20, p. 10] and α=1.3α=1.3 [6] are used in bicycle-network design as target bounds. 9.2 Algorithmic Setup We compare ILP (cf. (2)) against ILPtwc_ twc, which is ILP with TD-separator cuts, ILPpre pre, which is ILP where preprocessing is applied, and ILPpretwc_ twc pre, the combination of both. To compute a tree decomposition, we use NetworkX’s implementation treewidth_min_fill_in [25] of the minimum fill-in heuristic [3, 39]. On a high level, the heuristic greedily turns neighborhoods into cliques, thereby creating for the resulting graph a so-called perfect elimination ordering, which yields a tree decomposition. The number of candidate sides for each TD-separator can be as large as 2¯+12 tw+1. Each such candidate can be considered for every terminal pair, leading to many candidate cuts. Thus, our implementation limits the process of generating TD-separator cuts as part of the ILP building time in the following three ways. 1. We skip TD-separators of size larger than s∗s^*, since enumerating all 2s∗2^s^* candidate sets can be expensive. We set s∗=14s^*=14; recall that the maximum ¯ tw in our experiments is at most 14, implying that the limit applies only to boundary cases in our experiments. 2. We only consider the best N∗N^* candidate sides for cut generation according to the following ranking. Let U∈U be a candidate side with ∂G(U)≠∅ _G(U)≠ . Define the (negative) fraction ρG(U)=−|∂G(U)∩Eu|/|∂G(U)| _G(U)=-| _G(U)∩ E_u|/| _G(U)| of unsafe edges in the cut. The score of U in G is defined as score(U)=(|∂G(U)|,ρG(U),|U|)score(U)=(| _G(U)|, _G(U),|U|). Each dimension of the score is to minimize, and scores are compared lexicographically. That is, firstly we seek small cuts, secondly high fractions of unsafe edges, and thirdly small sides. Ties are broken arbitrarily (by their time of appearance) for any two candidate sides with the same score. We set N∗=5000N^*=5000. 3. For each terminal pair si,ti\s_i,t_i\, we only consider cuts with at most m∗m^* edges. From these, we only add at most c∗c^* cuts to the ILP. We set m∗=10m^*=10 and c∗=20c^*=20. These limits affect only which valid cuts are generated; every added inequality is valid. 9.3 Results Solver performance. Overall, from our experiments, we can conclude the following regarding the solver performance in terms of runtimes; Figure 4 and Figure 5 accompany our conclusions. Figure 4: Cactus plots for all instances solved by each of the four solvers regarding building time (left), solver runtime (middle), and total runtime (right). Each inset zooms into the tail of the corresponding cactus plot, i.e., the slowest 2% of the common solved instances. 1. Preprocessing significantly decreases the solver runtime; see Figure 4 (middle) and Figure 5. Due to the short runtimes of the preprocessing, both solvers suing preprocessing ILPpre pre and ILPpretwc_ twc pre score best versus ILP; see Figure 5. 2. The runtime for building the ILP with the TD-separator cuts but without preprocessing is 3.53 s3.53\,s on average and never exceeded 25.64 s25.64\,s; see Figure 4 (left). This indicates that the heuristic makes use of small treewidth, small degree, and sparsity. Preprocessing reduced the building times for both with and without TD-separator cut generation, to roughly 65% for the average time and 90% of the maximum observed time. 3. For instances solved within roughly 100 s100\,s, TD-separator cuts do not appear to pay off. For harder instances, however, ILPpretwc_ twc pre dominates; see Figure 4 (right) and Figure 5. 4. While ILPtwc_ twc performs worse than ILP in total, its solver runtime is mostly shorter; see Figure 5 (left). While preprocessing also decreases the solver runtime, finally ILPpretwc_ twc pre scores best against all other solvers, even against ILPpre pre when it comes to solver runtime. Figure 5: ±1± 1- and weighted scores of solver pairs 1S_1 versus 2S_2. The weighted score is s(1,2)=time(2)−time(1)s(S_1,S_2)=time(S_2)-time(S_1), where timetime is either the solver runtime (left) or the total runtime (right). The ±1± 1-score is +1 if s(1,2)>0s(S_1,S_2)>0, and -1 if s(1,2)<0s(S_1,S_2)<0. So, a line going upwards corresponds to 1S_1 is faster than 2S_2, and downwards to 1S_1 is slower than 2S_2. For each solver pair, the commonly solved instances are sorted separately. Effect of the preprocessing. Our preprocessing routine (cf. Section 8.1) is fast and effective. Over all of our instances, the routine takes 1.151.15 seconds on average (median 0.670.67 second), where the maximum observed time is 12.4612.46 seconds. Yet, the routine significantly reduces the number of unsafe edges and of terminal pairs to 63% and 73% on average, respectively. See Figure 6 for a detailed overview. Figure 6: Statistics for the preprocessing routine. For our three different safety models A, B, and C, we find only a correlation regarding the reduction of terminal pairs. Comparing safety models A and C, the reduction changes from 50% to 70% for villages, and 62% to 79% for regions. Cost of detours. Table 3 gives an overview of the costs when the detour factor is increased. 1.2→1.31.2→ 1.3 1.3→1.51.3→ 1.5 1.2→1.51.2→ 1.5 Cost reduction (in %) 7.877.87 [6.5937.860.00_0.00^37.86] 10.7610.76 [8.9739.210.00_0.00^39.21] 17.6317.63 [15.4257.290.00_0.00^57.29] Table 3: Overview of the average relative cost reduction when increasing the detour factor α, with median, minimum (bottom), and maximum (top) in parentheses. Recall that we set the cost of an unsafe edge to its length; hence, our results display the savings of the total upgraded length. We highlight that when moving from α=1.2α=1.2 to α=1.3α=1.3, on average 7.87% of the costs are reduced, ranging from no reduction even up to 37.86% in the maximum case. For decision makers, we can often assume that the upper bound on the detour factor lies within a reasonable interval, say α∈[1.2,1.3]α∈[1.2,1.3]. Our results hence indicate that it is worth computing solutions for several upper bounds on the detour factor in the given interval and compare the trade-offs between detour length and budget. 10 Discussion On the experimental-modeling side, we randomly sample terminal pairs, whereas real-world demand is likely more structured around hotspots such as schools, supermarkets, or public-transport stops. Similarly, we set the upgrade cost of each street segment to its length. Besides length, however, other factors such as road type or local regulations may affect the construction costs. Incorporating such data would make the experiments more realistic. On the algorithmic side, our experiments show that preprocessing substantially reduces solver runtimes, making further and improved reduction rules a promising direction. For TD-separator cuts, their effectiveness may depend strongly on the generated candidate sides. Larger heuristic parameters increase model-building time, and adding too many cuts can even slow down the ILP solver (see Section A.1 for details). A better understanding of how to select strong cuts and which candidate sides yield them is an important future direction. On the theoretical side, it remains open which structural parameters beyond m_u and +p fes+p lead to fixed-parameter tractability, in particular whether +p fvs+p or the feedback edge number alone is sufficient. References [1] Allgemeiner Deutscher Fahrrad-Club e.V. (ADFC) (2025) ADFC-Fahrradklima-Test 2024: Rankingliste. Note: https://fahrradklima-test.adfc.de/fileadmin/BV/FKT/Download-Material/Ergebnisse_2024/Download-Element/Rankingliste_FKT_2024.pdfAccessed: 2026-06-17 Cited by: §9.1. [2] C. Beckx, S. Broekx, B. Degraeuwe, B. Beusen, and L. Int Panis (2013) Limits to active transport substitution of short car trips. Transportation Research Part D: Transport and Environment 22, p. 10–13. External Links: ISSN 1361-9209, Document, Link Cited by: §1. [3] H. L. Bodlaender and A. M. C. A. Koster (2010) Treewidth computations i. upper bounds. Information and Computation 208 (3), p. 259–275. External Links: Document Cited by: §9.2. [4] G. Boeing (2017) OSMnx: new methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems 65, p. 126–139. External Links: Document, Link Cited by: §2. [5] G. Boeing (2020) A multi-scale analysis of 27,000 urban street networks: every US city, town, urbanized area, and zillow neighborhood. Environment and Planning B: Urban Analytics and City Science 47 (4), p. 590–608. External Links: Document, Link Cited by: §2. [6] Y. Cai, G. P. Ong, and Q. Meng (2024) Sidewalk-based bicycle path network design incorporating equity in cycling time. Computer-Aided Civil and Infrastructure Engineering 39 (20), p. 3063–3082. External Links: Document Cited by: §9.1. [7] A. Cardillo, S. Scellato, V. Latora, and S. Porta (2006) Structural properties of planar graphs of urban street patterns. Physical Review E 73 (6), p. 066107. External Links: Document, Link Cited by: §2. [8] E. Chlamtác, M. Dinitz, G. Kortsarz, and B. Laekhanukit (2020) Approximating spanners and directed steiner forest: upper and lower bounds. ACM Transactions on Algorithms 16 (3), p. 33:1–33:31. External Links: Document, Link Cited by: §2. [9] M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh, and M. Wahlström (2016) On problems as hard as CNF-SAT. ACM Trans. Algorithms 12 (3), p. 41:1–41:24. External Links: Link, Document Cited by: Problem 7. [10] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh (2015) Parameterized algorithms. Springer. Cited by: §3. [11] M. Cygan, F. Grandoni, and T. Kavitha (2013) On pairwise spanners. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 20, p. 209–220. External Links: Document, Link Cited by: §2. [12] C. Doll, C. Brauer, and D. Duffner-Korbee (2024) The potential of cycling for climate protection and livable urban centers and regions: new methods for forecasting supply and demand in germany as a cycling nation up to 2035. Technical report Fraunhofer Institute for Systems and Innovation Research ISI, Karlsruhe, Germany. Note: Prepared on behalf of the Allgemeiner Deutscher Fahrrad-Club (ADFC) External Links: Link Cited by: §1. [13] M. Dom, D. Lokshtanov, and S. Saurabh (2014) Kernelization lower bounds through colors and ids. ACM Trans. Algorithms 11 (2), p. 13:1–13:20. External Links: Link, Document Cited by: Problem 6. [14] R. G. Downey and M. R. Fellows (2013) Fundamentals of parameterized complexity. Springer, London. External Links: Document, Link Cited by: Problem 6. [15] J. Duthie and A. Unnikrishnan (2014) Optimization framework for bicycle network design. Journal of Transportation Engineering 140 (7), p. 04014028. External Links: Document, Link Cited by: §2. [16] D. Eppstein and M. T. Goodrich (2008) Studying (non-planar) road networks through an algorithmic lens. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, p. 16:1–16:10. External Links: Document, Link Cited by: §2. [17] European Conference of Ministers of Transport (1984) Public transport in rural areas. OECD Publishing. External Links: Document Cited by: §1. [18] A. E. Feldmann and M. Lampis (2025) Parameterized algorithms for steiner forest in bounded width graphs. ACM Transactions on Algorithms. External Links: Document, Link Cited by: §2, §7. [19] M. R. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette (2009) On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science 410 (1), p. 53–61. External Links: Document, Link Cited by: Problem 14. [20] Forschungsgesellschaft für Straßen- und Verkehrswesen (2010) Empfehlungen für Radverkehrsanlagen: ERA. Ausgabe 2010 edition, FGSV 284, FGSV Verlag, Köln. Note: See p. 10 for network-level detour-factor recommendations External Links: ISBN 978-3-941790-63-6, Link Cited by: §1, §9.1. [21] P. G. Furth, M. C. Mekuria, and H. Nixon (2016) Network connectivity for low-stress bicycling. Transportation Research Record: Journal of the Transportation Research Board 2587 (1), p. 41–49. External Links: Document, Link Cited by: §1, §2. [22] E. Gassner (2010) The steiner forest problem revisited. Journal of Discrete Algorithms 8 (2), p. 154–163. Note: Selected papers from the 3rd Algorithms and Complexity in Durham Workshop ACiD 2007 External Links: ISSN 1570-8667, Document, Link Cited by: §2. [23] H. Gorges and G. Mingardo (2025) The potential of active modes to reduce short car trips. a data-driven approach. Transport Policy 168, p. 1–14. External Links: ISSN 0967-070X, Document, Link Cited by: §1. [24] E. Grigorescu, N. Kumar, and Y. Lin (2026) Approximation algorithms for directed weighted spanners. Algorithmica 88 (3), p. 38. External Links: Document, Link Cited by: §2. [25] A. A. Hagberg, D. A. Schult, and P. J. Swart (2008) Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, G. Varoquaux, T. Vaught, and J. Millman (Eds.), Pasadena, CA USA, p. 11–15. Cited by: §9.2. [26] R. Impagliazzo, R. Paturi, and F. Zane (2001) Which problems have strongly exponential complexity?. Journal of Computer and System Sciences 63 (4), p. 512–530. External Links: Document Cited by: Problem 2. [27] R. Impagliazzo and R. Paturi (2001) On the complexity of k-sat. Journal of Computer and System Sciences 62 (2), p. 367–375. External Links: Document Cited by: Problem 2. [28] R. M. Karp (1972) Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Eds.), p. 85–103. External Links: Document Cited by: §4. [29] L. Kellerhals and T. Koana (2022) Parameterized complexity of geodetic set. Journal of Graph Algorithms and Applications 26 (4), p. 401–419. External Links: Document, Link Cited by: §7. [30] Y. Kobayashi (2018) NP-hardness and fixed-parameter tractability of the minimum spanner problem. Theoretical Computer Science 746, p. 88–97. External Links: Document, Link Cited by: §2. [31] Y. Kobayashi (2020) An FPT algorithm for minimum additive spanner problem. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), LIPIcs, Vol. 154, p. 11:1–11:16. External Links: Link, Document Cited by: §2. [32] J. Lim, K. Dalmeijer, S. Guhathakurta, and P. V. Hentenryck (2022) The bicycle network improvement problem. Journal of Transportation Engineering, Part A: Systems 148 (11), p. 04022095. External Links: Document, Link, https://ascelibrary.org/doi/pdf/10.1061/JTEPBS.0000742 Cited by: §1, §2. [33] S. Maniu, P. Senellart, and S. Jog (2019) An experimental study of the treewidth of real-world graph data. In 22nd International Conference on Database Theory, ICDT 2019, Lisbon, Portugal, March 26-28, 2019, LIPIcs, p. 12:1–12:18. External Links: Link, Document Cited by: §2. [34] A. Mauttone, G. Mercadante, M. Rabaza, and F. Toledo (2017) Bicycle network design: model and solution algorithm. Transportation Research Procedia 27, p. 969–976. External Links: Document Cited by: §2. [35] N. Mueller, D. Rojas-Rueda, T. Cole-Hunter, A. de Nazelle, E. Dons, R. Gerike, T. Götschi, L. Int Panis, S. Kahlmeier, and M. Nieuwenhuijsen (2015) Health impact assessment of active transportation: a systematic review. Preventive Medicine 76, p. 103–114. External Links: ISSN 0091-7435, Document, Link Cited by: §1. [36] L. G. Natera Orozco, F. Battiston, G. Iñiguez, and M. Szell (2020) Data-driven strategies for optimal bicycle network growth. Royal Society Open Science 7 (12), p. 201130. External Links: Document, Link Cited by: §2. [37] P. Oja, S. Titze, A. Bauman, B. de Geus, P. Krenn, B. Reger-Nash, and T. Kohlberger (2011) Health benefits of cycling: a systematic review. Scandinavian Journal of Medicine & Science in Sports 21 (4), p. 496–509. Note: Epub 2011 Apr 18 External Links: Document Cited by: §1. [38] H. Poltimäe, M. Rehema, J. Raun, and A. Poom (2022) In search of sustainable and inclusive mobility solutions for rural areas. European Transport Research Review 14 (1), p. 13. External Links: Document, Link, ISSN 1866-8887 Cited by: §1. [39] D. J. Rose, R. E. Tarjan, and G. S. Lueker (1976) Algorithmic aspects of vertex elimination on graphs. SIAM Journal on Computing 5 (2), p. 266–283. External Links: Document Cited by: §9.2. [40] J. E. Schoner and D. M. Levinson (2014) The missing link: bicycle infrastructure networks and ridership in 74 US cities. Transportation 41 (6), p. 1187–1204. External Links: Document, Link Cited by: §1, §2. [41] K. Simonov, F. Soheil, and S. Verma (2026) Finding minimum distance preservers: a parameterized study. arXiv preprint arXiv:2603.21442. External Links: 2603.21442, Link Cited by: §2. [42] SINUS-Institut and Bundesministerium für Verkehr (2026) Fahrrad-Monitor Deutschland 2025 – Erwachsenen- und Jugendbefragung (14–69 Jahre). Technical report Bundesministerium für Verkehr. External Links: Link Cited by: §1. [43] C. Steinacker, D. Storch, M. Timme, and M. Schröder (2022) Demand-driven design of bicycle infrastructure networks for improved urban bikeability. Nature Computational Science 2, p. 655–664. External Links: Document, Link Cited by: §2. [44] M. Szell, S. Mimar, T. Perlman, G. Ghoshal, and R. Sinatra (2022) Growing urban bicycle networks. Scientific Reports 12, p. 6765. External Links: Document, Link Cited by: §2. [45] C. van Dülmen, M. Šimon, and A. Klärner (2022) Transport poverty meets car dependency: a gps tracking study of socially disadvantaged groups in european rural peripheries. Journal of Transport Geography 101, p. 103351. External Links: ISSN 0966-6923, Document, Link Cited by: §1. [46] A. R. Vierø and M. Szell (2025) Network analysis of the danish bicycle infrastructure: bikeability across urban–rural divides. Geographical Analysis 57 (4), p. 616–640. External Links: ISSN 1538-4632, Link, Document Cited by: §1. Appendix A Appendix A.1 Further Experimental Results Recall that for parameters (s∗,N∗,m∗,c∗)(s^*,N^*,m^*,c^*) of the TD-separator cut heuristic, we selected the setup χ1=(14,5000,10,20) _1=(14,5000,10,20) (cf. Section 9.2). We also compared this setup with two other setups χ1/2=12⋅χ1 _1/2= 12· _1 and χ2=2⋅χ1 _2=2· _1, that is, when halving and doubling the parameters. Denote the corresponding ILP-based algorithms by ILPtwc1/2_ twc1/2 and ILPtwc2_ twc2 without preprocessing, and by ILPpretwc1/2_ twc1/2 pre and ILPpretwc2_ twc2 pre when preprocessing is applied. Figure 7 Figure 7: Cactus plots for all region instances solved by each of the three solvers based on different parameters with respect to the TD-separator cut heuristic with and without preprocessing. Presented are building time (left), solver runtime (middle), and total runtime (right). Each inset zooms into the tail of the corresponding cactus plot, i.e., the slowest 3% of the common solved region instances. and Figure 8 Figure 8: Scores (cf. Figure 5) of all TD-separator cut heuristics for all commonly solved region instances, where the largest setup competes against both the lower two setups, with and without preprocessing. Presented are building time (left), solver runtime (middle), and total runtime (right). show their performances and scores on region instances, respectively. Larger parameters lead to larger model-building times, but does not improve performance overall. Concretely, ILPtwc2_ twc2 has the largest average model-building time (almost twice the average model-building time of ILPtwc1/2_ twc1/2), but the smallest average and median solver runtime (marginally, e.g. regarding the average solver runtime, 28.99 s28.99\,s compared to 29.60 s29.60\,s for ILPtwc1/2_ twc1/2) among the commonly solved instances. In particular, larger candidate sets interact nontrivially with preprocessing and can even degrade performance. Concretely, the average total runtime ILPpretwc_ twc pre is the smallest with 28.92 s28.92\,s, yet ILPpretwc1/2_ twc1/2 pre achieves the smallest median (2.79 s2.79\,s compared to second place 3.07 s3.07\,s by ILPpretwc_ twc pre) and maximum (3373.82 s3373.82\,s compared to second place 4780.89 s4780.89\,s by ILPpretwc2_ twc2 pre) total runtime among the commonly solved instances.