The Minimum Length Bounded Cut problem is a natural variant of Minimum Cut: given a graph, terminal nodes s,t and a parameter L, find a minimum cardinality set of nodes (other than s,t) whose removal ensures that the distance from s to t is greater than L. We focus on the approximability of the problem for bounded values of the parameter L. The problem is solvable in polynomial time for L ≤ 4 and NP-hard for L ≥ 5. The best known algorithms have approximation factor ⌈ (L-1)/2⌉. It is NP-hard to approximate the problem within a factor of 1.17175 and Unique Games hard to approximate it within Ω(L), for any L ≥ 5. Moreover, for L = 5 the problem is 4/3-ε Unique Games hard for any ε > 0. Our first result matches the hardness for L = 5 with a 4/3-approximation algorithm for this case, improving over the previous 2-approximation. For 6-bounded cuts we give a 7/4-approximation, improving over the previous best 3-approximation. More generally, we achieve approximation ratios that always outperform the previous ⌈ (L-1)/2⌉ guarantee for any (fixed) value of L, while for large values of L, we achieve a significantly better ((11/25)L+O(1))-approximation. All our algorithms apply in the weighted setting, in both directed and undirected graphs, as well as for edge-cuts, which easily reduce to the node-cut variant. Moreover, by rounding the natural linear programming relaxation, our algorithms also bound the corresponding bounded-length flow-cut gaps.

Given a graph $G=(V,E)$ with two distinguished vertices $s,t\in V$ and an integer $L$, an $L$-bounded flow is a flow between $s$ and $t$ that can be decomposed into paths of length at most $L$. In the maximum $L$-bounded flow problem the task is to find a maximum $L$-bounded flow between a given pair of vertices in the input graph. For networks with unit edge lengths (or, more generally, with polynomially bounded edge lengths, with respect to the number of vertices), the problem can be solved in polynomial time using linear programming. However, as far as we know, no polynomial-time combinatorial algorithm1 for the $L$-bounded flow is known. For general edge lengths, the problem is NP-hard. The only attempt, that we are aware of, to describe a combinatorial algorithm for the maximum $L$-bounded flow problem was done by Koubek and Říha in 1981. Unfortunately, their paper contains substantial flaws and the algorithm does not work; in the first part of this paper, we describe these problems. In the second part of this paper we describe a combinatorial algorithm based on the exponential length method that finds a $(1+\varepsilon)$-approximation of the maximum $L$-bounded flow in time $\mathcal{O}(\varepsilon^{-2}m^2L\log L)$ where $m$ is the number of edges in the graph. Moreover, we show that this approach works even for the NP-hard generalization of the maximum $L$-bounded flow problem in which each edge has a length. 1Combinatorial in the sense that it does not explicitly use linear programming methods or methods from linear algebra or convex geometry.

An elementary h-route flow, for an integer h≥1, is a set of h edge-disjoint paths between a source and a sink, each path carrying a unit of flow, and an h-route flow is a non-negative linear combination of elementary h-route flows. An h-route cut is a set of edges whose removal decreases the maximum h-route flow between a given source-sink pair (or between every source-sink pair in the multicommodity setting) to zero. The main result of this paper is an approximate duality theorem for multicommodity h-route cuts and flows, for h≤3: The size of a minimum h-route cut is at least f/h and at most O(log4 k⋅f) where f is the size of the maximum h-route flow and k is the number of commodities. The main step towards the proof of this duality is the design and analysis of a polynomial-time approximation algorithm for the minimum h-route cut problem for h=3 that has an approximation ratio of O(log4 k). Previously, polylogarithmic approximation was known only for h-route cuts for h≤2. A key ingredient of our algorithm is a novel rounding technique that we call multilevel ball-growing. Though the proof of the duality relies on this algorithm, it is not a straightforward corollary of it as in the case of classical multicommodity flows and cuts. Similar results are shown also for the sparsest multiroute cut problem.

Given an integer h, a graph G = (V, E) with arbitrary positive edge capacities and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk), called terminals, an h-route cut is a set F ⊆ E of edges such that after the removal of the edges in F no pair si − ti is connected by h edge-disjoint paths (i.e., the connectivity of every si − ti pair is at most h − 1 in (V, E\F)). The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an O(h5 22h (h + log k)2)-approximation algorithm for the minimum h-route cut problem in the case that s1 = s2 = … = sk, called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

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.

In this paper we consider the k edge‐disjoint paths problem (k‐EDP), a generalization of the well‐known edge‐disjoint paths problem. Given a graph $G=(V,E)$ and a set of terminal pairs (or requests) T, the problem is to find a maximum subset of the pairs in T for which it is possible to select paths such that each pair is connected by k edge‐disjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for $k>1$. To measure the performance of our algorithms we use the recently introduced flow number F of a graph. This parameter is known to fulfill $F=O(\Delta \alpha^{-1} \log n)$, where $\Delta$ is the maximum degree, $\alpha$ is the edge expansion of G, and n is the number of vertices in G. We show that a simple greedy online algorithm achieves a competitive ratio of $O(k^3 F)$ which naturally extends the best known bound of $O(F)$ for $k=1$ to higher k. To achieve this competitive ratio, we introduce a new method of converting a system of k disjoint paths into a system of k length‐bounded disjoint paths. We also show that any deterministic online algorithm has a competitive ratio of $\Omega(k F)$. In addition, we study the k disjoint flows problem (k‐DFP), which is a generalization of the previously studied unsplittable flow problem. The difference between the k‐DFP and the k‐EDP is that now we consider a graph with edge capacities and our requests are allowed to have arbitrary demands $d_i$. The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand $d_i$ is connected by k disjoint paths, each of flow value $d_i/k$. The k‐EDP and k‐DFP problems have important applications in fault‐tolerant (virtual) circuit switching, which plays a key role in optical networks.

In the Minimum Common String Partition problem (MCSP), we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. This problem is NP-hard, even for a special case, denoted 2-MCSP, where each letter occurs at most twice in each input string. We study a greedy algorithm for MCSP that at each step extracts a longest common substring from the given strings. We show that the approximation ratio of this algorithm is between Ω( n 0.43 ) and O ( n 0.69 ). In the case of 2-MCSP, we show that the approximation ratio is equal to 3. For 4-MCSP, we give a lower bound of Ω(log n ).

We deal with a generalization of the Minimum path colouring problem, k-Edge disjoint path systems colouring: given a graph G and a set of pairs of vertices of G, the task is to connect each pair by a system of k-edge disjoint paths (a k-system) and to colour the k-systems by minimal number of colours in such way that any two edge-intersecting k-systems have different colours. Multiple connecting paths between the same pair of vertices are motivated by a need for fault tolerant connections. We propose an O(k2 F) approximation algorithm for this problem where F is the flow number of the graph. As a byproduct of our analysis we also show that any two k-connected vertices in G are connected by k edge disjoint paths of average length O(k F) which improves previously known bounds for many classes of graphs.

In this paper we consider the k edge-disjoint paths problem (k-EDP), a generalization of the well-known edge-disjoint paths problem. Given a graph G=(V,E) and a set of terminal pairs (or requests) T, the problem is to find a maximum subset of the pairs in T for which it is possible to select paths such that each pair is connected by k edge-disjoint paths and the paths for different pairs are mutually disjoint. To the best of our knowledge, no nontrivial result is known for this problem for k>1. To measure the performance of our algorithms we will use the recently introduced flow number F of a graph. This parameter is known to satisfy F=O(\Delta \alpha^-1 \log n), where \Delta is the maximum degree and \alpha is the edge expansion of G. We show that a simple, greedy online algorithm achieves a competitive ratio of O(k^3 \cdot F) which naturally extends the best known bound of O(F) for k=1 to higher $k$. To get this bound, we introduce a new method of converting a system of k disjoint paths into a system of k length-bounded disjoint paths. Also, an almost matching deterministic online lower bound \Omega(k \cdot F) is given.In addition, we study the k disjoint flows problem (k-DFP), which is a generalization of the well-known unsplittable flow problem (UFP). The k-DFP is similar to the k-EDP with the difference that we now consider a graph with edge capacities and the requests can have arbitrary demands d_i. The aim is to find a subset of requests of maximum total demand for which it is possible to select flow paths such that all the capacity constraints are maintained and each selected request with demand d_i is connected by k disjoint paths, each of flow value d_i/k.The k-EDP and k-DFP problems have important applications in fault-tolerant (virtual) circuit switching which plays a key role in optical networks.

In this paper we study the problem of finding disjoint paths in graphs. Whereas for specific graphs many (almost) matching upper and lower bounds are known for the competitiveness of on-line path selection algorithms, much less is known about how well on-line algorithms can perform in the general setting. In several papers the expansion has been used to measure the performance of off-line and on-line algorithms in this field. We study a class of simple deterministic on-line algorithms and show that they achieve a competitive ratio that is asymptotically equal to the best possible competitive ratio that can be achieved by any deterministic on-line algorithm. For this we use a parameter caled routing number which allows more precise results than the expansion. Interestingly, our upper bound on the competitive ratio is even better than the best approximation ratio known for off-line algorithms. Furthermore, we show that a refined variant of the routing number allows to construct on-line algorithms with a competitive ratio that is for many graphs significantly below the best possible upper bound for deterministic on-line algorithms if only the routing number or expansion of a graph is known. We also show that our algorithms can be transformed into efficient algorithms for the related unsplittable flow problem.