ABSTRACT A deadlock occurs in a network when two or more items prevent each other from moving and are stalled. In a general model, items are stored at vertices and each vertex has a buffer with slots. Given a route for each item toward its destination, the Deadlock Safety Problem asks whether the current state is safe , that is, it is possible to deliver each item at its destination, or is bound to deadlock , that is, any sequence of moves will end up with a set of items stalled. While when the problem is solvable in polynomial time building upon a nice characterization of YES/NO‐instances, it is NP‐hard on quite simple graphs as grids when and on trees when . We improve on these results by means of two new tools, weak deadlock sets and wise states. We show that for general networks and a state that is wise and without weak deadlock sets—this can be recognized in polynomial time—is safe: this is indeed a strengthening of the result for . We sharpen this result for trees, where we show that a wise state is safe if and only if it has no weak deadlock set. That is interesting in particular in the context of rail transportation where networks are often single‐tracked and deadlock detection and avoidance focuses on local sub‐networks, mostly with a tree‐like structure. We pose some research questions for future investigations.

We introduce reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. An important new feature of this model, distinguishing it from existing robust network flow models, is that no flow can get lost in the network. Our goal is to compute maximum flows under this robustness requirement. We investigate different variants depending on the number of failing links, the capacities available for rerouting, and integrality requirements. While the most general versions of the model turn out to be $NP$-hard, we devise linear programming (LP) formulations and combinatorial algorithms for important special cases and provide approximation algorithms for the harder variants.

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O (| V |(| E | + | V | log| V |))-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present article. Despite being weaker than the structural results for claw-free graphs given by Chudnovsky and Seymour [2005, 2008a, 2008b] our decomposition theorem is, on the other hand, algorithmic, that is, it is coupled with an O (| V || E |)-time algorithm that actually produces the decomposition.

In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formulations and propose a new polytime algorithm for solving the separation problem for the stable set polytope of claw-free graphs. This routine combines a separation algorithm for the matching polytope due to Padberg and Rao and the solution of (moderate size) compact linear programs. Hence, it does not rely on the ellipsoid method and seems to be appropriate to be inserted in branch and cut frameworks for solving real world problems.

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which is also introduced in the present paper. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour [5], our decomposition theorem is, on the other hand, algorithmic, i.e. it is coupled with an O(n3)-time procedure that actually produces the decomposition. We also believe that our algorithmic decomposition result is interesting on its own and might be also useful to solve other kind of problems on claw-free graphs.

Only recently Goyal, Olver, and Shepherd [Proc. STOC, ACM, New York, 2008] proved that the symmetric virtual private network design (sVPN) problem has the tree routing property, namely, that there always exists an optimal solution to the problem whose support is a tree. Combining this with previous results by Fingerhut, Suri, and Turner [J. Algorithms, 24 (1997), pp. 287–309] and Gupta et al. [Proc. STOC, ACM, New York, 2001], sVPN can be solved in polynomial time. In this paper we investigate an APX-hard generalization of sVPN, where the contribution of each edge to the total cost is proportional to some non-negative, concave, and nondecreasing function of the capacity reservation. We show that the tree routing property extends to the new problem and give a constant-factor approximation algorithm for it. We also show that the undirected uncapacitated single-source minimum concave-cost flow problem has the tree routing property when the cost function has some property of symmetry.

Abstract The authors settle the complexity status of the robust network design problem in undirected graphs. The fact that the flow‐cut gap in general graphs can be large, poses some difficulty in establishing a hardness result. Instead, the authors introduce a single‐source version of the problem where the flow‐cut gap is known to be one. They then show that this restricted problem is coNP‐Hard. This version also captures, as special cases, the fractional relaxations of several problems including the spanning tree problem, the Steiner tree problem, and the shortest path problem. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 50–54 2007

Virtual private network design is the following NP-hard problem. We are given a communication network represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often elusive. The main contributions of this paper are as follows: (1) Using Hu's 2-commodity flow theorem, we provide a new and considerably stronger lower bound on the cost of an optimum solution. With this lower bound we reanalyze a simple routing scheme which has been described in the literature many times, and provide an improved upper bound on its approximation ratio. (2) We present a new randomized approximation algorithm. In contrast to earlier approaches from the literature, the resulting solution does not have tree structure. A combination of our new algorithm with the simple routing scheme yields an expected performance ratio of $3.79$ for virtual private network design. This is a considerable improvement of the previously best known $5.55$-approximation result [A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365–372]. (3) Our VPND algorithm uses a Steiner tree approximation algorithm as a subroutine. It is known that an optimum Steiner tree can be computed in polynomial time if the number of terminals is logarithmic. Replacing the approximate Steiner tree computation with an exact one whenever the number of terminals is sufficiently small, we finally reduce the approximation ratio to $3.55$. To the best of our knowledge, this is the first time that a nontrivial result from exact (exponential) algorithms leads to an improved polynomial-time approximation algorithm.

Abstract Continuing research begun in a previous study [SIAM J Discr Math 14 (2001), 524–539], we investigate problems of reserving capacity in the arcs of a network, subject to the constraint that, on the failure of any one arc, there is enough reserved capacity on the remaining arcs to support a flow of value T from a source s to a destination t . We also impose upper bounds on the amount of capacity we may reserve on the arcs: This alters the nature of the problem. In the case where each arc has the same upper bound, we investigate the strategy of finding the minimum‐cost reservation that is itself an acyclic ( s , t ) flow: We show that such a reservation is easy to find, always has a simple form, and has a cost at most twice that of the optimal solution. In the case where each arc has its own upper bound, we explain why no such results can hold, but we do give an efficient algorithm for the case where we are asked for a reservation on a fixed set of arc‐disjoint paths. We consider the case where we are free to reserve on each arc as much capacity as we want but only in bundles of fixed size. © 2003 Wiley Periodicals, Inc.

We examine various problems concerning the reservation of capacity in a given network, where each arc has a per-unit cost, so as to be "resilient" against one or more arc failures. For a given pair (s,t) of nodes and demand T, we require that, on the failure of any k arcs of the network, there is sufficient reserved capacity in the remainder of the network to support an (s,t) flow of value T. This problem can be solved in polynomial time for any fixed k, but we show that it is NP-hard if we are required to reserve an integer capacity on each arc. We concentrate on the case where the reservation has to consist of a collection of arc-disjoint paths: here we give a very simple algorithm to find a minimum cost fractional solution, based on finding successive shortest paths in the network. Unlike traditional network flow problems, the integral version is NP-hard: we do, however, give a polynomial time $\frac{15}{14}$-approximation algorithm in the case k=1 and show that this bound is best possible unless P = NP.