CS Paper Radar

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

Till Fluschnik

cs.DS cs.MA ·submitted 2026-08-10 11:39 UTC · v1
publishedtheory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Dichotomy for Terminal Cyclability

cs.DS ·2026-11-04 ·Matthias Bentert, Dario Cavallaro, Sebastian Wiederrecht
similarity 0.68
Abstract

Given an undirected graph $G$ and a set $R \subseteq V(G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$. We establish a complexity dichotomy for this problem on red-minor-closed classes of annotated graphs. In particular, we show that Terminal Cyclability is polynomial-time solvable on every such class excluding any annotated planar graph. The problem is NP-complete whenever the class contains all annotated planar graphs. More precisely, we give an $|G|^{2^{\mathbf{poly}(b)}}$-time algorithm, where $b$ is the bidimensionality of $(G,R)$. Our main technical contribution is the introduction of a weak irrelevant vertex rule. Rather than removing irrelevant vertices until the treewidth becomes constant, we only remove irrelevant vertices until the treewidth is logarithmic in the graph size. Such a weakening is necessary as a parameter-only treewidth threshold for an irrelevant vertex rule in this setting is known to be impossible to realise. Combined with a single-exponential algorithm for Terminal Cyclability parameterized by treewidth, this yields the polynomial-time algorithm for our dichotomy.

0.24

Eccentricity Shortest Path: the structural parameter landscape

cs.DS math.CO ·2026-10-14 ·Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep
theory similarity 0.66
Abstract · 74 pages, short abstract for arXiv

The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We study its structural parameterized complexity. We give fixed-parameter algorithms for vertex-deletion distance to cographs, vertex-deletion distance to interval graphs, and bandwidth. The interval-deletion result answers a question of Bhyravarapu et al. (IWOCA 2023). We obtain XP algorithms for vertex-deletion distance to chordal graphs, clique-width, and rank-width, without requiring expressions or decompositions for the latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove $\mathsf{W}[3]$-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; $\mathsf{W}[2]$-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number $\ell$, we obtain an $O(\ell^4)$-bit compression and a polynomial kernel. Finally, unless $\mathsf{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.

0.24

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

cs.DS ·2026-10-13 ·Hitendra Kumar, Mathieu Mari, R. B. Sandeep
theory similarity 0.65
Abstract · added acknowledgement

Fix a set $S$ of positive integers. An $S$-Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belongs to $S$. We study the complexity of deciding whether an input graph admits such an ordering, together with the corresponding path variants with prescribed or unrestricted endpoints. We complete the complexity classification for undirected graphs. In particular, we prove NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026). For digraphs, all three problems are NP-complete for every fixed finite nonempty $S$ and admit linear-time algorithms when $S$ is cofinite. For other fixed infinite sets $S$, we establish NP-complete and undecidable cases, with undecidability occurring even when $S$ is recursive.

0.23

Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth

cs.DS ·2026-10-12 ·Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner +1 more
theory similarity 0.65
Abstract · 32 pages, 8 figures

We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on their shared graph? We establish fixed-parameter tractability with respect to the vertex integrity of the union graph (that is, the union of the input graphs) plus k, resolving an open question and generalizing the known algorithm parameterized by vertex cover number plus k. Our main technical contribution on the way towards this result is the extension of the recently introduced Ramsey pruning technique beyond ordering problems. Finally, we complement our tractability result with a lower bound that establishes NP-hardness when both k and the pathwidth of the union graph are bounded by constants, ruling out a generalization of our main result to path- or treewidth.

0.31

Emergency Vertex Cover

cs.DS ·2026-09-17 ·Eric Angel, Evangelos Bampas, Evripidis Bampis, Vincent Chau, Johanne Cohen +2 more
theory similarity 0.64
Abstract

The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is incident to at least one vertex in this subset. Among its variants, the Min-Power-Cover problem stands out due to its practical applications, such as camera placement at intersections: in an edge-weighted graph, an edge is covered if one of its endpoints is assigned a power value at least as large as the edge's weight. In this paper, we introduce the Emergency Vertex Cover (Em-VC) problem where an edge may be covered not only by its endpoints, but also by a distant vertex, provided the vertex is given sufficient power to "cover" the cumulative weight of the edges along a shortest path to one of the edge's endpoints plus the weight of the edge. Em-VC is motivated by different practical scenarios, e.g. the need for urban disaster response, where ensuring accessibility to all road segments (edges of the graph) is crucial for effective aid delivery. We prove that Em-VC is NP-hard, derive lower bounds, and design a polynomial-time algorithm for its continuous version. Moreover, we present a 4/3-approximation algorithm for the discrete case and identify several special graph classes for which the problem can be solved in polynomial time.

0.42

Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path

cs.CC cs.DMmath.CO ·2026-11-10 ·Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider, Torsten Ueckerdt
similarity 0.64
Abstract

We examine the computational complexity of well-known problems on subgraphs of the strong product of two paths. Namely, for Max Cut we show NP-hardness on induced subgraphs of $P \boxtimes P$ answering a question by Dvořák, Huynh, Joret, Liu, and Wood (2021). For 3-Edge Coloring we show NP-hardness on subgraphs of $P \boxtimes P$ and that it is equivalent to 3-Edge Coloring on planar graphs for induced subgraphs of $P \boxtimes P$. It is a long standing open question whether 3-Edge Coloring on planar graphs is NP-hard. As a second contribution, we consider graphs of the form $G \boxtimes P$ and show that Feedback Vertex Set on these graphs is FPT in the clique-width of $G$. Furthermore, we show that it can be solved in polynomial time if $G$ is chordal or co-comparable and that the computational complexity depends on the parity of $P$ if $G$ is bipartite. Namely, it is solvable in polynomial time if $P$ has an even number of vertices but is NP-complete otherwise. For Max Cut, we show that it can be solved in polynomial time if $G$ is bipartite.

0.06

Parameterized Complexity of Edge-Constrained Graph Partitioning

cs.DS cs.CC ·2026-08-28 ·Ajinkya Gaikwad, Jan Pokorný, Tomáš Valla
similarity 0.64
Abstract

We study the Edge-Constrained Graph Partitioning Problem (ECGP), which asks whether the vertices of a graph can be partitioned into r parts, each inducing at least gamma edges. We also consider a balanced variant (BECGP), requiring equal-sized parts, and signed variants, where the utility of a part is the difference between its numbers of positive and negative edges. We show that ECGP and BECGP remain NP-hard for fixed gamma, while BECGP is also NP-hard for fixed r. For the natural parameterization r+gamma, both problems admit polynomial kernels. We obtain FPT algorithms for ECGP and BECGP parameterized by maximum leaf number, vertex deletion distance to a clique, cluster vertex deletion number plus gamma, and vertex integrity. Furthermore, ECGP is FPT parameterized by vertex deletion distance to stars plus gamma and vertex deletion distance to paths plus gamma. On the negative side, ECGP and BECGP are W[1]-hard when parameterized by r together with several structural parameters. In particular, hardness holds for feedback edge set, vertex deletion distance to stars or paths, and modular width even when the corresponding parameter is zero. The problems are also W[1]-hard parameterized by cluster vertex deletion number plus r, and by clique-width even when gamma=3. For signed graphs, both variants are NP-hard even when r+gamma=3 and the input is a disjoint union of two cliques. Finally, the balanced signed variant is W[1]-hard parameterized by treedepth plus r, even when gamma=0.

0.09

Fair, Efficient and Connected Allocations on Graphs

cs.GT ·2026-08-19 ·Susobhan Bandopadhyay, Anish Datta, Palash Dey, Ashlesha Hota, Abhishek Sahu
published similarity 0.64
Abstract · Accepted to Algorithmic Decision Theory (ADT) 2026, Paris, France

We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximization. We first establish a sharp complexity dichotomy in the classical setting: both problems are NP-hard in general and remain hard even on very restricted graph classes such as paths, and consequently trees and cycles. In contrast, they are polynomial-time solvable on stars, but this tractability does not extend even to the case of two disjoint stars. Motivated by these boundaries, we move to the parameterized complexity framework, where we study the problem with respect to the number of agents. We obtain fixed-parameter tractability (FPT) on trees and, more generally, identify a robust phenomenon whereby tractability on a connected graph class extends to disjoint unions of graphs from that class. We further investigate the parameters treewidth and treedepth, showing that the utilitarian version is FPT for both, whereas the egalitarian version remains para-NP-hard even on graphs of treedepth two. Finally, we analyze the number of connected components and show that except for the collection of stars, the problems remain hard. For the collection of stars,while we obtain para-NP-hardness for the egalitarian case, the utilitarian case gives W[2]-hardness together with an XP algorithm.

0.25