Premium
Theoretical and computational advances for network diversion
Author(s) -
Cullenbine Christopher A.,
Wood R. Kevin,
Newman Alexandra M.
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21514
Subject(s) - combinatorics , vertex (graph theory) , mathematics , corollary , integer programming , discrete mathematics , undirected graph , neighbourhood (mathematics) , time complexity , directed graph , graph , computer science , algorithm , mathematical analysis
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”e ′ . This problem, with intelligence‐gathering and war‐fighting applications, seeks a minimum‐weight, minimal s ‐ t cutE C ⊆ E in G such thate ′ ∈ E C . 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 whene ′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