Optimal attack and reinforcement of a network

ABSTRACT

In a nonnegative edge-weighted network, the weight of an edge represents the effort required by an attacker to destroy the edge, and the attacker derives a benefit for each new component created by destroying edges. The attacker may want to minimize over subsets of edges the difference between (or the ratio of) the effort incurred and the benefit received. This idea leads to the definition of the “strength” of the network, a measure of the resistance of the network to such attacks. Efficient algorithms for the optimal attack problem, the problem of computing the strength, and the problem of finding a minimum cost “reinforcement” to achieve a desired strength are given. These problems are also solved for a different model, in which the attacker wants to separate vertices from a fixed central vertex.

REFERENCES

• 1: BROWN, J. R.The sharing problem. Oper. Res. 27 (1979), 324-340.
• 2: CHV,~TAL, V.Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973), 215-228.
• 3: CUNNINGHAM, W. H.Testing membership in matroid polyhedra. J. Comb. Theory B 36 (1984), 161-188.
• 4: CUNNINGHAM, W. H.Minimum cuts, modular functions, and matroid polyhedra. Networks 15 (1985), 205-215.
• 5: DINKELBACH, W. On nonlinear fractional programming. Management Sci. 13 (1967), 492-498.
• 6: EDMONDS, J.Minimum partition ofa matroid into independent subsets. J. Res. N.B.S. B69 (1965), 67-72.
• 7: EDMONDS, J.Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Applications, R. K. Guy, E. Milner, and N. Sauer, Eds. Gordon and Breach, New York, 1970, pp. 69-87.
• 8: FUJISHIGE, S.Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5 (1980), 186-196.
• 9: Michel Gondran , Michel Minoux , Steven Vajda, Graphs and algorithms, John Wiley & Sons, Inc., New York, NY, 1984
• 10: GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A.The ellipsoid method and its consequences in combinatorial optimization. Combinatorica I ( 1981 ), 169-- 197.
• 11: GUSFIELD, D.Connectivity and edge-disjoint spanning trees. Inf. Proc. Lett. 16 (1983), 87-89.
• 12: ITAI, A., AND RODEH, M.Scheduling transmissions in a network, preprint, 1983.
• 13: MEGIDDO, N. A good algorithm for lexicographically optimal flows in multiterminal networks. Bull. A.M.S. 83 (1977), 407-409.
• 14: NASH-WILLIAMS, C. ST. J. A.Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36 ( 1961 ), 445-450.
• 15: PADBERG, M. W., AND WOLSEY, L. A. Trees and cuts. Ann. Discrete Math. 17 (1983), 511-517.
• 16: PADBERG, M. W., AND WOLSEY, L. A.Fractional covers for forests and matchings. Math. Programming 29 (1984), 1-14.
• 17: PICARD, J.-C., AND QUEYRANNE, M.Selected applications of minimum cuts in networks. INFOR 20 (1982), 394-422.
• 18: SCHAIBLE, S. Fractional programming II. On Dinkelbach's algorithm. Management Sci. 22 (I 976), 868-873.
• 19: TARDOS, E.A strongly polynomial minimum cost circulation algorithm. Report 84356-OR, Universit/it Bonn, Bonn, West Germany, 1984.
• 20: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 21: TUTTE, W. T. On the problem of decomposing a graph into n connected factors. J. London Math. Soc. 36 ( 1961 ), 221-230.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory, Verification