The network‐diversion problem (ND) is defined on a directedor undirected graph G = (V,E) having non‐negative edge weights, a source vertex s, a sink vertex t, and a “diversion edge” . This problem, with intelligence‐gathering and war‐fighting applications, seeks a minimum‐weight, minimal s‐t cut in G such that . We present (a) a new NP‐completeness proof for ND on directed graphs, (b) the first polynomial‐time solution algorithm for a special graph topology, (c) an improved mixed‐integer programming formulation (MIP), and (d) useful valid inequalities for that MIP. The proof strengthens known results by showing, for instance, that ND is strongly NP‐complete on a directed graph even when is incident from s or into t, but not both, and even when G is acyclic; a corollary shows the NP‐completeness of a vertex‐deletion version of ND on undirected graphs. The polynomial‐time algorithm solves ND on s‐t planar graphs. Compared to a MIP from the literature, the new MIP, coupled with valid inequalities, reduces the average duality gap by 10–50% on certain classes of test problems. It can also reduce solution times by an order of magnitude. We successfully solve unweighted problems with roughly 90,000 vertices and 360,000 edges and weighted problems with roughly 10,000 vertices and 40,000 edges. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 000(00), 000–000 2013

Abstract The constrained shortest‐path problem (CSPP) generalizes the standard shortest‐path problem by adding one or more path‐weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian function, identifies a feasible solution, and then closes any optimality gap by enumerating near‐shortest paths, measured with respect to the Lagrangianized length. “Near‐shortest” implies ε‐optimal, with a varying ε that equals the current optimality gap. The algorithm exploits a variety of techniques: a new path‐enumeration method; aggregated constraints; preprocessing to eliminate edges that cannot form part of an optimal solution; “reprocessing” that reapplies preprocessing steps as improved solutions are found; and, when needed, a “phase‐I procedure” to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state‐of‐the‐art label‐setting algorithm on singly constrained randomly generated grid networks. On multiconstrained grid networks, road networks, and networks for aircraft routing the advantage varies but, overall, the new algorithm is competitive with the label‐setting algorithm. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We describe a new algorithm for computing the efficient frontier of the “bi-objective maximum-flow network-interdiction problem.” In this problem, an “interdictor” seeks to interdict (destroy) a set of arcs in a capacitated network that are Pareto-optimal with respect to two objectives, minimizing total interdiction cost and minimizing maximum flow. The algorithm identifies these solutions through a sequence of single-objective problems solved using Lagrangian relaxation and a specialized branch-and-bound algorithm. The Lagrangian problems are simply max-flow min-cut problems, while the branch-and-bound procedure partially enumerates s-t cuts. Computational tests reveal the new algorithm to be one to two orders of magnitude faster than an algorithm that replaces the specialized branch-and-bound algorithm with a standard integer-programming solver.

We present a new algorithm for enumerating all near-shortest simple (loopless) s-t paths in a graph G = (V, E) with nonnegative edge lengths. Letting n = |V| and m = |E|, the time per path enumerated is O(nS(n, m)) given a user-selected shortest-path subroutine with complexity O(S(n, m)). When coupled with binary search, this algorithm solves the corresponding K-shortest paths problem (KSPR) in O(KnS(n, m)(log n+ log cmax)) time, where cmax is the largest edge length. This time complexity is inferior to some other algorithms, but the space complexity is the best available at O(m). Both algorithms are easy to describe, to implement and to extend to more general classes of graphs. In computational tests on grid and road networks, our best polynomial-time algorithm for KSPR appears to be at least an order of magnitude faster than the best algorithm from the literature. However, we devise a simpler algorithm, with exponential worst-case complexity, that is several orders of magnitude faster yet on those test problems. A minor variant on this algorithm also solves “KSPU,” which is analogous to KSPR but with loops allowed. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 98–109 2005

Abstract We study the problem of interdicting the arcs in a network in order to maximize the shortest s–t path length. “Interdiction” is an attack on an arc that destroys the arc or increases its effective length; there is a limited interdiction budget. We formulate this bilevel, max–min problem as a mixed‐integer program (MIP), which can be solved directly, but we develop more efficient decomposition algorithms. One algorithm enhances Benders decomposition by adding generalized integer cutting planes, called “supervalid inequalities” (SVIs), to the master problem. A second algorithm exploits a unique set‐covering master problem. Computational results demonstrate orders‐of‐magnitude improvements of the decomposition algorithms over direct solution of the MIP and show that SVIs also help solve the original MIP faster. Published 2002 Wiley Periodicals, Inc.

In an original and very interesting paper (Satyanarayana and Wood [1]) concerning polygon-to-chain reductions in a stochastic network, a small inconsistency occurs in the proof of Theorem 1. In particular, this happens in cases where the whole set of ${\bf K}$-vertices lies in the remaining polygon. Such an example is the case of polygon type 5, where the appropriate note has been made by the authors for $|{\bf K}| = 2$. Analogous notes must also be made for polygon types 4, 6, and 7, when ${\bf K} = 2,3$, and 4, respectively. The correct transformations are given in Table 1 (note that dark vertices are ${\bf K}$-vertices).

Abstract Let R(Gk) denote the probability that a subset of vertices K in the undirected graph G = (V, E) can communicate when the edge of G fail independently with known probabilities. Suppose that Gk contains as separting pair of vertices {u, v} such that Gk= G̃k̃ ∪ Ǧǩ, Ṽ ∩ V̂ ={u v}, Ẽ ∩ Ê = ø, |Ẽ| ⩾ 2, and |Ê| ⩾2. It is shown that Ĝk may be replaced by a chain χ of at most three edges between u and v such that R(Gk) = ΩR ((G̃ ∪ χ)k̃′) where Ω is a derived constant and K̃′ is defined by the procedure. The failure probabilities of the edges in χ and the value of Ω are shown to be computable by evaluating the reliability of one of four variants of Ĝk̂. Minimal components Ĝk̂ can be efficiently found using triconnected decomposition and the above procedure embedded within a recursive factoring algorithm for computing K‐terminal reliability. Conditions are derived which guarantee the new algorithm is at least as good as a pure factoring algorithm, and an example shows that the new algorithm can be exponentially better.

Abstract Let G = (V,E) be an undirected graph whose edges may fail, and let Gk denote G with a set k ⊆ V specified. Edge failures are assumed to be statistically independent and to have known probabilities. The k‐terminal reliability of Gk, denoted R(Gk), is the probability that all vertices in k are connected by working edges. Computing k‐terminal reliability is an NP‐hard problem not known to be in NP. A factoring algorithm for computing network reliability recursively applies the formula R(Gk) = PiR(Gk′*ei + qiR(Gk − ei)), where Gk′*ei is Gk with edge ei contracted, Gk − ei is Gk with ei deleted and pi = 1 − qi is the reliability of edge ei. Various reliability‐preserving reductions may be performed after each factoring operation in order to reduce computational complexity. The complexity of a slightly restricted factoring algorithm using standard reductions, along with newly developed polygon‐to‐chain reductions, will be bounded below by an invariant of G, the “minimum domination.” For 2 ≤ ∣K∣ ≤ 5 or ∣V∣ − 2 ≤ ∣K∣ ≤ ∣V∣, this bound is always achievable. The factoring algorithm with polygon‐to‐chain reductions will always perform as well as or better than an algorithm using only standard reductions, and for some networks, it will outperform the simpler algorithm by an exponential factor. This generalizes early results that were only valid for K = V. Removing the restriction on edge selection leaves results essentially unchanged in the upper range of ∣K∣, but minimum domination becomes only a tight upper bound for the lower range.

Let $G = (V,E)$ be a graph whose edges may fail with known probabilities and let $K \subseteq V$ be specified. The K-terminal reliability of G, denoted $R(G_K )$, is the probability that all vertices in K are connected. Computing $R(G_K )$ is, in general, NP-hard. For some series-parallel graphs, $R(G_K )$ can be computed in polynomial time by repeated application of well-known reliability-preserving reductions. However, for other series-parallel graphs, depending on the configuration of K, $R(G_K )$ cannot be computed in this way. Only exponential-time algorithms as used on general graphs were known for computing $R(G_K )$ for these “irreducible” series-parallel graphs. We prove that $R(G_K )$ is computable in polynomial time in the irreducible case, too. A new set of reliability-preserving “polygon-to-chain” reductions of general applicability is introduced which decreases the size of a graph, and conditions are given for a graph admitting such reductions. Combining all types of reductions, an $O(|E|)$ algorithm is presented for computing the reliability of any series-parallel graph irrespective of the vertices in K.