Length-bounded cuts and flows

TLDR

An L‑length‑bounded cut removes all s‑t paths of length ≤ L, while an L‑length‑bounded flow consists of paths of length ≤ L. We present approximation algorithms achieving O(min{L, n/L}) for node cuts (≤ O(√n)) and O(min{L, n²/L², √m}) for edge cuts (≤ O(n^{2/3})), and analyze optimal solution structure and additional complexity results. We show that the min L‑length‑bounded cut can be Θ(n^{2/3}) (node cuts) or Θ(√n) (edge cuts) times larger than the max flow, that approximating the cut within 1.1377 is NP‑hard for L≥5 (node) and L≥4 (edge), and that deciding the existence of a fractional length‑bounded flow in unit‑capacity graphs with arbitrary edge lengths is NP‑complete.

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.