=== A. arXiv abstracts of candidates ===
[1807.09389v1] Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings -- Haris Angelidakis
   ABSTRACT: In this thesis, we design algorithms for several NP-hard problems in both worst and beyond worst case settings. In the first part of the thesis, we apply the traditional worst case methodology and design approximation algorithms for the Hub Labeling problem; Hub Labeling is a preprocessing technique introduced to speed up shortest path queries. Before this work, Hub Labeling had been extensively studied mainly in the beyond worst case analysis setting, and in particular on graphs with low highway dimension. In this work, we significantly improve our theoretical understanding of the problem and design (worst-case) algorithms for various classes of graphs, such as general graphs, graphs with unique shortest paths and trees, as well as provide matching inapproximability lower bounds for the problem in its most general settings. Finally, we demonstrate a connection between computing a Hub Labeling on a tree and searching for a node in a tree. In the second part of the thesis, we turn to beyond worst case analysis and extensively study the stability model introduced by Bilu and Linial in an attempt to describe real-life instances of graph partitioning and clustering problems. Informally, an instance of a combinatorial optimization problem is stable if it has a unique optimal solution that remains the unique optimum under small multiplicative perturbations of the parameters of the input. Utilizing the power of convex relaxations for stable instances, we obtain several results for problems such as Edge/Node Multiway Cut, Independent Set (and its equivalent, in terms of exact solvability, Vertex Cover), clustering problems such as $k$-center and $k$-median and the symmetric Traveling Salesman problem. We also provide strong lower bounds for certain families of algorithms for co
[1607.05133v1] Improved Hardness for Cut, Interdiction, and Firefighter Problems -- Euiwoong Lee
   ABSTRACT: We study variants of the classic $s$-$t$ cut problem and prove the following improved hardness results assuming the Unique Games Conjecture (UGC). - For any constant $k \geq 2$ and $ε&gt; 0$, we show that Directed Multicut with $k$ source-sink pairs is hard to approximate within a factor $k - ε$. This matches the trivial $k$-approximation algorithm. By a simple reduction, our result for $k = 2$ implies that Directed Multiway Cut with two terminals (also known as $s$-$t$ Bicut) is hard to approximate within a factor $2 - ε$, matching the trivial $2$-approximation algorithm. Previously, the best hardness factor for these problems (for constant $k$) was $1.5 - ε$ under the UGC. - For Length-Bounded Cut and Shortest Path Interdiction, we show that both problems are hard to approximate within any constant factor, even if we allow bicriteria approximation. If we want to cut vertices or the graph is directed, our hardness factor for Length-Bounded Cut matches the best approximation ratio up to a constant. Previously, the best hardness factor was $1.1377$ for Length-Bounded Cut and $2$ for Shortest Path Interdiction. - Assuming a variant of the UGC (implied by another variant of Bansal and Khot), we prove that it is hard to approximate Resource Minimization Fire Containment within any constant factor. Previously, the best hardness factor was $2$. Our results are based on a general method of converting an integrality gap instance to a length-control dictatorship test for variants of the $s$-$t$ cut problem, which may be useful for other problems.
[2509.01413v1] Hitting Geodesic Intervals in Structurally Restricted Graphs -- Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada, Yota Otachi, Hayato Takaike
   ABSTRACT: Given a graph $G = (V,E)$, a set $T$ of vertex pairs, and an integer $k$, Hitting Geodesic Intervals asks whether there is a set $S \subseteq V$ of size at most $k$ such that for each terminal pair $\{u,v\} \in T$, the set $S$ intersects at least one shortest $u$-$v$ path. Aravind and Saxena [WALCOM 2024] introduced this problem and showed several parameterized complexity results. In this paper, we extend the known results in both negative and positive directions and present sharp complexity contrasts with respect to structural graph parameters. We first show that the problem is NP-complete even on graphs obtained by adding a single vertex to a disjoint union of 5-vertex paths. By modifying the proof of this result, we also show the NP-completeness on graphs obtained from a path by adding one vertex and on graphs obtained from a disjoint union of triangles by adding one universal vertex. Furthermore, we show the NP-completeness on graphs of bandwidth 4 and maximum degree 5 by replacing the universal vertex in the last case with a long path. Under standard complexity assumptions, these negative results rule out fixed-parameter algorithms for most of the structural parameters studied in the literature (if the solution size $k$ is not part of the parameter). We next present fixed-parameter algorithms parameterized by $k$ plus modular-width and by $k$ plus vertex integrity. The algorithm for the latter case does indeed solve a more general setting that includes the parameterization by the minimum vertex multiway-cut size of the terminal vertices. We show that this is tight in the sense that the problem parameterized by the minimum vertex multicut size of the terminal pairs is W[2]-complete. We then modify the proof of this intractability result and show that the problem is 
[1511.02801v1] Parameterized complexity of length-bounded cuts and multi-cuts -- Dušan Knop, Pavel Dvořák
   ABSTRACT: We show that the Minimal Length-Bounded L-But problem can be computed in linear time with respect to L and the tree-width of the input graph as parameters. In this problem the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least L long. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width) and that this problem does not admit polynomial kernel when parameterized by tree-width and L. We also derive an FPT algorithm for the Minimal Length-Bounded Cut problem when parameterized by the tree-depth. Thus showing an interesting paradigm for this problem and parameters tree-depth and path-width.
[1910.03409v1] Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters -- Matthias Bentert, Klaus Heeger, Dušan Knop
   ABSTRACT: In the presented paper we study the Length-Bounded Cut problem for special graph classes as well as from a parameterized-complexity viewpoint. Here, we are given a graph $G$, two vertices $s$ and $t$, and positive integers $β$ and $λ$. The task is to find a set of edges $F$ of size at most $β$ such that every $s$-$t$-path of length at most $λ$ in $G$ contains some edge in $F$. Bazgan et al. conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph $G$ is a~proper interval graph. We confirm this conjecture by showing a dynamic-programming based polynomial-time algorithm. We strengthen the W[1]-hardness result of Dvořák and Knop. Our reduction is shorter, seems simpler to describe, and the target of the reduction has stronger structural properties. Consequently, we give W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
[1512.00333v3] Fractals for Kernelization Lower Bounds -- Till Fluschnik, Danny Hermelin, André Nichterlein, Rolf Niedermeier
   ABSTRACT: The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos [Discrete Optim. 2011], we show that, unless NP $\subseteq$ coNP / poly, the NP-hard Length-Bounded Edge-Cut (LBEC) problem (delete at most $k$ edges such that the resulting graph has no $s$-$t$ path of length shorter than $\ell$) parameterized by the combination of $k$ and $\ell$ has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex deletion problems. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.
[2607.29649v1] Structural Tractability Frontiers for Metric Repair -- Asaf Etgar, Anna C. Gilbert, Jamie Tucker-Foltz
   ABSTRACT: Given a graph $G$ labeled with positive distances on each edge, what is the fewest number of edge distances that must be modified for $G$ to become a metric? It is known that this metric repair problem is $\mathrm{NP}$-hard on general graphs, with prior work focusing on approximations and fixed-parameter tractability with respect to properties of the input distance function. In this paper, we ask what structural properties of the graph itself make metric repair tractable. On the positive side, we give pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth. An immediate consequence of this result is a new algorithm for the length-bounded multicut problem, with a parameterized runtime bound in terms of the treewidth of a modestly augmented graph. Surprisingly, pseudo-polynomial time turns out to be the best one can hope for: We complement our algorithm with a proof that metric repair is weakly $\mathrm{NP}$-hard even on graphs of pathwidth at most six. We also prove that planarity does not help either, as the problem remains strongly $\mathrm{NP}$-hard even on grid graphs.
=== B. extra arXiv queries ===
arxiv all:"shortest paths" AND all:"hitting set" AND all:pairs: status=200 total=['7']
   - 2003.03058v1 Exponentially Faster Shortest Paths in the Congested Clique
   - 2606.03674v1 Deterministic Distance Approximation in MPC via Improved Hitting Sets
   - 1412.3445v2 Approximation of Distances and Shortest Paths in the Broadcast Congest Clique
   - 1611.01210v1 Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs
   - 2101.02311v1 A Deterministic Parallel APSP Algorithm and its Applications
   - 1609.00512v2 Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
   - 2106.02120v2 Approximation Algorithms for Min-Distance Problems in DAGs
arxiv all:"shortest path" AND all:blocking AND all:pairs AND all:edges: status=200 total=['4']
   - 2502.08125v1 Incremental Approximate Single-Source Shortest Paths with Predictions
   - 1405.6893v8 Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs
   - 1404.3082v4 Further Hardness Results on Rainbow and Strong Rainbow Connectivity
   - 1910.04911v1 Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications
arxiv abs:"L-bounded cut": status=200 total=['1']
   - 1705.02390v2 On Algorithms for $L$-bounded Cut Problem
arxiv abs:"length-bounded" AND abs:cut: status=200 total=['5']
   - 1607.05133v1 Improved Hardness for Cut, Interdiction, and Firefighter Problems
   - 1910.03409v1 Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters
   - 1511.02801v1 Parameterized complexity of length-bounded cuts and multi-cuts
   - 1512.00333v3 Fractals for Kernelization Lower Bounds
   - 1311.0779v2 Converting homotopies to isotopies and dividing homotopies in half in an effective way
arxiv abs:"shortest path" AND abs:interdiction AND abs:"multiple pairs": status=200 total=['0']
arxiv abs:"shortest paths" AND abs:"multiway cut": status=200 total=['3']
   - 1607.05133v1 Improved Hardness for Cut, Interdiction, and Firefighter Problems
   - 1807.09389v1 Shortest path queries, graph partitioning and covering problems in worst and beyond worst case settings
   - 1405.4960v3 Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems
arxiv abs:"geodetic" AND abs:hitting: status=200 total=['1']
   - 2608.29680v1 GeoRay: Gauge-Aware Feed-Forward Satellite 3D Reconstruction in the Geodetic Frame
arxiv abs:"distance" AND abs:"edge deletion" AND abs:"NP-hard" AND abs:terminals: status=200 total=['0']
=== C. OpenAlex abstracts (inverted index) ===
[10.1145/3622941] status=200 Attacking Shortest Paths by Cutting Edges (2023) -- Benjamin A. Miller, Zohair Shafi, Wheeler Ruml, Yevgeniy Vorobeychik, Tina Eliassi‐Rad, Scott Alfeld
   ABSTRACT: Identifying shortest paths between nodes in a network is a common graph analysis problem that is important for many applications involving routing of resources. An adversary that can manipulate the graph structure could alter traffic patterns to gain some benefit (e.g., make more money by directing traffic to a toll road). This article presents theForce Path Cutproblem, in which an adversary removes edges from a graph to make a particular path the shortest between its terminal nodes. We prove that the optimization version of this problem is APX-hard but introducePATHATTACK, a polynomial-time approximation algorithm that guarantees a solution within a logarithmic factor of the optimal value. In addition, we introduce theForce Edge CutandForce Node Cutproblems, in which the adversary targets a particular edge or node, respectively, rather than an entire path. We derive a nonconvex optimization formulation for these problems and derive a heuristic algorithm that usesPATHATTACKas a subroutine. We demonstrate all of these algorithms on a diverse set of real and synthetic networks, illustrating where the proposed algorithms provide the greatest improvement over baseline methods.
[10.1145/3179407] status=200 Network Resilience and the Length-Bounded Multicut Problem (2018) -- Alan Kuhnle, Victoria G. Crawford, My T. Thai
   ABSTRACT: Motivated by networked systems in which the functionality of the network depends on vertices in the network being within a bounded distance T of each other, we study the length-bounded multicut problem: given a set of pairs, find a minimum-size set of edges whose removal ensures the distance between each pair exceeds T . We introduce the first algorithms for this problem capable of scaling to massive networks with billions of edges and nodes: three highly scalable algorithms with worst-case performance ratios. Furthermore, one of our algorithms is fully dynamic, capable of updating its solution upon incremental vertex / edge additions or removals from the network while maintaining its performance ratio. Finally, we show that unless NP ⊆ BPP , there is no polynomial-time, approximation algorithm with performance ratio better than $Ømega (T)$, which matches the ratio of our dynamic algorithm up to a constant factor.
[10.1145/1868237.1868241] status=200 Length-bounded cuts and flows (2010) -- Georg Baier, Thomas Erlebach, Alexander Hall, Ekkehard Köhler, Petr Kolman, Ondřej Pangrác, Heiko Schilling, Martin Skutella
   ABSTRACT: For a given number L , an L -length-bounded edge-cut (node-cut, respectively) in a graph G with source s and sink t is a set C of edges (nodes, respectively) such that no s - t -path of length at most L remains in the graph after removing the edges (nodes, respectively) in C . An L -length-bounded flow is a flow that can be decomposed into flow paths of length at most L . In contrast to classical flow theory, we describe instances for which the minimum L -length-bounded edge-cut (node-cut, respectively) is Θ( n 2/3 )-times (Θ(√ n )-times, respectively) larger than the maximum L -length-bounded flow, where n denotes the number of nodes; this is the worst case. We show that the minimum length-bounded cut problem is NP -hard to approximate within a factor of 1.1377 for L ≥ 5 in the case of node-cuts and for L ≥ 4 in the case of edge-cuts. We also describe algorithms with approximation ratio O (min{ L , n/L }) ⊆ O √ n in the node case and O (min { L , n 2 / L 2 ,√ m } ⊆ O 2/3 in the edge case, where m denotes the number of edges. Concerning L -length-bounded flows, we show that in graphs with unit-capacities and general edge lengths it is NP -complete to decide whether there is a fractional length-bounded flow of a given value. We analyze the structure of optimal solutions and present further complexity results.
[10.1007/s00453-018-0408-7] status=200 Parameterized Complexity of Length-bounded Cuts and Multicuts (2018) -- Pavel Dvořák, Dušan Knop
   ABSTRACT: 
[10.1016/j.jcss.2021.12.002] status=200 Length-bounded cuts: Proper interval graphs and structural parameters (2021) -- Matthias Bentert, Klaus Heeger, Dušan Knop
   ABSTRACT: We study the Length-Bounded Cut problem for special graph classes and from a parameterized complexity viewpoint. Here, we are given a graph G, two vertices s and t, and positive integers β and λ. The task is to find a set F of at most β edges such that each s-t-path of length at most λ in G contains some edge in F. Bazgan et al. [20] conjectured that Length-Bounded Cut admits a polynomial-time algorithm if the input graph is a proper interval graph. We confirm this conjecture by providing a dynamic-programming-based polynomial-time algorithm. Moreover, we strengthen the W[1]-hardness result of Dvořák and Knop [15] for Length-Bounded Cut parameterized by pathwidth by showing W[1]-hardness for the combined parameter pathwidth and maximum degree of the input graph. Finally, we prove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Both our hardness results complement known XP algorithms.
[10.1137/0222034] status=200 Blocking Small Cuts in a Network, and Related Problems (1993) -- Daniel Bienstock, Nicole Romito Diaz
   ABSTRACT: Let G be a graph with weights on the edges, S a subset of vertices, and k an integer. The problem of computing a minimum-weight subset of edges that meets all the cuts of cardinality $ \leqslant k$ that separate pairs of vertices in S is considered. This problem is motivated by issues in network survivability. Assuming $|S| = 2$, it is shown that although this problem is NP-hard, it can be solved in linear time for each fixed value of k. Furthermore, if $|S| > 2$, the problem is NP-hard even for small values of k but can be solved in linear time for each fixed k and $|S|$.
[10.1007/978-3-540-35751-6_23] status=404 None (None) -- 
   ABSTRACT: 
openalex search "shortest paths" "hitting set" pairs NP-hard: status=200 count=442
   - Improved Results on Geometric Hitting Set Problems (2010) https://doi.org/10.1007/s00454-010-9285-9
   - Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs (2016) https://doi.org/10.48550/arxiv.1611.01210
   - Highway Dimension: a Metric View (2025) https://doi.org/10.1137/1.9781611978322.104
   - The Complexity of Blocking All Solutions (2025) https://doi.org/10.48550/arxiv.2502.05348
   - Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model (2026) https://doi.org/10.48550/arxiv.2609.37979
   - On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension (2022) https://doi.org/10.4230/lipics.ipec.2022.5
   - Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling (2019) https://doi.org/10.1137/1.9781611975499.11
   - Leveraging Path Structures in NP-hard Graph Problems (2022) None
   - Knapsack with Vertex Cover, Set Cover, and Hitting Set (2024) https://doi.org/10.4230/lipics.isaac.2024.27
   - Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems (2024) https://doi.org/10.4230/lipics.mfcs.2024.68
openalex search "most vital edges" "shortest path" "several pairs": status=200 count=0
openalex search "Krause" "increasing distances in graphs": status=200 count=0
openalex search "blocking shortest paths" Bienstock: status=200 count=1
   - Increasing distances in graphs (2006) https://doi.org/10.24355/dbbs.084-200605170200-19
openalex search shortest path "three pairs" NP-hard edges deletion distance: status=200 count=40
   - Parameterized Complexity of $$(A,\ell )$$-Path Packing (2021) https://doi.org/10.1007/s00453-021-00875-y
   - Separating Geodesic Structure and Product Structure (2026) https://doi.org/10.4230/lipics.esa.2026.126
   - Algorithms for the Maximum Independent Set Problem (2014) None
   - Novel Split-Based Approaches to Computing Phylogenetic Diversity and Planar Split Networks (2010) None
   - Problèmes de placement, de coloration et d’identification (2012) None
   - On packing, colouring and identification problems (2012) https://doi.org/10.70675/cf37e72cz10faz4c28zbadbz19dc67088546
   - Parameterized Complexity of $$(A,\ell )$$-Path Packing (2020) https://doi.org/10.1007/978-3-030-48966-3_4
   - Theoretical and Experimental Studies on the Minimum Size 2-edge-connected Spanning Subgraph Problem (2013) https://doi.org/10.20381/ruor-3017
   - Coalition Structure Generation over Graphs (2012) https://doi.org/10.1613/jair.3715
   - A survey of parameterized algorithms and the complexity of edge modification (2023) https://doi.org/10.1016/j.cosrev.2023.100556
=== D. Semantic Scholar retry (slow) ===
S2 search 'blocking shortest paths Krause': status=200 total=1762
   - Increasing distances in graphs (2006) cites=0 doi=None arxiv=None
   - A trainable clustering algorithm based on shortest paths from density peaks (2019) cites=42 doi=10.1126/sciadv.aax3770 arxiv=None
   - AnyDijkstra, an algorithm to compute shortest paths on images with anytime properties (2022) cites=0 doi=10.48550/arXiv.2210.15421 arxiv=2210.15421
   - Incremental Approximate Single-Source Shortest Paths with Predictions (2025) cites=8 doi=10.48550/arXiv.2502.08125 arxiv=2502.08125
   - Going Faster: Privacy-Preserving Shortest paths from Start to End (2025) cites=0 doi=None arxiv=None
   - Shortest Paths in a Weighted Simplicial Complex (2025) cites=1 doi=10.48550/arXiv.2506.12921 arxiv=2506.12921
   - New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes (2024) cites=2 doi=10.21122/2309-4923-2023-4-4-13 arxiv=None
   - Blocked algorithm of finding all-pairs shortest paths in graphs divided into weakly connected clusters (2024) cites=2 doi=10.21122/2309-4923-2024-2-4-10 arxiv=None
   - Competing all-pairs shortest paths algorithms for sparse / dense graphs: implementation and comparison (2024) cites=1 doi=10.21122/2309-4923-2024-4-4-12 arxiv=None
   - Discrete Shortest Paths in Optimal Power Flow Feasible Regions (2024) cites=1 doi=10.1109/TPWRS.2025.3581453 arxiv=2408.02172
S2 search 'shortest path blocking three terminals NP-hard': status=429 total=None
done
