CS Paper Radar

Maximum Covering Network Design on Graphs with Low Connectivity: Dynamic Programming and Block-Cut Trees

Felix Rauh, Jannik Matuschke, Hande Yaman

cs.DM math.OCcs.DS ·submitted 2026-08-21 09:13 UTC · v1

Abstract

Planning accessible public services such as health care, emergency response, and schools often requires not only choosing where to open facilities but also improving the network that connects people to them, for example upgrading flood-prone roads in vulnerable regions. Most location models, however, take the network as fixed and the budget as given. We study the Maximum Covering Network Design Problem, in which a single budget is shared between opening facilities and upgrading weak links to maximize the population within a target travel distance of an open facility. The problem is hard even on the simplest networks, and planners usually want to see how coverage grows with the budget, not a single plan. We develop an exact dynamic-programming framework that exploits a property common to real road networks: their low connectivity, with many cut points whose removal disconnects the network. On trees, the recursion is self-contained: each state reduces to a few simple facility and upgrade choices that are fast to compute without a solver, giving predictable running times; for larger budgets and travel distances it outperforms solving the MILP formulation directly. On general low-connectivity networks, the framework decomposes the problem at the cut points and embeds a given MILP formulation to solve the resulting pieces, coordinating them through coverage conditions at the interfaces. This lets us compare a formulation on its own against the same formulation inside the framework: across 306 test cases the framework matches or outperforms direct solving on more than 80% of instances. Because it evaluates all budget levels in a single run, it also yields the full coverage-versus-budget curve at no extra cost, whereas direct solving must split its time across individual budgets.

Closest papers

Nearest neighbours by meaning across the whole index.

Emergency Vertex Cover

cs.DS ·2026-09-17 ·Eric Angel, Evangelos Bampas, Evripidis Bampis, Vincent Chau, Johanne Cohen +2 more
theory similarity 0.66
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

Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage

cs.DS ·2026-10-14 ·Quanlong Niu, Riheng Jia
theory similarity 0.64
Abstract

The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph vertices to cover every edge while minimizing the total budget. The cost of covering an edge from a station is the shortest-path distance from the station to the nearer endpoint plus the edge length. We study how restricting the number of stations affects the cost of ordinary and fault-tolerant coverage. In ordinary Em-VC, we prove that the optimal solution using at most two stations costs at most $5/4$ times the unrestricted optimum, improving the known $4/3$ guarantee for a single station. A recurrence extends this bound to larger station limits, giving approximation factors that converge to $\sqrt{5}-1$. Budget-threshold enumeration computes the restricted optimum in polynomial time for every fixed station limit. Under $k$-fold coverage, every edge must be covered by at least $k$ distinct stations, ensuring coverage after any $k-1$ station failures. We prove that selecting the $k$ vertices with the smallest full-coverage costs yields a $2$-approximation relative to the unrestricted optimum for $k$-fold coverage. When $k=2$, we combine upper bounds derived from the structure of the covering balls to improve the approximation guarantee to $5/3$.

0.09

Buy-at-Bulk Facility Location on Trees

cs.DS ·2026-08-26 ·Shamisa Nematollahi, Daniel Vaz
similarity 0.64
Abstract · Presented at WAOA 2025

We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+ε)$-approximation for any $ε> 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+ε$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.

0.28

Approximation Algorithms for Multi-Criteria Network Design Problems

cs.DS ·2026-11-03 ·Mehrshad Taziki, Ali Vakilian
theoryhot direction similarity 0.62
Abstract

Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.

0.27

A Graph Theoretic Approach to Spatial Modeling of Post Disaster Shelter Camps Using Rainbow and Roman Domination Parameters

cs.DM ·2026-09-30 ·Didem Gözüpek, Piotr Lange, Joanna Raczek
similarity 0.61
Abstract

Effective spatial organization of post-disaster shelter camps is essential for ensuring access to basic services while making efficient use of limited space and resources. In this paper, we propose a graph-theoretic framework for shelter-camp facility placement based on rainbow $k$-domination and Roman domination. Rainbow $k$-domination models the simultaneous accessibility of distinct facility types, such as sanitation units, kitchens, water points, and schools, whereas Roman domination is used to represent services with different capacity levels, illustrated through Wi-Fi deployment. We present an $O(nk)$-time algorithm for finding a minimum rainbow $k$-dominating set of a tree with $n$ vertices, which is linear in $n$ for fixed $k$, and computational experiments confirm its scalability on large instances. For general graphs, we establish new lower and upper bounds on the rainbow $k$-domination number. We further investigate its relationship with Roman domination, derive structural properties of graphs attaining the extremal equality between the two parameters, and prove that recognizing such graphs is NP-hard. These results provide a theoretical foundation for domination-based approaches to facility placement in post-disaster shelter planning.

0.49

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.60
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25

The Influence of Agent Models on the Complexity of Bus Routing

cs.CC cs.MA ·2026-08-18 ·Eva Deltl, Christian Komusiewicz, Jurek Rostalsky, Johannes Schröder, Luca Pascal Staus
similarity 0.59
Abstract

In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account for several factors, including agents' cost for reaching the bus stops, their travel time, or the energy consumption of the buses. We study the complexity of several variants of this problem, focusing on how the objective function and the models for agents' walking costs influence the problem complexity. After observing that even the simplest agent cost model leads to hardness on general networks, we consider networks with tree structure. Our main findings are as follows. First, allowing agent-specific cost models leads to hardness even on extremely limited trees such as stars. Second, consistent agent models (where agents differ only in their starting points and destinations) make the problem easier in some cases. Finally, allowing agents to choose between using the bus and walking directly can make the problem considerably harder. Most of our hardness results show not only classical NP-hardness but also parameterized intractability for the natural parameter $k$, the number of bus stops.

0.26

Stochastic Corridor Time Network Capacity Planning for Low Altitude Airspace Systems

cs.CE ·2026-08-11 ·Yipu Yao, Li Ding, Yanlu Zhao
similarity 0.59
Abstract

Regulators in China, the United States, and the European Union now provide low-altitude airspace access as priced, time-windowed corridor authorizations, booked in advance and forfeited if unused. We ask how much capacity a UAV logistics planner should reserve on each corridor--time unit before demand is realized, to maximize expected profit net of reservation cost. Reserved capacity cannot be transferred across corridors or time windows and is consumed jointly along time-respecting paths, so reservations are coupled through the network in ways that models with exogenous airspace capacity cannot capture. We formulate a two-stage stochastic program whose recourse selects and routes accepted requests on a time-expanded network, prove its arc-based and path-packing forms equivalent, and solve it by Benders decomposition with column-generated subproblems. The decomposition operates on the LP relaxation, and all reported reservation and routing decisions are recovered as integer plans. Computational experiments achieve single-digit LP-Benders gaps on moderate-sized networks and extend to much larger instances through a truncated-path approach. A Shenzhen case study shows reservations concentrating on structurally central corridors, with demand level and reservation price having more influence on the quantity of capacity reserved than the selection of corridors.

0.04