arXiv:1110.3546v5 [q-fin.RM] 9 Mar 2013

On the Computational Complexity of Measuring Global Stability of
Banking Networks∗
Piotr Berman
Department of Computer Science & Engineering
Pennsylvania State University
University Park, PA 16802
Email: berman@cse.psu.edu
Bhaskar DasGupta & Lakshmi Kaligounder
Department of Computer Science
University of Illinois at Chicago
Chicago, IL 60607-7053
Email: dasgupta@cs.uic.edu, lkalig2@uic.edu

Marek Karpinski
Department of Computer Science
University of Bonn
53117 Bonn, Germany
Email: marek@cs.uni-bonn.de

November 13, 2017

Abstract
Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable emphasis is placed on the analyzing the cause and effect of such threats. The
financial crisis in the current and past decade has shown that one important cause of instability in global
markets is the so-called financial contagion, namely the spreadings of instabilities or failures of individual components of the network to other, perhaps healthier, components. This leads to a natural question
of whether the regulatory authorities could have predicted and perhaps mitigated the current economic
crisis by effective computations of some stability measure of the banking networks. Motivated by such
observations, we consider the problem of defining and evaluating stabilities of both homogeneous and
heterogeneous banking networks against propagation of synchronous idiosyncratic shocks given to a
subset of banks. We formalize the homogeneous banking network model of Nier et al. [46] and its corresponding heterogeneous version, formalize the synchronous shock propagation procedures outlined
in [25, 46], define two appropriate stability measures and investigate the computational complexities of
evaluating these measures for various network topologies and parameters of interest. Our results and
proofs also shed some light on the properties of topologies and parameters of the network that may lead
to higher or lower stabilities.
∗ Talks based on these results were given or will be given at the 4th

annual New York Computer Science and Economics Day, New
York University, September 16, 2011, at the Industrial-Academic Workshop on Optimization in Finance and Risk Management,
October 3-4, 2011, Fields Institute, Toronto, Canada, and at the Mathematical Finance theme, 2012 Annual Meeting of the Canadian
Applied and Industrial Mathematics Society, July 24-28, 2012.

1

1 Introduction and Motivation
In market-based economies, financial systems perform important financial intermediation functions of borrowing from surplus units and lending to deficit units. Financial stability is the ability of the financial
systems to absorb shocks and perform its key functions, even in stressful situations. Threats on the stability of a financial system may severely affect the functioning of the entire economy, and thus considerable
emphasis is placed on the analyzing the cause and effect of such threats. The concept of instability of a
market-based financial system due to factors such as debt financing of investments can be traced back to
earlier works of the economists such as Irving Fisher [29] and John Keynes [37] during the 1930’s Great
Depression era. Subsequently, some economists such as Hyman Minsky [44] have argued that:
Such instabilities are inherent in many modern capitalist economies.
In this paper, we investigate systemic instabilities of the banking networks, an important component of
modern capitalist economies of many countries. The financial crisis in the current and past decade has shown
that an important component of instability in global financial markets is the so-called financial contagion,
namely the spreadings of instabilities or failures of individual components of the network to other, perhaps
healthier, components. The general topic of interest in this paper, motivated by the global economic crisis in
the current and the past decade, is the phenomenon of financial contagion in the context of banking networks,
and is related to the following natural extension of the question posed by Minsky and others:
• What is the true characterization of such instabilities of banking networks, i.e.,
– Are such instabilities systemic, e.g., caused by a repeal of Glass-Steagall act with subsequent
development of specific properties of banking networks that allowed a ripple effect [14]?
– Or, are such instabilities caused just by a few banks that were “too big to fail” and/or “a few
individually greedy executives” ?
To investigate these types of questions, one must first settle the following issues:
• What is the precise model of the banking network that is studied?
• How exactly failures of individual banks propagated through the network to other banks?
• What is an appropriate stability measure and what are the computational properties of such a measure?
As prior researchers such as Allen and Babus [1] pointed out,graph-theoretic concepts provide a conceptual
framework within which various patterns of connections between banks can be described and analyzed in a
meaningful way by modeling banking networks as a directed network in which nodes represent the banks
and the links represent the direct exposures between banks. Such a network-based approach to studying
financial systems is particularly important for assessing financial stability, and in capturing the externalities that the risk associated with a single or small group of institutions may create for the entire system.
Conceptually, links between banks have two opposing effects on contagion:
• More interbank links increase the opportunity for spreading failures to other banks [32]: when one
region of the network suffers from a crisis, another region also incurs a loss because their claims on
the troubled region fall in value and, if this spillover effect is strong enough, it can cause a crisis in
adjacent regions.
2

• More interbank links provide banks with a form of coinsurance against uncertain liquidity flows [2],
i.e., banks can insure against the liquidity shocks by exchanging deposits through links in the network.

2 The Banking Network Model
2.1 Rationale Behind the Model
As several prior researchers such as [1, 25, 39, 46] have already commented, graph-theoretic frameworks
may provide a powerful tool for analyzing stability of banking and other financial networks. We provide
and use a mathematically precise abstraction of a banking network model as outlined in [46] and elsewhere.
The same or very similar version of the graph-theoretic loss propagation model used in this paper has also
been extensively used by prior researchers in finance, economics and banking industry to study various
properties and research questions involving banking systems similar to what is studied in this paper (e.g.,
see [5, 19, 31, 45, 49], to name a few). As commented by researchers such as [5, 46]:
the modelling challenge in studying banking networks lies not so much in analyzing a model
that is flexible enough to represent all types of insolvency cascades, but in studying a model that
can mimic the empirical properties of these different types of networks.
A loss propagation model such as the one discussed here and elsewhere such as in [5, 19, 31, 45, 49] conceptualises the main characteristics of a financial system using network theory by relating the cascading
behavior of financial networks both to the local properties of the nodes and to the underlying topology of
the network, allowing us to vary continuously the key parameters of the network.

2.2 Homogeneous Networks: Balance Sheets and Parameters for Banks
We provide a precise abstraction of the model as outlined in [46] which builds up on the works of Eboli [25].
The network is modeled by a weighted directed graph G = (V, F) of n nodes and m directed edges, where
each node v ∈ V corresponds to a bank (Bankv ) and each directed edge (v, v′ ) ∈ F indicates that Bankv has
an agreement to lend money to Bank v′ . Let degin (v) and degout (v) denote the in-degree and the out-degree
of node v. The model has the following parameters:
E = total external asset,
I = total inter-bank exposure,
A = I + E = total asset
I
=
weight
of
edge
e
∈
F,
Φ = severity of shock (1 ≥ Φ > γ )
[0, 1] ∋ γ = percentage of equity to asset, w = w(e) = m

Now, we describe the balance sheet for a node v ∈ V (i.e., for Bankv )1 :
ιv
ev
av = ev + ιv

=
=
=
=

Assets
degout (v) × w = interbank asset
bv
E−∑v∈V (bv −ιv )
E
cv = γ × a v
(bv − ιv ) +
= (bv − ιv ) + n
n
dv
share of total external asset E
ℓ v = b v + cv + d v
bv + En = total asset
av = ℓv (balance sheet equation)

=
=
=
=

Liabilities
degin (v) × w = interbank borrowing
net worth (equity)
customer deposits
total liability

1 This model assumes that all the depositors are insured for their deposits, e.g., in United States the Federal Deposit Insurance
Corporation provides such an insurance up to a maximum level. Thus, we will omit the parameters dv for all v in the rest of the
paper when using the model. Similarly, ℓv quantities (which depend on the dv ’s) are also only necessary in writing the balance
sheet equation and will not be used subsequently.

3

Note that the homogeneous model is completely described by the 4-tuple of parameters h G, γ , I, Eii.

2.3 Balance Sheets and Parameters for Heterogeneous Networks
The heterogeneous version of the model is the same as its’ homogeneous counterpart as described above, except that the shares of interbank exposures and external assets for different banks may be different. Formally,
the following modifications are done in the homogeneous model:
• w(e) > 0 denotes the weight of the edge e ∈ E along with the constraint that ∑e∈F w(e) = I.

• ιv = ∑e=(v,v′ )∈F w(e), and bv = ∑e=(v′ ,v)∈F w(e).

• ev = (bv − ιv ) + αv × E − ∑v∈V (bv − ιv ) for some αv > 0 along with the constraint ∑v∈V αv = 1.
Since ∑v∈V (bv − ιv ) = 0, this gives ev = (bv − ιv) + αv E. Consequently, av now equals bv + αv E.
Denoting the m-dimensional vector of w(e)’s by w and the n-dimensional vector of αv ’s by α , the heterogeneous model is completely described by the 6-tuple of parameters h G, γ , I, E, w, α i .
v2

v4

v1

v3

Figure 1: An example of our banking network model.
n = number of nodes = 5
v5 m = number of edges = 7
I = total inter-bank exposure = m = 7
E = total external asset = 14, γ = 0.1

Illustration of calculations of balance sheet parameters We illustrate the calculation of relevant parameters of the balance sheet of banks for the simple banking network shown in Fig. 1.
(a) Homogeneous version of the network
• w = weight of every edge = I/m = 1.
• ιv1 = degout (v1 ) × w = 1, ιv2 = degout (v2 ) × w = 1, ιv3 = degout (v3 ) × w = 2, ιv4 = degout (v4 ) × w =
1, ιv5 = degout (v5 ) × w = 2.
• bv1 = degin (v1 ) × w = 2, bv2 = degin (v2 ) × w = 1, bv3 = degin (v3 ) × w = 1, bv4 = degin (v4 ) × w =
3, bv5 = degin (v5 ) × w = 0.
• ev1 = bv1 − ιv1 + En = 3.8, ev2 = bv2 − ιv2 + En = 2.8, ev3 = bv3 − ιv3 + En = 1.8, ev4 = bv4 − ιv4 + En =
4.8, ev5 = bv5 − ιv5 + En = 0.8.
• av1 = bv1 + En = 4.8, av2 = bv2 + En = 3.8, av3 = bv3 + En = 3.8, av4 = bv4 + En = 5.8, av5 = bv5 + En = 2.8.
• cv1 = γ av1 = 0.48, cv2 = γ av2 = 0.38, cv3 = γ av3 = 0.38, cv4 = γ av4 = 0.58, cv5 = γ av5 == 0.28.

4

(b) Heterogeneous version of the network
Suppose that 95% of E is distributed equally on the two banks v1 and v2 , and the rest 5% of E is
distributed equally on the remaining three banks. Thus:
E
0.95 E
0.05 E
0.05 E
0.05 E
αv1 E = 0.95
2 = 6.65, αv2 E = 2 = 6.65, αv3 E = 3 ≈ 0.233, αv4 E = 3 ≈ 0.233, αv5 E = 3 ≈ 0.233

Suppose that 95% of I is distributed equally on the three edges f1 = (v2 , v1 ), f2 = (v1 , v4 ), f3 = (v4 , v2 ), and
the remaining 5% of I is distributed equally on the remaining four edges f4 = (v3 , v1 ), f5 = (v3 , v4 ), f6 =
(v5 , v4 ), f7 = (v5 , v3 ). Then,
w( f1 ) = w( f2 ) = w( f3 ) =
for bank v1 :
for bank v2 :
for bank v3 :
for bank v4 :
for bank v5 :

0.95 I
3

≈ 2.216, w( f4 ) = w( f5 ) = w( f6 ) = w( f7 ) =

0.05 I
4

= 0.08725

bv1 = w( f1 ) + w( f4 ) ≈ 2.30325, ιv1 = w( f2 ) = 2.216
ev1 = (bv1 − ιv1 ) + αv1 E ≈ 6.7365, av1 = bv1 + αv1 E = 8.9525, cv1 = γ av1 = 0.8925
bv2 = w( f3 ) ≈ 2.216, ιv2 = w( f1 ) ≈ 2.216
ev2 = (bv2 − ιv2 ) + αv2 E = 6.65, av2 = bv2 + αv2 E ≈ 8.866, cv2 = γ av2 ≈ 0.8666

bv3 = w( f7 ) = 0.08725, ιv3 = w( f4 ) + w( f5 ) = 0.1745
ev3 = (bv3 − ιv3 ) + αv3 E ≈ 0.14575, av3 = bv3 + αv3 E ≈ 0.32025, cv3 = γ av3 ≈ 0.032035
bv4 = w( f2 ) + w( f5 ) + w( f6 ) ≈ 2.39050, ιv4 = w( f3 ) ≈ 2.216
ev4 = (bv4 − ιv4 ) + αv4 E ≈ 0.4075, av4 = bv4 + αv4 E ≈ 2.6235, cv4 = γ av4 ≈ 0.26235

bv5 = 0, ιv5 = w( f6 ) + w( f7 ) = 0.1745
ev5 = (bv5 − ιv5 ) + αv5 E ≈ 0.0585, av5 = bv5 + αv5 E ≈ 0.233, cv5 = γ av5 ≈ 0.0233

2.4 Idiosyncratic Shock [25, 46]
As in [46], our initial failures are caused by idiosyncratic shocks which can occur due to operations risks
(frauds) or credit risks, and has the effect of reducing the external assets of a selected subset of banks
perhaps causing them to default. While aggregated or correlated shocks affecting all banks simultaneously
is relevant in practice, idiosyncratic shocks are a cleaner way to study the stability of the topology of the
banking network. Formally, we select a non-empty subset of nodes (banks) 0/ ⊂ Vshock ⊆ V . For all nodes
v ∈ Vshock , we simultaneously decrease their external assets from ev by sv = Φ ev , where the parameter Φ ∈
(0, 1] determines the “severity” of the shock. As a result, the new net worth of Bankv becomes c′v = cv − sv .
The effect of this shock is as follows:
• If c′v ≥ 0, Bankv continues to operate but with a lower net worth of c′v .
• If c′v < 0, Bankv defaults (i.e., stops functioning).

2.5 Propagation of an Idiosyncratic Shock [25, 46]
We use the notation cv (t) to denote cv at time t, and t0+ to denote any t > t0 . Let Valive (t) ⊆ V be the set
of nodes that have not failed at time t and let Galive (t) = (Valive (t), Falive (t)) be the corresponding nodeinduced subgraph of G at time t with degin (v,t) and degout (v,t) denote the in-degree and out-degree of a
node v ∈ Valive (t) in the graph Galive (t). In a continuous-time model, the shock propagates as follows:
5

t = 1 ; Valive (1) = V
(* start the shock at t = 1 on nodes in Vshock *)
∀ v ∈ V : if v ∈ Vshock then cv (1) = cv − Φ ev else cv (1) = cv
(* shock propagation at times t = 2, 3, . . . , T *)
V
while (t ≤ T )
(Valive (t) , 0)
/ do
(* transmit loss to next time step *)

∑

∀ u ∈ Valive (t) : cu (t + 1) = cu (t) −

min

v: cv (t )<0 & (u,v)∈Falive (t )



cv (t) , bv
degin (v, t)

(* remove Bankv from network if it is to fail at this step *)

Valive (t + 1) = Valive (t) \ v v ∈ Valive (t) & cv (t) < 0

t = t +1
endwhile

Table 1: Discrete-time idiosyncratic shock propagation for T steps.
• Valive (1) = V , cv (1) = cv − sv if v ∈ Vshock , and cv (1) = cv otherwise.
• If a banks equity ever becomes negative, it fails subsequently, i.e., ∀t0 ≥ 1 : cv (t0 ) < 0 ⇒ v < Valive (t0+ ).
• A failed bank Bankv at time t = t0 affects the net worth (equity) of all banks that gave loan to Bankv
in the following manner. For each edge (u, v) ∈ Falive (t0 ) in the network at time t0 , the equity cu (t0 ) is
| cv (t0 ) |, bv }
. Thus, the shock propagation is defined by the following
decreased by an amount2 of min{deg
in (v,t0 )
differential equation:

min cv (t) , bv
∂ cu (t)
=−
∀t ≥ 1 ∀ u ∈ Valive (t) :
∑
∂t
degin (v, t)
v: c (t)<0 & (u,v)∈F (t)
v

alive

An intuitive explanation of the two quantities inside the summation in the above equation is as follows. The
|cv (t)|
term deg
(v,t) distributes the loss of equity of a bank equitably among its creditors that have not failed yet.
in

The term deg bv(v,t) ensures that the total loss propagated is no more than the total interbank exposure of the
in
failed bank.
A discrete-time version of the above can be obtained by the obvious method of quantizing time and
replacing the partial differential equations by “difference equations”. With appropriate normalizations, the
discrete-time model for shock propagation is described by a synchronous iterative procedure shown in Table 1 where t = 1, 2, . . . , T denotes the discrete time step at which the synchronous update is done (T ≤ n).
2 If

| cv (t0 ) | > bv then the depositors incur a loss of bv − | cv (t0 ) |, but as already mentioned before this model assumes that all
the depositors are insured for their deposits.

6

A simplified illustration of the effect of idiosyncratic shocks Consider the
case when the model is homogeneous and the topology of the graph G is inarborescence, i.e., a directed rooted tree where all edges are oriented towards
the root. Consider two nodes u, v ∈ V such that (v, u) ∈ F and degin (v) = 0 (see
Fig. 2). Suppose that at time t = 1 the node u is shocked and consequently it
defaults. The amount of shock transmitted from u to v is

u




min {|c′u (1)|, bu } min {Φeu − cu (1), bu } min Φ bu − ιu + En − γ bu + En , bu
=
=
Figure 2:
An
∆=
degin (u)
degin (u)
degin (u)



arborescence
graph.
min Φ degin (u) − 1 + En − γ degin (u) + En , degin (u)
=
degin (u)




1
E
= min (Φ − γ ) × 1 +
,1
−
n degin (u)
degin (u)

v

in-

Since cv (1) = γ × E/n, we have




E
E
1
cv (2) = cv (1) − ∆ = γ × − min (Φ − γ ) × 1 +
,1
−
n
n degin (u)
degin (u)
Assuming Φ − γ ≪ 1 + n degE

in (u)

and degin (u) ≫ 1, the above expression simplifies to



E
E
cv (2) ≈ γ × − (Φ − γ ) × 1 +
n
n degin (u)


3E
Suppose that γ = Φ/4. Then, cv (2) ≈ γ × En − 3 − n deg
(u) . Consequently, one can observe the following:
in

• If E/n ≤ 2, then cv (2) < 0 and node v will surely fail at time t = 2.

• If E/n ≥ 4 and degin (u) > 10 then cv (2) > 0 and node v will surely not fail at time t = 2.

2.6 Parameter Simplification
We can assume without loss of generality that in the homogeneous shock propagation model w = 1. To
observe this, if w = I/m , 1, then we can divide each of the quantities ιv , bv , E and dv by w; it is easy to see
that the outcome of the shock propagation procedure in Table 1 remains the same. Moreover, we will ignore
the balance sheet equation since dv has no effect in shock propagation.

3 Related Prior Works on Financial Networks
Although there is a large amount of literature on stability of financial systems in general and banking systems
in particular, much of the prior research is on the empirical side or applicable to small-size networks. Two
main categories of prior researches can be summarized as follows. The particular model used in this paper
is the model of Nier et al. [46]. As stated before, definition of a precise stability measure and analysis of its
computational complexity issues for stability calculation were not provided for these models before.

7

Network formation Babus [7] proposed a model in which banks form links with each other as an insurance mechanism to reduce the risk of contagion. In contrast, Castiglionesi and Navarro [15] studied
decentralization of the network of banks that is optimal from the perspective of a social planner. In a setting
in which banks invest on behalf of depositors and there are positive network externalities on the investment
returns, fragility arises when “not sufficiently capitalized” banks gamble with depositors’ money. When the
probability of bankruptcy is low, the decentralized solution well-approximates the first objective of Babus.
Contagion spread in networks Although ordinarily one would expect the risk of contagion to be larger in
a highly interconnected banking system, some empirical simulations indicate that shocks have an extremely
complex effect on the network stability in the sense that higher connectivity among banks may sometimes
lead to lower risk of contagion.
Allen and Gale [2] studied how a banking system may respond to contagion when banks are connected
under different network structures, and found that, in a setting where consumers have the liquidity preferences as introduced by Diamond and Dybvig [23] and have random liquidity needs, banks perfectly insure
against liquidity fluctuations by exchanging interbank deposits, but the connections created by swapping deposits expose the entire system to contagion. Allen and Gale concluded that incomplete networks are more
prone to contagion than networks with maximum connectivity since better-connected networks are more
resilient via transfer of proportion of the losses in one bank’s portfolio to more banks through interbank
agreements. Freixas et al. [30] explored the case of banks that face liquidity fluctuations due to the uncertainty about consumers withdrawing funds. Gai and Kapadia [32] argued that the higher is the connectivity
among banks the more will be the contagion effect during crisis. Haldane [34] suggested that contagion
should be measured based on the interconnectedness of each institution within the financial system. Liedorp
et al. [42] investigated if interconnectedness in the interbank market is a channel through which banks affect
each others riskiness, and argued that both large lending and borrowing shares in interbank markets increase
the riskiness of banks active in the dutch banking market.
Dasgupta [21] explored how linkages between banks, represented by cross-holding of deposits, can
be a source of contagious breakdowns by investigating how depositors, who receive a private signal about
fundamentals of banks, may want to withdraw their deposits if they believe that enough other depositors will
do the same. Lagunoff and Schreft [41] considered a model in which agents are linked in the sense that the
return on an agents’ portfolio depends on the portfolio allocations of other agents. Iazzetta and Manna [35]
used network topology analysis on monthly data on deposits exchange to gain more insight into the way a
liquidity crisis spreads. Nier et al. [46] explored the dependency of systemic risks on the structure of the
banking system via network theoretic approach and the resilience of such a system to contagious defaults.
Kleindorfer et al. [39] argued that network analyses can play a crucial role in understanding many important
phenomena in finance. Corbo and Demange [20] explored, given the exogenous default of set of banks, the
relationship of the structure of interbank connections to the contagion risk of defaults. Babus [8] studied
how the trade-off between the benefits and the costs of being linked changes depending on the network
structure, and observed that, when the network is maximal, liquidity can be redistributed in the system to
make the risk of contagion minimal.

8

4 The Stability and Dual Stability Indices
A banking network is called dead if all the banks in the network have failed. Consider a given homogeneous
or heterogeneous banking network h G, γ , I, E, Φii or h G, γ , I, E, Φ, w, α i. For 0/ ⊂ V ′ ⊆ V , let
infl(V ′ ) = v ∈ V v fails if all nodes in V ′ are shocked



SI(G,V ′ , T ) =

The Stability Index

(

/n , if infl(V ′ ) = V
∞,
otherwise

V′

The optimal stability index of a network G is defined as
SI∗ (G, T ) = SI(G,Vshock , T ) = min
SI(G,V ′ , T )
′
V



For estimation of this measure, we assume that it is possible for the network to fail, i.e., SI∗ (G, T ) < ∞. Thus,
0 < SI∗ (G, T ) ≤ 1, and the higher the stability index is, the better is the stability of the network against an
idiosyncratic shock. We thus arrive at the natural computational problem S TABT,Φ . We denote an optimal
subset of nodes that is a solution of Problem S TABT,Φ by Vshock , i.e., SI∗ (G, T ) = SI(G,Vshock , T ). Note that
if T ≥ n then the S TABT,Φ finds a minimum subset of nodes which, when shocked, will eventually cause the
death of the network in an arbitrary number of time steps.
Input: a banking network with shocking parameter Φ,
and an integer T > 1
Valid solution: A subset V ′ ⊆ V such that SI(G,V ′ , T ) < ∞
Objective: minimize |V ′ |

Input: a banking network with shocking parameter Φ,
and two integers T, κ > 1
Valid solution: A subset V ′ ⊆ V such that |V ′ | = κ
Objective: maximize infl(V ′ )/κ

Stability of banking network ( S TABT,Φ )

Dual Stability of banking network ( D UAL -S TABT,Φ,κ )

The Dual Stability Index Many covering-type minimization problems in combinatorics have a natural
maximization dual in which one fixes a-priori the number of covering sets and then finds a maximum number
of elements that can be covered with these many sets. For example, the usual dual of the minimum set
covering problem is the maximum coverage problem [38]. Analogously, we define a dual stability problem
D UAL -S TABT,Φ,κ . The dual stability index of a network G can then be defined as
DSI∗ (G, T, κ ) =

max

V ′ ⊆V : |V ′ |=κ

infl(V ′ ) / κ

The dual stability measure is of particular interest when SI∗ (G, T ) = ∞, i.e., the entire network cannot be
made to fail. In this case, a natural goal is to find out if a significant portion of the nodes in the network can
be failed by shocking a limited number of nodes of G; this is captured by the definition of DSI∗ (G, T, κ ).
Violent Death vs. Slow Poisoning

In our results, we distinguish two cases of death of a network:

violent death (T = 2) The network is dead by the very next step after the shock.
slow poisoning (any T ≥ 2) The network may not be dead immediately but dies eventually.

9

4.1 Rationale Behind the Stability Measures
Although it is possible to think of many other alternate measures of stability for networks than the ones
defined in this paper, the measures introduced here are in tune with the ideas that references [25, 46] directly
(and, some other references such as [31, 49] implicitly) used to empirically study their networks by shocking
only a few (sometimes one) node. Thus, a rationale in defining the stability measures in the above manner
is to follow the cue provided by other researchers in the banking industry in studying models such as in
this paper instead of creating a completely new measure that may be out of sync with ideas used by prior
researchers and therefore could be subject to criticisms.

5 Comparison with Other Models for Attribute Propagation in Networks
Models for propagation of beneficial or harmful attributes have been invesa
d
tigated in the past in several other contexts such as influence maximization
c
in social networks [13, 16, 17, 36], disease spreading in urban networks
e
b
[18, 26, 27], percolation models in physics and mathematics [48] and other
Φ = 0.4 γ = 0.1 E = 5
types of contagion spreads [11, 12]. However, the model for shock propagation in financial network discussed in this paper is fundamentally very Figure 3: A homogeneous netdifferent from all these models. For example, the cascade models of fail- work used in the discussion in
ure considered in [11, 12] are probabilistic models of failure propagation Section 5.
of a more generic nature, and thus not very useful to study failure propagation via interlocked balance sheets
of financial institutions (as is the case in OTC derivatives markets). Some distinguishing features of our
model include:
(a) Almost all of these models include a trivial solution in which the attribute spreads to the entire network
if we inject each node individually with the attribute. This is not the case with our model: a node may not
fail when shocked, and the network may not be dead if all nodes are shocked. For example, consider the
network in Fig. 3(i).
• Suppose that all the nodes are shocked. Then, the following events happen.


– Node a (and similarly node b) fails at t = 1 since Φ degin (a) + E5 > γ degin (a) + E5 .


– Node c also fails at t = 1 since Φ degin (c) − degout (c) + E5 = 0.4 > γ degin (c) + E5 = 0.3.

– Node d (and similarly node e) do not fail at t = 1 since Φ −degout (d) + E5 = 0 < γ × E5 = 0.1
and its equity stays at 0.1 − 0 = 0.1.

– At t = 2, node d (and similarly node e) receives a shock from node c of the amount 0.4−0.3
=
2
0.05 < 0.1. Thus, nodes d and e do not fail. Since no new nodes fail during t > 2, the network
does not become dead.

• However, suppose that only nodes a and b are shocked. Then, the following events happen.


– Node a (and similarly node b) fails at t = 1 since Φ degin (a) + E5 =0.8 > γ degin (a) + E5 =0.2.

– At t = 2, node c receives a shock of the amount 2 × (0.8 − 0.2) = 1.2 > γ degin (c) + E5 = 0.3.
Thus, node c fails at t = 2.

10

= 0.45 > γ × E5 =
– At t = 3, node d (and similarly node e) receives a shock of the amount 1.2−0.3
2
0.1. Thus, both these nodes fail at t = 3 and the entire network is dead.
As the above example shows, if shocking a subset of nodes makes a network dead, adding more nodes to this
subset may not necessarily lead to the death of the network, and the stability measure is neither monotone
nor sub-modular. Similarly, it is also possible to exhibit banking networks such that to make the entire
network fail:
• it may be necessary to shock a node even if it does not fail since shocking such a node “weakens” it
by decreasing its equity, and
• it may be necessary to shock a node even if it fails due to shocks given to other nodes.
(b) The complexity of the computational aspects of many previous attribute propagation models arise due
to the presence of cycles in the graph; for example, see [16] for polynomial-time solutions of some of these
problems when the underlying graph does not have a cycle. In contrast, our computational problems are
may be hard even when the given graph is acyclic; instead, a key component of computational complexity
arises due to two or more directed paths sharing a node.
Stability SI∗ (G, T )
bound, assumption (if any),
corresponding theorem

Network type,
result type
T=2
approximation hardness
Homogeneous

T = 2, approximation ratio

(1 − ε ) ln n,


NP * DTIME nlog log n , Theorem 8.1

 
O log

nΦE
γ (Φ − γ ) |E − Φ|


, Theorem 9.1

Acyclic, ∀ T > 1,
approximation hardness

APX-hard, Theorem 10.1

In-arborescence,
∀ T > 1, exact solution


O n2 time, every node fails
when shocked, Theorem 11.1

Acyclic, ∀ T > 1,
approximation hardness


(1 − ε ) ln n, NP * DTIME nlog log n ,
Theorem 12.1

Acyclic, T = 2, approximation hardness
Heterogeneous

Acyclic, ∀ T > 3,
approximation hardness
Acyclic, T = 2,
approximation ratio ‡

Dual Stability DSI∗ (G, T, κ )
bound, assumption (if any),
corresponding theorem

2

log1−ε n


1 − e −1 + ε −1 ,
P , NP, Theorem 15.1(a)

O n3 time, every node fails
when shocked, Theorem 15.1(b)
−1
,
1 − e −1 + ε
P , NP, Theorem 15.1(a)

nδ , assumption (⋆)† , Theorem 16.1

, NP * DTIME(n poly(log n) ),
Theorem 14.1


n E wmax wmin αmax
,
Φ γ (Φ − γ ) E wmin αmin wmax
Theorem 13.1

O log

‡ See

Theorem 13.1 for definitions of some parameters in the approximation ratio.
page 43 for statement of assumption (⋆), which is weaker than the assumption P , NP.
Table 2: A summary of our results; ε > 0 is any arbitrary constant and 0 < δ < 1 is some constant.
† See

6 Overview of Our Results and Their Implications on Banking Networks
Table 2 summarizes our results, where the notation poly (x1 , x2 , . . . , xk ) denotes a constant-degree polynomial
in variables x1 , x2 , . . . , xk . Our results for heterogeneous networks show that the problem of computing
stability indices for them is harder than that for homogeneous networks, as one would naturally expect.
11

6.1 Brief Overview of Proof Techniques
6.1.1

Homogeneous Networks, S TABT,Φ

T = 22, approximation hardness and approximation algorithm The reduction for approximation hardness is from a corresponding inapproximability result for the dominating set problem for graphs. The logarithmic approximation almost matches the lower bound. Even though this algorithmic problem can be cast
as a covering problem, one cannot explicitly enumerate exponentially many covering sets in polynomial
time. Instead, we reformulate the problem to that of computing an optimal solution of a polynomial-size
integer linear programming (ILP), and then use the greedy approach of [24] for approximation. A careful
calculation of the size of the coefficients of the ILP ensures that we have the desired approximation bound.
Any T > 11, approximation hardness and exact algorithm The APX-hardness result, which holds even
if the degrees of all nodes are small constants, is via a reduction from the node cover problem for 3-regular
graphs. Technical complications in the reduction arise from making sure that the generated graph instance
of S TABT,Φ is acyclic, no new nodes fail for any t > 3, but the network can be dead without each node being
individually shocked. If the network is a rooted in-arborescence and every node can be individually shocked

to fail, then we design an O n2 time exact algorithm via dynamic programming; as a by product it also
follows that the value of the stability index of this kind of network with bounded node degrees is large.
6.1.2

Homogeneous Networks, D UAL -S TABT,Φ,κ

Any T , approximation hardness and exact algorithm For hardness, we translate a lower bound for
the maximum coverage problem [28]. The reduction relies on the fact that in dual stability measure every
node of the network need not fail. If the given graph is a rooted in-arborescence and every node can be

individually shocked to fail, we provide an O n3 time exact algorithm via dynamic programming.
6.1.3

Heterogeneous Networks, S TABT,Φ

Any T , approximation hardness The reduction is from a corresponding inapproximability result for the
minimum set covering problem. Unlike homogeneous networks, unequal shares of the total external assets
by various banks allows us to encode an instance of set cover by “equalizing” effects of nodes.
T = 2 The approximation algorithm uses linear program in Theorem 9.1 with more careful calculations.
Any T > 22, approximation hardness This stronger poly-logarithmic inapproximability result than that in
Theorem 12.1 is obtained by a reduction from M INREP, a graph-theoretic abstraction of two prover multiround protocol for any problem in NP. Many technical complications in the reduction, culminating to a set
of 22 symbolic linear equations between the parameters that we must satisfy. Intuitively, the two provers in
M INREP correspond to two nodes in the network that cooperate to fail to another specified set of nodes.
approximation hardness The reduction for this
6.1.4 Heterogeneous Networks, D UAL -S TAB2,Φ,κ ,
stronger inapproximability result is from the densest hyper-graph problem.

12

6.2 Implications of Our Results on Banking Networks
6.2.1

Effects of Topological Connectivity

Though researchers agree that the connectivity of banking networks affects its stability [2, 32], the conclusions drawn are mixed, namely some researchers conclude that lesser connectivity implies more susceptibility to contagion whereas other researchers conclude in the opposite. Based on our results and their proofs,
we found that topological connectivity does play a significant role in stability of the network in the following
complex manner.
Even acyclic networks display complex stability behavior: Sometimes a cause of the instability of
a banking network is attributed to cyclical dependencies of borrowing and lending mechanisms among
major banks, e.g., banks v1 , v2 and v3 borrowing from banks v2 , v3 and v1 , respectively. Our results
show that computing the stability measures may be difficult even without the presence of such cycles.
Indeed, larger inapproximability results, especially for heterogeneous networks, are possible because
slight change in network parameters can cause a large change in the stability measure. On the other hand,
acyclic small-degree rooted in-arborescence networks exhibit higher values of the stability measure, e.g.,
if the maximum in-degree of any node in a rooted in-arborescence is 5 and the shock parameter Φ is no
more than twice the value of the percentage of equity to assets γ , then by Theorem 11.1 SI∗ (G, T ) > 0.1.
Intersection of borrowing chains may cause lower stability: By a borrowing chain we mean a directed
path from a node v1 to another node v2 , indicating that bank v2 effectively borrowed from bank v1 through
a sequence of successive intermediaries. Now, assume that there is another directed path from v1 to
another node v3 . Then, failure of v2 and v3 propagates the resulting shocks to v1 and, if the shocks arrive
at the same step, then the total shock received by bank v1 is the addition of these two shocks, which in
turn passes this “amplified” shock to other nodes in the network.
Based on these kinds of observations, it can be reasonably inferred that homogeneous networks with topologies more like a small-degree in-arborescence have higher stabilities, whereas networks of other types of
topologies may have lower stabilities even if the topologies are acyclic. For example, as we observe later,
∗
when degmax
in = 3, γ = 0.1 and Φ = 0.15, we get SI (G, T ) > 0.22 and the network cannot be put to death
without shocking more than 22% of the nodes.
6.2.2

Effects of Ratio of External to Internal Assets (E/I) and percentage of equity to assets (γ ) for
Homogeneous Networks

As our relevant results and their proofs show, lower values of E/I and γ may cause the network stability to be
extremely sensitive with respect to variations of other parameters of a homogeneous network. For example,
in the proof of Theorem 8.1 we have limn→∞ E/I = limn→∞ γ = 0, leading to variation of the stability index
by a logarithmic factor; however, in the proof of Theorem 10.1 we have E/I = 0.25 and γ = 0.23 leading to
much smaller variation of the stability index.
6.2.3

Homogeneous vs. Heterogeneous Networks

Our results and proofs show that heterogeneous networks of banks with diverse equities tend to exhibit wider
fluctuations of the stability index with respect to parameters, e.g., Theorem 14.1 shows a polylogarithmic
fluctuation even if the ratio E/I is large.
13

6.2.4

Further Empirical Study

Subsequent to writing this paper, DasGupta and Kaligounder in a separate article [22] performed a thorough
empirical analysis of the stability measure over more than 700000 combinations of networks types and
parameters, and uncovered many interesting insights into the relationships of the stability with other relevant
parameters of the network, such as:
Effect of uneven distribution of assets: Networks where all banks have roughly the same external assets
are more stable over similar networks in which fewer banks have a disproportionately higher external
assets compared to the remaining banks, and failures of those banks with higher assets contribute
more damage to the stability of the network. Furthermore, networks in which fewer banks have a
disproportionately higher external assets compared to the remaining banks has a minimal instability
even if their equity to asset ratio is large and comparable to loss of external assets. This is not the
case for networks where all banks have roughly the same external assets. Thus, in summary, they
concluded that banks with disproportionately large external assets (“banks that are too big”) affect the
stability of the entire banking network in an adverse manner.
Effect of connectivity: For banking networks where all banks have roughly the same amount of external
assets, higher connectivity leads to lower stability. In contrast, for banking networks in which few
banks have disproportionately higher external assets compared to the remaining banks, higher connectivity leads to higher global stability.
Correlated versus random failures: Correlated initial failures of banks causes more damage to the entire
banking network as opposed to just random initial failures of banks.
Phase transition properties of global stability: The global stability exhibits several sharp phase transitions for various banking networks within certain parameter ranges.

7 Preliminary Observations on Shock Propagation
Proposition 7.1. Let hG = (V, F), γ , β , Ei be the given (homogeneous or heterogeneous) banking network.
Then, the following are true:
(a) If degout (v) = 0 for some v ∈ V , then node v must be given a shock (and, must fail due to this shock) for
the entire network to fail.
(b) Let α be the number of edges in the longest directed simple path in G. Then, no new node fails at any
time t > α .
(c) We can assume without loss of generality that G is weakly connected, i.e., the un-oriented version of G
is connected.
Proof.
(a) Since degout (v) = 0, no part of any shock given to any other nodes in the network can reach v. Thus, the
network of v, namely cv = γ av stays strictly positive (since γ > 0) and node v never fails.
(b) Let t last be the latest time a node of G failed, and let V (t) be the set of nodes that failed at time t =
1, 2, . . . , t last . Then, V (1),V (2), . . . ,V (t last ) is a partition of V . For every i = 1, 2, . . . , t last − 1, add directed
14

edges (u, v) from a node u ∈ V (i) to a node v ∈ V (i + 1) if u was last node that transmitted any part of the
shock to v before v failed. Note that (u, v) is also an edge of G and for every node v ∈ V (i + 1) there must
be an edge (u, v) for some node u ∈ V (i). Thus, G has a path of length at least t last .
(c) This holds since otherwise the stability measures can be computed separately on each weakly connected
component.


8 Homogeneous Networks, S TAB2,Φ , Logarithmic Inapproximability
Theorem 8.1. SI∗ (G, 2) cannot be approximated in polynomial time within a factor of (1 − ε ) ln n, for any

constant ε > 0, unless NP ⊆ DTIME nlog log n .

Proof. The dominating set problem for an undirected graph (DOMIN-SET) is defined as follows: given an
undirected graph G = (V, F ) with n = |V | nodes, find a minimum cardinality subset of nodes V ′ ⊂ V such
that every node in V \ V ′ is incident on at least one edge whose other end-point is in V ′ . It is known that
DOMIN-SAT is equivalent to the minimum set-cover problem under L-reduction [9], and thus cannot be

approximated within a factor of (1 − ε ) ln n unless NP ⊆ DTIME nlog log n [28].
Consider an instance G = (V, F) of DOMIN-SET with n nodes and m edges, and let OPT denote the
→
−
→−
−
→
size of an optimal solution for this instance. Our (directed) banking network G = ( V , F ) is obtained
from G by replacing each undirected edge {u, v} by two directed edges (u, v) and (v, u). Thus we have
0 < degin (v) = degout (v) < n for every node v ∈ V . We set the global parameters as follows: E = 10 n,
γ = n−2 and Φ = 1.
For a node v, let Nbr(v) = { u | {u, v} ∈ E } be the set of neighbors of v in G. We claim that if a node v is
shocked at time t = 1, then all nodes in in {v} ∪ Nbr(v) fail at time t = 2. Indeed, suppose that v is shocked
at t = 1. Then, v surely fails because
Φ ev = degin (v) − degout (v) +

E
2 degin (v) + En
= 10 > >
= γ av
n
n
n2

Now, consider t = 2 and consider a node v such that v has not failed but a node u ∈ Nbr(v) failed at time
t = 1. Then, node v surely fails because
(
)
10 − n2
min{su,1 − cu , bu } min{Φ eu − γ au , degin (u)}
sv,2 ≥
=
> min
,1
degin (u, 2)
degin (u)
degin (u)
>

2 degin (v) + En
>
= γ av
n
n2

→
−
Thus, we have a 1–1 correspondence between the solutions of DOMIN-SET and death of G , namely V ′ ⊂ V
→
−
is a solution of DOMIN-SET if and only if shocking the nodes in V ′ makes G fail at time t = 2.


9 Homogeneous Networks, S TAB2,Φ , Logarithmic Approximation
Theorem
  9.1. S TAB2,Φ admits
nΦE
O log
.
γ (Φ − γ ) |E − Φ|

a

polynomial-time

15

algorithm

with

approximation

ratio

Proof. Suppose that Φeu < 0 for some node u ∈ V . Then, there exists an optimal solution in which we do
not shock the node u. Indeed, if u was shocked, the equity of u increases from cu to cu + | Φ eu | and u does
not propagate any shock to other nodes. Thus, if u still fails at t = 2, then it also fails at t = 2 if it was not
shocked.
Let Vshock denote the set of nodes that we will select for shocking, and, for every node v ∈ V , let δ v,u

max{ 0, Φ ev },
if u = v


 min{Φ e − c , b }
v
v v
, if Φ ev > cv and (u, v) ∈ F. Then, our problem reduces to a
be defined as: δ v,u =

degin (v)


0,
otherwise
covering problem of the following type:
find a minimum cardinality subset Vshock ⊆ V such that, for every node u, ∑v∈Vshockδ v,u > cu .
Note that we cannot even explicitly enumerate, for a node u ∈ V , all subsets V ′ ⊆ V \ {u} such that
∑v∈V ′δ v,u > cu , since there are exponentially many such subsets. Let the binary variable xv ∈ {0, 1} be
the indicator variable for a node v ∈ V for inclusion in Vshock . However, we can reformulate our problem as
the following integer linear programming problem:
minimize

∑ xv

v∈V

subject to ∀u ∈ V :

∑δ v,u xv > cu

(1)

v∈V

xu ∈ {0, 1}

δ v,u
cu
xv >
to ensure
ζ
v∈V
v∈V ζ
that every non-zero entry is at least 1. Since the coefficients of the constraints and the objective function are
all positive real numbers, (1) can be approximated
bynthe greedy

oalgorithm described in [24, Theorem 4.1]
δ
with an approximation ratio of 2 + ln n + ln maxv∈V ∑u∈V ζv,u . Now, observe that:


Let ζ = min min{δ u,v }, cu . We can rewrite each constraint
u∈V

v∈V

∑δ v,u xv > cu as ∑

!
 

E −Φ
E
min {δ u,u } = min Φ degin (u) − degout (u) +
=Ω
u∈V
u∈V
n
n
δ u,u >0
δ u,u >0






(Φ − γ ) E
degout (v)
E
−Φ
=Ω
min min {δ u,v } = min min (Φ − γ ) 1 +
u∈V v∈V
u∈V v∈V
degin (v)
degin (v)
n
Φ ev >cv
δ u,v >0



 
γE
E
=Ω
min{cu } = min γ degin (u) +
u∈V
u∈V
n
n
(
)!

E − Φ (Φ − γ ) E γ E
ζ = min min min{δ u,v }, min{cu } = Ω min
,
,
u∈V
u∈V v∈V
n
n
n




E
degout (u)
−Φ
= O ( n (Φ − γ ) E )
max ∑ δ v,u ≤ n max (Φ − γ ) 1 +
v∈V u∈V
u∈V
degin (u)
degin (u)

and thus, maxv∈V

n

δ
∑u∈V ζv,u

o





= O poly n,

1
E
Φ
γ , Φ−γ , E−Φ

16



, giving the approximation bound.



10 Homogeneous Networks, S TABT,Φ , any T , APX-hardness
Theorem 10.1. For any T , computing SI∗ (G, T ) is APX-hard even if the banking network G is a DAG with
degin (v) ≤ 3 and degout (v) ≤ 2 for every node v.
Proof. We reduce the 3-MIN-NODE-COVER problem to S TABT,Φ . 3-MIN-NODE-COVER is defined as
follows. We are given an undirected 3-regular graph G, i.e., an undirected graph G = (V, F ) in which the
degree of every node is exactly 3 (and thus |F| = 1.5 |V |). A valid solution (node cover) is a subset of nodes
V ′ ⊆ V such that every edge is incident to at least one node in V ′ . The goal is then to find a node cover
V ′ ⊆ V such that |V ′ | is minimized. This problem is known to be APX-hard [10].

v6

e1,2

v5

v1

e1,4

{v2 ,v3 }
e2,3

e1,6

e2,5

e3,4

e3,5

e4,5

e5,6

sink
nodes

v4
e2,3

v2
v3
G = (V, F)

u1

u2

u3

u5

u4

u6

−
→
→−
−
→
G = (V , F )

u′1

u2 ′

u′3

u′4

u′5

u′6

super-source nodes
→

→ →

Figure 4: A 3-regular graph G = (V, F ) and its corresponding banking network G= (V , F ).
Given such an instance G = (V, F) of 3-MIN-NODE-COVER, we construct an instance of the banking
→
−
→−
−
→
network G = ( V , F ) as follows:
→
−
• For every node vi ∈ V , we have two nodes ui , u′i in V , and a directed edge (ui , u′i ). We refer to u′i as a
“super-source” node.
→
−
• For every edge {vi , v j } ∈ F with i < j, we have a (“sink”) node ei, j in V and two directed edges
→
−
(ei, j , ui ) and (ei, j , u j ) in F . For notational convenience, the node ei, j is also sometimes referred to as
the node e j,i .
→
−
→
−
Thus, | V | = 3.5 |V |, and | F | = 4 |V |. See Fig. 4 for an illustration. Observe that:
• degin (ui ) = 3 and degout (ui ) = 1 for all i = 1, 2, . . . , |V |.
• degin (u′i ) = 1 and degout (u′i ) = 0 for all i = 1, 2, . . . , |V |. Thus, by Proposition 7.1(a), every node u′i
must be shocked to make the network fail.

17

• degin (ei, j ) = 0 and
degout (ei, j ) = 2 for all i and j.
Since degin (ei, j ) = 0, if a node
ei, j is shocked, no part of the
shock is propagated to any other
node in the network.

t =1
e2,3 e2,5

e1,2

t=2
e2,3 e2,5

e1,2

u2

u2

failed
not shocked
arbitrary
Figure 5: Case (III): if node u2 is shocked then the nodes
e1,2 , e2,3 and e2,5 must fail at t = 2.

→
−
• Since the longest path in G has
2 edges, by Proposition 7.1(b)
no new node fails at any t > 3.

For notational convenience, let n = |V |, E = E/n, and ei, j1 , ei, j2 and ei, j3 be the three edges {vi , v j1 }, {vi , v j2 }
and {vi , v j3 } in G that are incident on the node vi . We will select the remaining network parameters, namely
γ , Φ and E , based on the following desirable properties.
(I) If a node u′i is shocked at t = 1, it fails:


Φ degin (u′i ) − degout (u′i ) + E > γ degin (u′i ) + E ≡ Φ (1 + E ) > γ (1 + E ) ≡ Φ > γ

(2)

degin (ei, j ) − degout (ei, j ) + E < 0 ≡ E < 2

(3)

(II) If a node ei, j is shocked, it does not fail:

(III) If a node ui is shocked at t = 1, then ui fails at t = 1, and the nodes ei, j1 , ei, j2 and ei, j3 fail at time t = 2
if they were not shocked (see Fig. 5 for an illustration):

min Φ (degin (ui ) − degout (ui ) + E ) − γ (degin (ui ) + E ) , degin (ui )
> γ (degin (ei, j1 ) + E )
degin (ui )

min Φ (2 + E ) − γ (3 + E ), 3
>γE
≡
3
The above inequality is satisfied provided:
Φ (2 + E ) > γ (3 + 4E )
1
1>γE ≡ γ <
E

(4)
(5)

(IV) Consider a sink node ei, j . Then, we require that if one or both of the super-source node u′i and u′j are
shocked at t = 1 but the none of the nodes ui , u j and ei, j were shocked, then we require that one or both of
the corresponding nodes ui and u j fail at t = 2, but the node ei, j never fails. Pictorially, we want a situation
as depicted in Fig. 6. This is satisfied provided the following inequalities hold:
(IV-1) ui fails at t = 2 if u′i was shocked (the case of u j and u′j is similar):

min Φ (degin (u′i ) − degout (u′i ) + E ) − γ (degin (u′i ) + E ) , degin (u′i )
degin (u′i )

min (Φ − γ )(1 + E ), 1
> γ (3 + E )
≡
1
18

> γ (degin (ui ) + E )

The above inequality is satisfied provided:
(Φ − γ )(1 + E ) > γ (3 + E ) ≡ Φ(1 + E ) > γ (4 + 2 E )
1
1 > γ (3 + E ) ≡ γ <
3+E

(6)
(7)

(IV-2) ei, j never fails even if both ui and u j have failed:




min (Φ − γ )(1 + E ), 1
E
γE
− γ (3 + E ) ≤
≡ min (Φ − γ )(1 + E ), 1 ≤ 3 γ 1 +
1
2
2
The above inequality is satisfied provided:




E
5E
(Φ − γ )(1 + E ) ≤ 3 γ 1 +
≡ Φ (1 + E ) ≤ γ 4 +
2
2


2
E
1 ≤ 3γ 1 +
≡ γ≥
2
6 + 3E

(8)
(9)

There are obviously many
T >2
t =1
t=2
e2,3
e2,3
e2,3
choices of parameters γ ,
Φ and E that satisfy Equations (2)–(9); here we exu2 u3
u2 u3
u2 u3
hibit just one. Let E =
failed
1 which satisfied Equanot shocked
tion (3). Choosing γ =
arbitrary
never fails
0.23 satisfies Equations (5),
Figure 6: Case (IV): to make e2,3 fail, at least one of u2 or u3 must be shocked.
(7) and (9). Letting Φ =
0.7 satisfies Equations (2), (4), (6) and (8).
Suppose that V ′ ⊂ V is a solution of 3-MIN-NODE-COVER. Then, we shock all the super-nodes, and

the nodes in V ′ . By (I) and (III) all the super-nodes and the nodes in ∪vi ∈V \V ′ {vi } fails at t = 1, and by
→
−
(III) the nodes in ∪{vi ,v j }∈E {ei, j } fails t = 2. Thus, we obtain a solution of G by shocking |V ′ | + n nodes.
i< j

→
−
Conversely, consider a solution of the S TABT,Φ problem on G . Remember that all the super-nodes must
be shocked, which ensures that we need to shock n + a nodes for some integer a ≥ 0, and that any node vi
that is not shocked will fail at t = 2. By (II) it is of no use to shock the sink nodes. Thus, the shocked nodes
consist of all super-nodes and a subset V ′ of cardinality a of the nodes u1 , u2 , . . . , un . By (IV) for every node
ei, j at least one of the nodes ui or u j must be in U . Thus, the set of nodes {vi | ui ∈ U } form a node cover of
G of size a.
That the reduction is an L-reduction follows from the observation that any locally improvable solution
of 3-MIN-NODE-COVER has between n/3 and n nodes.


11 Restricted Homogeneous Networks, S TABT,Φ , Any T , Exact Solution
The APX-hardness result of Theorem 10.1 has constant values for both Φ and γ , and requires degout (v) = 2
for some nodes v. We show that if degout (v) ≤ 1 for every node v then under mild technical assumptions
19

SI∗ (G, T ) can be computed in polynomial time for any T and, in addition, if degin (v) is bounded by a
constant for every node v then the network is highly stable (i.e., SI∗ (G, T ) is large). Recall that an in-

arborescence is a directed rooted tree where all edges are oriented towards the root.
Theorem 11.1. If the banking network G is a rooted in-arborescence then SI∗ (G, T ) >

1
1 + degmax
in



Φ
γ

,
−1


that every node of G can be individuwhere degmax
in = max v∈V degin (v) . Moreover, under the assumption

∗
2
ally failed by shocking, SI (G, T ) can be computed exactly in O n time.

∗
Remark 11.2. Thus, for example, when degmax
in = 3, γ = 0.1 and Φ = 0.15, we get SI (G, T ) > 0.22 and the
network cannot be put to death without shocking more than 22% of the nodes. The proof gives an example
for which the lower bound is tight.

In the rest of this section, we prove the above theorem. Let G = (V, F) be the given in-arborescence
rooted at node r. We will use the following notations and terminologies:
• u → v and u { v denote a directed edge and a directed path of one of more edges, respectively, from
node u to node v.
• If (u, v) ∈ F then v is the parent of u and u is a child of v. Similarly, if u { v exists in G then v an
ancestor of u and u a descendent of v.
• Let ∇(u) = { v | u { v exists in G } denote the set of all proper ancestors of u, and ∆(u) = { v | v {
u exists in G } ∪ {u} denote the set of all descendants of u (including the node u itself). Note that for
the network G to fail, at least one node in ∇(u) ∪ {u} must be shocked for every node u.

Suppose that we shock a node u of G (and shock no other nodes in ∆(u)). If u fails, then the shock splits
and propagates to a subset of nodes in ∆(u) until each split part of the shock terminates because of one of
the following reasons:
• the component of the shock reaches a “leaf” node v with degin (v) = 0, or
• the component of the shock reaches a node v with a sufficiently high cv such that v does not fail.
Based on the above observations, we define the following quantities.

Definition 11.3 (see Fig. 7 for illustrations). The influence zone of a shock on u, denoted by iz(u), is the set
of all failed nodes v ∈ ∆(u) within time T when u is shocked (and, no other node in ∆(u) is shocked). Note
that u ∈ iz(u).
Note that, for any node u, iz(u) can be computed in O(n) time.


Lemma 11.4. For any node u, iz(u) < 1 + degin (u) Φγ − 1 .

Proof. For notational simplicity, let E = E/n. If the node u does not fail when shocked, or u fails but it
has no child, then iz(u) ≤ 1 and our claim holds since Φ > γ . Otherwise, u fails and each of its degin (u)
children at level 2 receives a part of the shock given by


Φ (degin (u) − 1 + E ) − γ (degin (u) + E )
,1
a = min
degin (u)




E
E
< Φ 1+
−γ 1+
≤ Φ (1 + E ) − γ (1 + E )
degin (u)
degin (u)
20

shocked
failed (due to shock)
not shocked and not failed

parent

u

......
......

u

..
.

iz(u)
child

..
.

.. . . . . . . ..
.
.
......

}

j

Φ
γ

k
−1

Figure 8: A tight example for the bound
in Lemma 11.4 (E = 0).
Figure 7: Influence zone of a shock on u.

Consider a child v of u. Each node v′ ∈ ∆(v) that fails due to the shock subtracts an amount of γ (degin (v′ ) + E ) ≥
γ (1 + E ) from a provided this subtraction does not result in a negative value.
Thus,
the total number of


Φ(1+E )−γ (1+E )
Φ

= 1 + degin (u) γ − 1 .
failed nodes is strictly less than 1 + degin (u)
γ (1+E )
Remark 11.5. The bound in Lemma 11.4 is tight as shown in Fig. 8.
Lemma 11.4 immediately implies that

SI∗ (G, T ) >

n
n

max iz(u)
u∈V

n

o

>




Φ
−
1
n 1 + degmax
in
γ
n

=

1
1 + degmax
in



Φ
γ


−1

We now provide a polynomial time algorithm to compute SI∗ (G, T ) exactly assuming each node can be
shocked to fail individually. For a node u, define the following:
• For every node u′ ∈ ∇(u), SI∗S A NS (G, T, u, u′ ) is the number of nodes in an optimal solution of S TABT,Φ
for the subgraph induced by the nodes in ∆(u) (or ∞, if there is no feasible solution of S TABT,Φ for
this subgraph under the stated conditions) assuming the following:
– u′ was shocked,
– u was not shocked, and
– no node in the path u′ { u excluding u′ was shocked.
• SI∗S A S (G, T, u) is the number of nodes in an optimal solution of S TABT,Φ for the subgraph induced
by the nodes in ∆(u) (or ∞, if there is no feasible solution of S TABT,Φ under the stated conditions)3
assuming that the node u was shocked (and therefore failed).
We consider the usual partition of the nodes of G into levels: level(r) = 1 and level(u) = level(v) + 1 if u is
a child of v. We will compute SI∗S A S (G, T, u) and SI∗S A NS (G, T, u, v) for the nodes u level by level, starting
3 Intuitively,

a value of ∞ signifies that the corresponding quantity is undefined.

21

with the highest level and proceeding to successive lower levels. By Observation 7.1(a), the root r must
be shocked to fail for the entire network to fail, and thus SI∗S A S (G, T, r) will provide us with our required
optimal solution.
Every node u at the highest level has degin (u) = 0. In general, SI∗S A S (G, T, u) and SI∗S A NS (G, T, u, u′ ) can
be computed for any node u with degin (u) = 0 as follows:
Computing SI∗S A S (G, T, u) when degin (u) = 0: SI∗S A S (G, T, u) = 1 by our assumption that every node can
be shocked to fail.
Computing SI∗S A NS (G, T, u, u′ ) when degin (u) = 0:
• If u ∈ iz(u′ ) then shocking node v makes node u fail. Since node u fails without being shocked,
we have SI∗S A NS (G, T, u, u′ ) = 0.
• Otherwise, node u does not fail. Thus, there is no feasible solution and SI∗S A NS (G, T, u, u′ ) = ∞.
Note that we only count the number of nodes in ∆(u) in the calculations of SI∗S A NS (G, T, u, u′ ) and SI∗S A S (G, T, u).
Now, consider a node u at some level ℓ with degin (u) > 0. Let v1 , v2 , . . . , vdegin (u) be the children of u at
level ℓ + 1. Note that ∇(v1 ) = ∇(v2 ) = · · · = ∇(vdegin (u) ).
Computing SI∗S A S (G, T, u) when degin (u) > 0: By our assumption, u fails when shocked. Note that no
node in ∆(u) \ {u} can receive any component of a shock given to a node in V \ ∆(u) since u failed.
For each child vi of u we have two choices: vi is shocked and (and,
o
n therefore, fails), or vi is not shocked.
deg (u)
Thus, in this case we have SI∗S A S (G, T, u) = 1 + ∑i=1in min SI∗S A S (G, T, vi ), SI∗S A NS (G, T, vi , u) .
Computing SI∗S A NS (G, T, u, u′ ) when degin (u) > 0: Since u′ is shocked and u is not shocked, the following
cases arise:
• If u < iz(u′ ) then then u does not fail. Thus, there is no feasible solution for the subgraph induced
by the nodes in ∆(u) under this condition, and SI∗S A NS (G, T, u, u′ ) = ∞.
• Otherwise, u ∈ iz(u′ ), and therefore u fails when u′ is shocked. For each child vi of u, there
are two options: vi is shocked and
o in this case we have
n fails, or vi is not shocked. Thus,
deg (u)
SI∗S A NS (G, T, u, u′ ) = ∑i=1in min SI∗S A S (G, T, vi ), SI∗S A NS (G, T, vi , u′ ) .

Let ℓmax be the maximum level number of any node in G. Based on the above observations, we can design
the dynamic programming algorithm as shown in Fig. 9 to compute an optimal solution of S TABT,Φ on G.

It is easy to check that the running time of our algorithm is O n2 .

12 Heterogeneous Networks, S TABT,Φ , Any T , Logarithmic Inapproximability

Theorem 12.1. Assuming NP 1 DTIME nlog log n , for any constant 0 < ε < 1 and any T , it is impossible to
approximate SI∗ (G, T ) within a factor of (1 − ε ) ln n in polynomial time even if G is a DAG.

22

(* preprocessing *)
∀u ∈ V : compute iz(u)
(* dynamic programming *)
for ℓ = ℓmax , ℓmax −1, . . . , 1 do
for each node u at level ℓ do
if degin (u) = 0 then
SI∗S A S (G, T, u) = 1
∀u′ ∈ ∇(u) : if u ∈ iz(u′ ) then SI∗S A NS (G, T, u, u′ ) = 0 else SIaS A NS st(G, T, u, u′ ) = ∞
else
(* degin (u) > 0 *)
n
o
deg (u)

SI∗S A S (G, T, u) = 1 + ∑i=1in

min SI∗S A S (G, T, vi ), SI∗S A NS (G, T, vi , u)

∀u′ ∈ ∇(u) : if u < iz(u′ ) then SI∗S A NS (G, T, u, u′ ) = ∞
else
n
SI∗S A NS (G, T, u, u′ )

deg (u)
= ∑i=1in min

SI∗S A S (G, T, vi ),

endif

SI∗S A NS (G, T, vi , u′ )

o

endif
endfor
endfor
return SI∗S A S (G, T, r) as the solution
Figure 9: A polynomial time algorithm to compute SI∗ (G, T ) when G is a rooted in-arborescence and each
node of G fails individually when shocked.
U = {u1 , u2 , u3 , u4 }
S = {S1 , S2 , S3 , S4 }
S1 = {u1 , u2 , u3 }
S2 = {u3 , u4 }
S3 = {u3 }
S4 = {u1 , u2 }

u1

3
2

u2
1

3
2

u3

u4

1
3

3
2

1
3
2

S1

S2
1

S3
1

1

S4

Figure 10: An instance hU , S i
of S ET-C OVER and its corresponding banking network G =
(V, F).

1

B
Proof. The (unweighted) S ET-C OVER problem is defined as follows. We have an universe U of n elements,
a collection of m sets S over U . The goal is to pick a sub-collection S ′ ⊆ S containing a minimum
number of sets such that these sets “cover” U , i.e., ∪S∈S ′ S = U . It is known that there exists instances of
S ET-C OVER that cannot be approximated within a factor of (1 − δ ) ln n, for any constant 0 < δ < 1, unless

NP ⊆ DTIME nlog log n [28]. Without any loss of generality, one may assume that every element u ∈ U
belongs to at least two sets in S since otherwise the only set containing u must be selected in any solution.
Given such an instance hU , S i of S ET-C OVER, we now construct an instance of the banking network
G = (V, F) as follows:
• We have a special node B.
• For every set S ∈ S , we have a node S, and a directed edge (S, B).
23

• For every element u ∈ U , we have a node u, and directed edges (u, S) for every set S that contains u.
Thus, |V | = n + m + 1, and |F| < n m + m. See Fig. 10 for an illustration. We set the shares of internal assets
for each bank as follows:
• For each set S ∈ S , if S contains k > 1 elements then, for each element u ∈ S, we set the weight of
the edge e = (u, S) as w(e) = 3k .
• For each set S ∈ S , we set the weight of the edge (S, B) as 1.
Thus, I = 4m. Also, observe that:
• For any S ∈ S , bS = 3, and ιS = 1.
• For any u ∈ U , bu = 0. Also, since u belongs to at least two sets in S and any set has at most n − 1
elements, n2 ≤ ιu < 3n
2 .
• bB = m and ιB = 0.
• Since degin (u) = 0 for any element u ∈ U , if a node u is shocked, no part of the shock is propagated
to any other node in the network.
• Since the longest path in G has 2 edges, by Proposition 7.1(b) no new node in G fails for T > 3.
Let the share of external assets for a node (bank) y be denoted by Ey (thus, ∑y∈V Ey = E). We will select the
remaining network parameters, namely γ , Φ and the Ey values, based on the following properties.
(I) If the node B is shocked at t = 1, it fails:
Φ (bB − ιB + EB ) > γ (bB + EB ) ≡ Φ (m + EB ) > γ (m + EB ) ≡ Φ > γ

(10)

(II) For any S ∈ S , if node S is shocked at t = 1, then S fails at t = 1, and, for every u ∈ S, node u fails at
time t = 2:

min Φ (bS − ιS + ES ) − γ (bS + ES ) , bS
> γ (bu + Eu )
degin (S)

min Φ (2 + ES ) − γ (3 + ES ), 3
≡
> γ Eu
|S|
The above inequality is satisfied if:
Φ (2 + ES ) > γ ( 3 + ES + |S| Eu )
Φ (2 + ES ) − γ (3 + ES ) ≤ 3

(11)
(12)

(III) For any u ∈ U , consider the node u, and let S1 , S2 , . . . , S p ∈ S be the p sets that contain u. Then,
we require that if the node B is shocked at t = 1 then B fails at t = 1, every node among the set of nodes
{ S1 , S2 , . . . , S p } that was not shocked at t = 1 fails at t = 2, but the node u does not fail if the none of the
nodes u, S1 , S2 , . . . , S p were shocked, This is satisfied provided the following inequalities hold:

24

(III-1) Any node among the set of nodes { S1 , S2 , . . . , S p } that was not shocked at t = 1 fails at t = 2. This
is satisfies provided for any set S ∈ S the following holds:

min Φ (bB − ιB + EB ) − γ (bB + EB ) , bB
degin (B)

> γ (bS + ES )
 


EB
, 1 > γ (3 + ES )
≡ min (Φ − γ ) 1 +
m

The above inequality is satisfied provided:






EB
EB
EB
(Φ − γ ) 1 +
> γ (3 + ES ) ≡ Φ 1 +
> γ 4 + ES +
m
m
m
1
1 > γ (3 + ES ) ≡ γ <
3 + ES

(13)
(14)

(III-2) u does not fail if the none of the nodes u, S1 , S2 , . . . , S p were shocked:
 


γ Eu
EB
, 1 − γ (3 + ES ) ≤
min (Φ − γ ) 1 +
m
n




 

EB
Eu
≡ min (Φ − γ ) 1 +
, 1 ≤ γ 3 + ES +
m
n

The above inequality is satisfied provided:








Eu
EB
EB Eu
EB
+
≤ γ 3 + ES +
≡ Φ 1+
≤ γ 4 + ES +
(Φ − γ ) 1 +
m
n
m
m
n


EB
1
(Φ − γ ) 1 +
≤1 ≡ γ ≥Φ−
m
1 + EmB

(15)
(16)

There are many choices of parameters γ , Φ and Ey ’s satisfying Equations (10)–(16); we exhibit just one:
∀S ∈ S : ES = 0

EB = 0

∀u ∈ U : Eu =

1
100n

γ = 0.1

Φ = 0.4 +

1
n10000

Suppose that S ′ ⊂ S is a solution of S ET-C OVER. Then, we shock the node B and the nodes S for each
S ∈ S ′ . By (I) and (II) the node B and the nodes S for each S ∈ S ′ fails at t = 1, and by (II) the nodes u
for every u ∈ U fails t = 2. Thus, we obtain a solution of G by shocking |S ′ | + 1 nodes.
Conversely, consider a solution of the S TABT,Φ problem on G. If a node u for some u ∈ U was shocked,
we can instead shock the node S for any set S that contains a, which by (II) still fails all the nodes in the
network and does not increase the number of shocked nodes. Thus, after such normalizations, we may
assume that the shocked nodes consist of B and a subset S ′ ⊆ S of nodes. By (II) and (III) for every node
u ∈ U at least one set that contains u must be in S ′ . Thus, the collection of sets in S ′ form a cover of U
of size |cS′ |.


13 Heterogeneous Networks, S TAB2,Φ , Logarithmic Approximation

For any positive real x > 0, let x = max {x, 1/x} and x = min {x, 1/x}. Let wmin = mine: w(e)>0 w(e) ,



wmax = maxe w(e) , αmin = minv: αv >0 αv , and αmax = maxv αv .
25

Theorem
13.1. S TAB2,Φ
admits


n E wmax wmin αmax
O log
.
Φ γ (Φ − γ ) E wmin αmin wmax

a

poly-time

algorithm

with

approximation

ratio

Proof. We can reuse the proof of the corresponding 
approximation
for homogeneous
networks in Theoo
n

δ
rem 9.1 to obtain an approximation ratio of 2+ln n+ln maxv∈V ∑u∈V ζv,u , where ζ = min min{δ u,v }, cu ,
u∈V
v∈V
o
n
δ v,u
provided we recalculate maxv∈V ∑u∈V ζ . Then,
min {δ u,u } = min

u∈V
δ u,u >0

u∈V
δu,u >0

(

∑

Φ

w(e) − ∑ w(e) + αv E

e=(v′ ,u)∈F

e=(u,v′ )∈F

!)



= Ω poly s, Φ, E, αmin





w(e) 

∑






E
e=(v,v′ )∈F
α
v
−Φ
min min {δ u,v } = min min (Φ − γ ) 
1
+

u∈V v∈V
u∈V v∈V 
w(e) 

∑
∑w(e) 
Φ ev >cv 


δ u,v >0
e=(v′ ,v)∈F
e=(v′ ,v)∈F


= Ω poly n−1 , Φ − γ , Φ, E, wmax , wmin , αmin
(

∑ w(e) + αu E

min{cu } = min γ
u∈V

u∈V

e=(v′ ,u)∈F

!)



= Ω poly n−1 , γ , E, αmin , wmin



ζ = min min min{δ u,v }, min{cu } = Ω poly n−1 , Φ − γ , Φ, γ , E, wmin , αmin , wmax
u∈V
u∈V v∈V






w(e)
∑








E
α
e=(v,v′ )∈F
v


E,
w
,
w
,
α
max ∑ δ v,u ≤ n max (Φ − γ ) 1 +
=
O
poly
n,
−
Φ
max
max
min
u∈V 
v∈V u∈V

w(e) 


∑
∑w(e)


′
′


e=(v ,v)∈F

and thus,
(
max
v∈V

∑

u∈V

δ v,u
ζ

)

e=(v ,v)∈F




= O poly n, Φ−1 , γ −1 , (Φ − γ )−1 , E, E −1 , wmax , wmin , αmax , wmin −1 , αmin −1 , wmax −1

giving the desired approximation bound.



14 Heterogeneous Networks, S TAB T,Φ , T > 3, Poly-logarithmic Inapproximability

Theorem 14.1. Assuming NP * DTIME npoly(log n) , for any constant 0 < ε < 1 and any T > 3, it is impos1−ε
sible to approximate SI∗ (G, T ) within a factor of 2log n in polynomial time even if G is a DAG.
Proof. The M INREP problem (with minor modifications from the original setup) is defined as follows. We
are given a bipartite graph G = (V left ,V right , F) such that the degree of every node of G is at least 10, a
right
left
partition of V left into |Vα | equal-size subsets V1left ,V2left , . . . ,Vαleft , and a partition of V right into |V β | equalright

size subsets V1

right

,V2

right

, . . . ,Vβ

.
26

These partitions define a natural “bipartite super-graph” Gsuper = (Vsuper , Fsuper ) in the following manner.
right
Gsuper has a “super-node” for every Vileft (for i = 1, 2, . . . , α ) and for every V j
(for j = 1, 2, . . . , β ). There
right

exists an “super-edge” hi, j between the super-node for Vileft and the super-node for V j
exists u

∈ Vileft

and v

right
∈ Vj

if and only if there

such that {u, v} is an edge of G. A pair of nodes u and v of G “witnesses” the

super-edge hi, j of H provided u is in Vileft , v is in V jright and the edge {u, v} exists in G, and a set of nodes
V ′ ⊆ V of G witnesses a super-edge if and only if there exists at least one pair of nodes in S that witnesses
the super-edge.
The goal of M INREP is to find V1 ⊆ V left and V2 ⊆ V right such that V1 ∪V2 witnesses every super-edge of H
and the size of the solution, namely |V1 |+ |V2 |, is minimum. For notational simplicity, let n = |V left |+ |V right |.
The following result is a consequence of Raz’s parallel repetition theorem [40, 47].
Theorem 14.2. [40] Let L be any language in NP and 0 < δ < 1 be any constant. Then, there exists a
reduction running in npoly(log n) time that, given an input instance x of L, produces an instance of M INREP
such that:
• if x ∈ L then M INREP has a solution of size α + β ;
1−δ

• if x < L then M INREP has a solution of size at least (α + β ) · 2log

n.

1−δ

Thus, the above theorem provides a 2log n -inapproximability for M INREP under the complexity
polylog(n) .
theoretic assumption
of
NP
*
DTIME
n
n
o

Let Fi, j = {u, v} u ∈ Vileft , v ∈ V jright , {u, v} ∈ F . We now show our construction of an instance of
→
−
→−
−
→
S TABT,Φ from an instance of M INREP . Our directed graph G = ( V , F ) for S TABT,Φ is constructed as
follows (see Fig. 11 for an illustration):
Nodes:

−−→ −
→
→
• For every node u ∈ Vileft of G we have a corresponding node −
u in the set of nodes Vileft in G , and for
−
−right
−→ −
→
right
→
of G we have a corresponding node −
v in the set of nodes V
in G . The total
every node v ∈ V
j

j

number of such nodes is n.

right

• For every edge {u, v} of G with u ∈ Vileft and v ∈ V j
→
−→ −
of nodes Fi, j in G . There are |F| such nodes.

→
→
, we have a corresponding node f−
u ,−
v in the set

−→ −
→
• For every super-edge hi, j of Gsuper , we have a node hi, j in G . There are |Fsuper | such nodes.
• We have one “top super-node” vtop , one “side super-node” vside , and 2 |F| additional nodes B1 , B2 , . . . , B|F| ,
|F|

|F|

D1 , D2 , . . . , D|F| . Let B = ∪ j=1 B j and D = ∪ j=1 D j .

→
−
Thus, n + 3|F| + 2 < | V | = n + |F| + |Fsuper | + 2 + 2 |F| < n + 4 |F| + 2.
Edges:

 −
→
• For every node u of G, we have an edge u, vtop in G . There are n such edges.

→
−
→
−
→
−
→
→
→
→
• For every edge {u, v} of G, we have two edges ( f−
u ,−
v , u ) and ( f−
u ,−
v , v ) in G . There are 2 |F| such
edges.

27

M INREP instance
G = (V left ,V right , F)
Gsuper = (Vsuper , Fsuper )

Super-node
vtop

=⇒
−
−−
→
V right
−
−−
→
−
−right
−
→
V jright
V1
→
−
· · · · · ···· · ···· · · v· · ···· · · · · ···· · ·

{
{

−−→
V left

−−→
Vileft
→
−
· · ···· · ···· · ·u · · ···· · · · · ···· · ·

···

vside

B

D

B1

D1

B2
..
.
..
.

D2
..
.
..
.

B|F| D|F|

···

···

−→
h1,1

−−→
Vαleft
···

· ···· · · ··
−→
F1,1

· · ·· · ···· · ·
−·→
Fi, j

−
→
f→
u ,−
v

··· ···

· · ···· · ···· · ···· · ·

−→
hi, j

···

−
−right
−
→
Vβ

···

−−→
Fα ,β

···

· · ···· · ···· · ···· · ·

−−→
hα ,β

[

−−→
V1left

Fsuper

Figure 11: Reduction of an instance of M INREP to S TABT,Φ for heterogeneous networks.
 −
−→
→
→
→
−
• For every super-edge hi, j of Gsuper and for every edge fu,v in Fi, j , we have an edge hi, j , f−
u , v in G .
There are |F| such edges.
• Let p1 , p2 , . . . , p|F| be any arbitrary ordering of the edges in F. Then, for every j = 1, 2, . . . , |F|, we
have the edges (vside , B j ), (B j , D j ) and (D j , p j ). The total number of such edges is 3|F|.
→
−
Thus, | E | = n + 6 |F|.
Distribution of internal assets: We set the weight of every edge to 1, Thus, I = n + ∑u∈V left ∪V right deg(u) +

4 |F| = n + 6 |F|.

Let deg(u) ≥ 10 be the degree of node u ∈ V left ∪V right . Observe that:

• bvtop = n, and ιvtop = 0. Since degout vtop = 0, by Proposition 7.1(a) the node vtop must be shocked to
make the network fail.
• bvside = |F|, and ιvside = 0. Since degout (vside ) = 0, by Proposition 7.1(a) the node vside must be shocked
to make the network fail.

28

→
→
• For any u ∈ V left ∪V right , b−
u = 1.
u = deg(u) and ι−
→
→
• For any node f−
= 1 and ι f−→u ,−→v = 2.
→
→
u ,−
v , b f−
u ,−
v

−→
−
→
−
→
→ = 0 and ι−→ = |Fi, j |. Since degin hi, j = 0 for any node hi, j , if such a node
• For every node hi, j , b−
hi, j
hi, j
is shocked, no part of the shock is propagated to any other node in the network.
• For every j, bD j = ιD j = bB j = ιB j = 1.
• Since the longest directed path in G has 4 edges, by Proposition 7.1(b) no new node in G fails for
t > 4.
Let the share of external assets for a node (bank) y be denoted by Ey (thus, ∑y∈V Ey = E). We will select
the remaining network parameters, namely γ , Φ and the set of Ey values, based on the following desirable
properties and events. For the convenience
of the readers,
all the relevant constraints are also summarized
n−

→o
−→ S 
were shocked at t = 1.
∪i, j hi, j
in Table 3. Assume that no nodes in ∪i, j Fi, j

(I) Suppose that the node vtop is shocked at t = 1. Then, the following happens.
(I-a) vtop fails at t = 1:

Φ (bvtop − ιvtop + Evtop ) > γ (bvtop + Evtop ) ≡ Φ (n + Evtop ) > γ (n + Evtop ) ≡ Φ > γ

(17)

−−→ −
−−
→
→
(I-b) Each node −
u ∈ V left ∪ V right that was not shocked at t = 1 fails at t = 2:

min Φ (bvtop − ιvtop + Evtop ) − γ (bvtop + Evtop ), bvtop
→
→
> γ (b−
u + E−
u)
degin (vtop )

min Φ (n + Evtop ) − γ (n + Evtop ), n
→
≡
> γ (deg(u) + E−
u)
n
These constraints are satisfied provided:
Φ (n + Evtop ) − γ (n + Evtop )
→
> γ (deg(u) + E−
u) ≡ Φ>γ
n

1+

Φ (n + Evtop ) − γ (n + Evtop ) ≤ n ≡ Φ ≤ γ +

→
deg(u) + E−
u

1+
1
1+

Evtop
n

Evtop
n

!

(18)

(19)

→
−
→
→
(I-c) If the nodes −
u,→
v and f−
u ,−
v were not shocked at t = 1, then the part of the shock, say σ1 , given

29

Φ>γ



Φ > γ 1 +

(17)


→
deg(u) + E−
u 

Φ≤γ+

(18)

Evtop
n

1+

1

Φ>γ

(19)

Evtop
n

1+



1
1+
−
deg(u) − 1 + E→
u



→
→
→
→
Φ (deg(v) − 1 + E−
Φ (deg(u) − 1 + E−
v ) − γ (deg(v) + E−
v )
u ) − γ (deg(u) + E−
u )
+
> γ 1 + E f→
−u ,→
−
v
deg(u)
deg(v)


→
deg(u) + E−
deg(u)
u
Φ≤γ
+
→
→
deg(u) − 1 + E−
deg(u)
− 1 + E−
u
u


→
→
→
→
Φ (deg(u) − 1 + E−
v ) − γ (deg(v) + E−
v)
u ) − γ (deg(u) + E−
u ) + Φ (deg(v) − 1 + E−
→
− γ 1 + E f→
> γ E−
−
−
u ,→
v
hi, j
deg(u)
deg(v)


Evside


γ 2 + |F|
+ EB j
1


→ <1
γ E−
Φ ≤ γ 1+
Φ>
(24)
(25)
(26)
E
hi, j
EB j
1 + vside



(20)

(21)
(22)
(23)

|F|

Φ>γ



(|F| + Evside )
3 |F| + |F|EB j + |F|ED j + Evside


Φ ≤ γ 1 +



Φ≤γ



Φ≤γ

1+

Evtop
n



1 + EB j
1+

+

Evside
|F|

→
+ deg(u) + E−
u

1+

Evtop
n



Φ≤γ

3+
1+

Ev



1+

+

1+

Evside
|F|



Φ≤γ

Ev

3+

→
−

1+



Φ>γ

(33)

Evtop
n

+ EB j + ED j
− EB j + ED j
Ev



+

Evside
|F|

Evside
|F|



+ EB j + ED j

1+

+

Evside
|F|

Ev

Evside
|F|

Ev

Evside
|F|

1+

Ev

Evside
|F|

Evside
|F|

→
−

Ev

Evside
|F|

Evside
|F|

+ EB j + ED j

+ EB j + ED j

→
−

top
1 +
v −1
+ deg(u)
+ Edeg(v)
n deg(u)
→
−




(31)




(34)

1+




− EB j + ED j
+

1
deg(u)

+

Evtop
n deg(u)

1

+

1
deg(v)

Ev

top
+ n deg(v)
+

Evside
|F|

(36)
− EB j + ED j


−→
E−
Evtop
Evtop
Evside
hi, j
→
→
E−
E−
1
1
u
v
6
+
+
+
+
+
+
+
E
+
E
+
E
+
+
→
−
→
−
B
D
f
j
j
u,v
deg(u)
n deg(u)
deg(u)
deg(v)
n deg(v)
deg(v)
|F|
|Fi, j | 

Φ≤γ

Evtop
Evtop
Evside
1
1
1 + deg(u) + n deg(u) + deg(v) + n deg(v) + |F| − EB j + ED j




Evside
Evside
2 + |F|
2 + |F|
+ EB j
+ EB j + 1 + ED j
1
1
+
+
Φ≤γ
Φ≤γ
(38)
Evside
Evside
Evside
Evside
1 + |F| − EB j
1 + |F| − EB j
1 + |F| − EB j + ED j
1 + |F| − EB j + ED j






Φ≤γ

Ev

Ev

2+

1
deg(u)

+

E

Eu
Ev
vside
top
1
 6 + deg(u) + n deg(u) + deg(u) + deg(v) + |F| + EB j + E f−→u ,−→v + ED j +
Φ≤γ
Evtop
Evside
→
E−
1
1
v
+ n deg(u)
− deg(v)
+ deg(v)
+ |F|
− EB j + ED j
2 + deg(u)

Eu
Ev
top
1
6 + deg(u)
+ n deg(u)
+ deg(u)
+ deg(v)
+
→
−

Evtop
n deg(u)

−

→
−

1
deg(v)

+

Evside
|F|

→
E−
v
deg(v)

+

→
−

→
−

+ EB j + E f−→u ,−→v + ED j

Evside
|F|

(28)

(32)

Evside
|F|

E u +1
Ev
top
+ EB j + ED j + n deg(u)
+ deg(u)
+ deg(v)
+ E f→
−
−
u ,→
v

2+



(35)

→
−

top
top
1 +
1 +
1 + deg(u)
+ deg(v)
+
n deg(u)
n deg(v)

Ev

Ev

1
ED j

− EB j + ED j

Eu
Ev
top
top
1 +
1 +
6 + deg(u)
+ deg(u)
+ deg(v)
+ deg(v)
+ E f−→u ,−→v +
n deg(u)
n deg(v)
→
−

Ev

1
1+

→
−

1+

1

top
top
1 +
1 +
+ deg(v)
+ deg(u)
n deg(u)
n deg(v)

6+



Φ≤γ

(27)

Eu
Ev
top
top
1 +
1
6 + deg(u)
+
−
−
u ,→
v
n deg(u) + deg(u) + deg(v) + n deg(v) + deg(v) + E f→

deg(u)
1+

1

(30)

Evside
|F|



Φ≤γ+

(29)

1

Φ>γ

Evside
|F|
Evside
|F|



− EB j + ED j



+

−→
γ E−
h
i, j

|Fi, j |



2+

+

Evtop
n deg(u)

−

1
deg(v)

Ev
+ deg(v)
+
→
−

Evside
|F|

(42)
− EB j + ED j

Table 3: List of all inequalities to be satisfied in the proof of Theorem 14.1.

30

(39)

(40)




1
1
deg(u)

(37)

→
→
to vtop that is received by node f−
u ,−
v at t = 3 is:
(
)

min Φ (bvtop − ιvtop + Evtop ) − γ (bvtop + Evtop ), bvtop
→
→
→
min
− γ (b−
u + E−
u ) , b−
u
degin (vtop )
σ1 =
→
degin (−
u)
)
(

min Φ (bvtop − ιvtop + Evtop ) − γ (bvtop + Evtop ), bvtop
→
→
→
min
− γ (b−
v + E−
v ) , b−
v
degin (vtop )
+
→
degin (−
v)
(
)

min Φ (n + Evtop ) − γ (n + Evtop ), n
→
min
− γ (deg(u) + E−
u ) , deg(u)
n
=
deg(u)
(
)

min Φ (n + Evtop ) − γ (n + Evtop ), n
→
min
− γ (deg(v) + E−
v ) , deg(v)
n
+
deg(v)
→
−
→
−
→
−
→
→
On the other hand, if the node f−
u ,−
v and exactly one of the nodes u and v , say u , were not
→
→
shocked at t = 1, then the part of the shock, say σ1′ , given to vtop that is received by node f−
u ,−
v
at t = 3 is:
)
(

min Φ (n + Evtop ) − γ (n + Evtop ), n
→
min
− γ (deg(u) + E−
u ) , deg(u)
n
′
σ1 =
deg(u)
→
(II) Suppose that some node −
u is shocked at t = 1. Then, the following happens.

→
(II-a) Node −
u fails at t = 1:
→
→
→
→
→
Φ (b−
u + E−
u ) ≡ Φ>γ
u − ι−
u + E−
u ) > γ (b−



1
1+
→
deg(u) − 1 + E−
u



(20)

−→
−→
−
→
→
−
→
→
(II-b) Node f−
u ,−
v ∈ Fi, j fails at t = 2 and node hi, j fails at t = 3 if both u and v were shocked at
t = 1:
→
→
→
→
→
→
min { Φ (b−
u − ι−
u + E−
u ) − γ (b−
u + E−
u ), b−
u }
→
−
degin ( u )


→
→
→
→
→
→
min { Φ (b−
v + E−
v ), b−
v }
v − ι−
v + E−
v ) − γ (b−
>
+
b
+
E
γ
→
→
→
→
f−
f−
→
u ,−
v
u ,−
v
degin (−
v)

≡

min



→
→
min { Φ (deg(u) − 1 + E−
u ) − γ (deg(u) + E−
u ), deg(u) }
deg(u)


→
→
min { Φ (deg(v) − 1 + E−
v ), deg(v) }
v ) − γ (deg(v) + E−
+
> γ 1 + E f−→u ,−→v
deg(v)

→
→
→
→
→
→
min { Φ (b−
u ) − γ (b−
u + E−
u − ι−
u }
u ), b−
u + E−
−
degin (→
u)

+

→
→
→
→
→
→
min { Φ (b−
v − ι−
v }
v ), b−
v + E−
v ) − γ (b−
v + E−
−v )
degin (→

→
→
degin f−
u ,−
v






− γ b f−→u ,−→v + E f−→u ,−→v , b f−→u ,→
−v



→ + E−→
> γ b−
h
h
i, j

31

i, j

≡
min



 

→
→
→
→
min { Φ (deg(u) − 1 + E−
min { Φ (deg(v) − 1 + E−
u ), deg(u) }
v ), deg(v) }
u ) − γ (deg(u) + E−
v ) − γ (deg(v) + E−
+
− γ 1 + E f→
,1
−
→
−
u,v
deg(u)
deg(v)

→
> γ E−
h
i, j

These constraints are satisfied provided the inequalities (17)–(20) are satisfied, and the following
holds:


−
→
→
→
Φ (deg(u) − 1 + E→
Φ (deg(v) − 1 + E−
u ) − γ (deg(u) + E−
v ) − γ (deg(v) + E−
u )
v )
+
> γ 1 + E f−→u ,−→v
deg(u)
deg(v)
−
→
Φ (deg(u) − 1 + E→
u ) − γ (deg(u) + E−
u ) ≤ deg(u) ≡ Φ ≤ γ



→
deg(u) + E−
u
→
deg(u) − 1 + E−
u



+

(21)

deg(u)
→
deg(u) − 1 + E−
u



→
→
→
→
Φ (deg(u) − 1 + E−
Φ (deg(v) − 1 + E−
u ) − γ (deg(u) + E−
v ) − γ (deg(v) + E−
u)
v)
→
+
− γ 1 + E f−→u ,−→v > γ E−
hi, j
deg(u)
deg(v)
→<1
γ E−
h

(22)

(23)
(24)

i, j

(III) When the node vside is shocked at t = 1, the following happens.
(III-a) vside fails at t = 1:
Φ (bvside − ιvside + Evside ) > γ (bvside + Evside ) ≡ Φ (|F| + Evside ) > γ (|F| + Evside ) ≡ Φ > γ
which is same as (17).
(III-b) If a node B j ∈ B is shocked at t = 1, it does not fail:
Φ (bB j − ιB j + EB j ) ≤ γ (bB j + EB j ) ≡ Φ ≤ γ



1
1+
EB j



(25)

(III-c) Any node B j ∈ B fails at t = 2 irrespective of whether B j was shocked or not:
min {Φ (bvside − ιvside + Evside ) − γ (bvside + Evside ), bvside }
> γ (bB j + EB j )
degin (vside )
These constraints are satisfied provided:


Evside
+
E
2
+
γ
B
j
|F|
Φ (bvside − ιvside + Evside ) − γ (bvside + Evside )


> γ (bB j + EB j ) ≡ Φ >
Evside
degin (vside )
1 + |F|
Φ (bvside − ιvside + Evside ) − γ (bvside + Evside ) ≤ bvside ≡ Φ ≤ γ +

32

1

1+

Evside
|F|

(26)

(27)

(III-d) If a node D j ∈ D is shocked at t = 1, it does not fail (and thus, by (III-b), it does not fail at
t = 2 also):


1
Φ (bD j − ιD j + ED j ) ≤ γ (bD j + ED j ) ≡ Φ ≤ γ 1 +
(28)
ED j
(III-e) Any node D j ∈ D fails at t = 3 irrespective of whether D j was shocked or not:


min{Φ (bvside −ιvside +Evside ) − γ (bvside +Evside ),bvside }
− γ (bB j + EB j ), bB j
min
degin (vside )

> γ bD j + ED j ≡
degin (B j )



min {Φ (|F| + Evside ) − γ (|F| + Evside ), |F|}
min
− γ (1 + EB j ), 1 > γ 1 + ED j
|F|

These constraints are satisfied provided all the previous constraints hold and the following holds:



Φ (|F| + Evside ) − γ (|F| + Evside )
(|F| + Evside )
(29)
− γ (1 + EB j ) > γ 1 + ED j ≡ Φ > γ
|F|
3 |F| + |F|EB j + |F|ED j + Evside


1 + EB j
1
Φ (|F| + Evside ) − γ (|F| + Evside )
+
− γ (1 + EB j ) ≤ 1 ≡ Φ ≤ γ 1 +
(30)
E
Ev
v
|F|
1 + side
1 + side
|F|

|F|

→
→
(III-f) Consider a directed path vside ←−B j ←−D j ←−p j from p j = f−
u ,−
v to vside . The maximum
value of its proportion of shock receive by p j from this path, say σ2 , is obtained by shocking all
the nodes vside , B j , D j and is given by (assuming all previous inequalities hold):

σ2 =







Φ (bvside − ιvside + Evside ) − γ (bvside + Evside )




− γ bB j + EB j − Φ bB j − ιB j + EB j , bB j
 min



degin (vside )
− γ bD j + ED j − Φ bD j − ιD j + ED j , bD j
min


degin (B j )




deg (D j )


 

 in
 


Evside
Evside
= min min Φ 1 +
− EB j − γ 2 +
+ EB j , 1 − γ 1 + ED j − ΦED j , 1
|F|
|F|

σ2′ =

Similarly, the minimum value of its proportion of shock receive by p j from this path, say σ2 ,
is obtained by shocking only the node vside and is given by (assuming all previous inequalities
hold):



ι
γ
(b
+
E
)
+
E
)
−
Φ
(b
−
v
v
v
v
v


side
side
side
side
side


− γ bB j + EB j



degin (vside )
− γ bD j + ED j , bD j
min
degin (B j )






deg (D j )
 

 in 


Evside
Evside
= min Φ 1 +
+ EB j − γ 1 + ED j , 1
− γ 2+
|F|
|F|

→
→
→
→
We want node f−
u ,−
v to fail at t = 4 assuming it did not fail already. Since f−
u ,−
v did not fail
→
−
→
−
at t = 2, at most one of the nodes u and v was shocked. There are two cases to consider:
−
→
−
when neither →
u nor −
v was shocked, or when exactly one of these nodes, say →
v , was shocked
(assuming all previous inequalities hold):

33

σ2′ + σ1 =

>





 

Ev
Ev
min Φ 1 + side − γ 2 + side + EB j − γ 1 + ED j , 1
|F|
 |F|



min Φ (n + Evtop − γ n + Evtop ), n
→
min
− γ (deg(u) + E−
u ) , deg(u)
n
+
deg(u)




min Φ (n + Evtop − γ n + Evtop ), n
→
−
− γ (deg(v) + E v ) , deg(v)
min
n
+
deg(v)


γ b f−→u ,−→v + E f−→u ,−→v
≡

+

>

σ2′ + σ1′ +

 





Evside
Evside
min Φ 1 +
+ EB j − γ 1 + ED j , 1
− γ 2+
|F|
|F|


 
Ev
Ev
→
)
,
deg(u)
min Φ 1 + ntop − γ 1 + ntop − γ (deg(u) + E−
u

 


 deg(u)
Evtop
Evtop
→
−
min Φ 1 + n
− γ 1+ n
− γ (deg(v) + E v ) , deg(v)

+


γ 1 + E f−→u ,−→v

deg(v)



→
→
→
→
→
→
min { Φ (b−
v + E−
v ) − γ (b−
v − ι−
v + E−
v ), b−
v }
>
b
+
E
γ
→
−
→
−
→
−
→
−
fu,v
fu,v
→
degin (−
v)
≡
 





Evside
Evside
min Φ 1 +
+ EB j − γ 1 + ED j , 1
− γ 2+
|F|
)
(
 |F|
min Φ (n + Evtop ) − γ (n + Evtop ), n
→
min
− γ (deg(u) + E−
u ) , deg(u)
n

+

deg(u)
→
−
−
→
→
→
−
→
→
+
E
)
−
min { Φ (b−
−
ι
γ
(b
v
v
v
v + E−
v ), b−
v }
→
−

 degin ( v )
γ b f−→u ,−→v + E f−→u ,−→v

+
>

≡

+
+


 




Evside
Evside
min Φ 1 +
+ EB j − γ 1 + ED j , 1
− γ 2+
|F| 
|F| 


 
Evtop
Evtop
→
−
− γ 1+
− γ (deg(u) + E u ) , deg(u)
min Φ 1 +
n
n
deg(u)
→
→
→
−
→
→
min { Φ (deg(−
v ) − 1 + E−
)
−
γ (deg(−
v ) + E−
v
v ), deg( v ) }
→
−
degin ( v )
34

>



γ 1 + E f−→u ,−→v

These constraints are satisfied provided all the previous constraints hold and the following holds:





Evside
Evside
Φ 1+
+ EB j − γ 1 + ED j
− γ 2+
|F| 
|F|


Evtop
Evtop
→
Φ 1+
−γ 1+
− γ (deg(u) + E−
u)
n
n
+

 deg(u) 

Evtop
Evtop
→
−γ 1+
− γ (deg(v) + E−
Φ 1+


v)
n
n
> γ 1 + E f−→u ,−→v
+
deg(v)

Evtop
Evtop
→
→
E−
1
E−
Evside
1
u
v
+
+
+
+
+
+
E
+
+
E
+
E
6
+
→
−
→
−
f
B
D
j
j
u,v

deg(u) n deg(u) deg(u) deg(v) n deg(v) deg(v)
|F|
 (31)
≡ Φ>γ


Evtop
Evtop
Evside
1
1
1+
+
+
+
+
|F|
deg(u) n deg(u) deg(v) n deg(v)



Evside




 3 + |F| + EB j + ED j 

Ev
1
Ev
+
Φ 1 + side − γ 2 + side + EB j − γ 1 + ED j ≤ 1 ≡ Φ ≤ γ 
Evside


Evside
|F|
|F|
1 + |F|
1+
|F|




Φ 1+

Evtop
n





Φ 1+

(32)



Evtop


→
−
+ deg(u) + E u
1+
Ev
deg(u)


n
→
− γ 1 + top − γ (deg(u) + E−
+
u ) ≤ deg(u) ≡ Φ ≤ γ 
Evtop
Evtop
n
1+
1+
n
n
(33)

Evside
|F|





− γ 2+







Ev
Ev
→
Φ 1 + ntop − γ 1 + ntop − γ (deg(u) + E−
u)


Evside
+ EB j − γ 1 + ED j +
|F|
deg(u)
→
−
→
−


→
→
Φ (deg( v ) − 1 + E−
v ) − γ (deg( v ) + E−
v ))
> γ 1 + E f−→u ,−→v
+
→
−
degin ( v )
≡



6 +
Φ>γ


Evside
|F|


Evtop
→
→
E−
E−
+1
v
u
+
+
+ E f−→u ,−→v 
+ EB j + ED j +
n deg(u) deg(u) deg(v)


Evtop
→
Evside
1
E−
v −1
2+
+
+
+
|F|
deg(u) n deg(u) deg(v)

(34)

−
→
→
→
(IV) By (II-b) node hi, j fails at t = 3 provided both the nodes −
u and −
v were shocked at t = 1.
−→
Our goal is to make sure that node hi, j does not fail in any other condition (assuming the node
35

→
→
→
→
itself was not shocked). Assuming the nodes −
u,−
v and f−
u ,−
v were not shocked, the maximum
−→
→
→
→
→
amount of shock that f−
u ,−
v ∈ Fi, j can receive is when all the nodes before f−
u ,−
v in the path
→ −
−
→
vside ←−B j ←−D j ←−p j ←− f−
→
→
u ,−
v were shocked and no more than one of the nodes u or v was
−
→
shocked. Based on this, the following constraints must hold for hi, j not to fail.




o
n
→ + E−→
γ b−
min σ1 + σ2 − γ b f−→u ,−→v + E f−→u ,−→v , b f−→u ,−→v
hi, j
hi, j
≤
→
→
degin ( f−
|Fi, j |
u ,−
v)
≡

min

(
+



min Φ (n + Evtop ) − γ (n + Evtop ), n
→
−
min
− γ (deg(u) + E u ) , deg(u)
n


deg(u)


min Φ (n + Evtop ) − γ (n + Evtop ), n
→
− γ (deg(v) + E−
min
v ) , deg(v)
n




deg(v)
 
 




Evside
Ev
− EB j − γ 2 + side + EB j , 1 − γ 1 + ED j − ΦED j , 1
+ min min Φ 1 +
|F|
) |F|




− γ 1 + E f−→u ,−→v , 1

≤

→
γ E−
h
i, j

|Fi, j |

≡

(


Evtop
Evtop
1
1
+
+
+
min Φ
deg(u) n deg(u) deg(v) n deg(v)


Evtop
Evtop
→
→
E−
1
E−
1
u
v
+
+
+
+
+
+ E f−→u ,−→v
−γ 3+
deg(u) n deg(u) deg(u) deg(v) n deg(v) deg(v)
)
 


 
→
γ E−
Ev
Ev
hi, j
+ min Φ 1 + side − EB j + ED j − γ 3 + side + EB j + ED j , 1 , 1
≤
|F|
|F|
|Fi, j |


These constraints are satisfied provided all the previous constraints hold and the following holds:




Ev
Ev
Φ 1 + side − EB j + ED j − γ 3 + side + EB j + ED j ≤ 1
|F|
|F|


Evside
3
+
+
E
+
E
Bj
Dj 

1
|F|
+
≡ Φ≤γ


Ev
Ev
1 + side − EB j + ED j
1 + side − EB j + ED j
|F|
|F|

36

(35)


Evtop
Evtop
→
→
E−
1
E−
Evside
1
u
v
 6 + deg(u) + n deg(u) + deg(u) + deg(v) + n deg(v) + deg(v) + E f−→u ,−→v + |F| + EB j + ED j 

Φ≤γ


Evtop
Evtop
1
Evside
1
+
+
+
+
− EB j + ED j
1+
deg(u) n deg(u) deg(v) n deg(v)
|F|
1
+
Evtop
Evtop
1
Ev
1
+
+
+
+ side − EB j + ED j
1+
deg(u) n deg(u) deg(v) n deg(v)
|F|



→
E−
Evtop
Evtop
→
→
1
E−
1
E−
Evside
hi, j
u
v
 6 + deg(u) + n deg(u) + deg(u) + deg(v) + n deg(v) + deg(v) + E f−→u ,−→v + |F| + EB j + ED j + |F | 

i, j 
Φ≤γ

Evtop
Evtop
1
1
Evside


1+
+
+
+
+
− EB j + ED j
deg(u) n deg(u) deg(v) n deg(v)
|F|


(37)

→
→
→
On the other hand, if exactly one of the nodes −
u or −
v , say −
u , was shocked at t = 1, then the
−→
→
−
→
−
maximum amount of shock that f u , v ∈ Fi, j can receive is is modified, and the new conditions
for our desired goal become as follows.






→
→
→
→
→
→
min { Φ (b−
v + E−
v ), b−
v }
v + E−
v ) − γ (b−
v − ι−
′
min σ1 +
+ σ2 − γ b f−→u ,−→v + E f−→u ,−→v , b f−→u ,−→v
−→ + E−→
→
−
b
γ
degin ( v )
hi, j
hi, j
≤
→
→
−
degin ( f−
|F
|
)
i, j
u,v
≡

min

(

min

(

)



min Φ n + Evtop − γ n + Evtop , n
→
− γ (deg(u) + E−
u ) , deg(u)
n
deg(u)

→
→
→
→
→
→
min { Φ (b−
v + E−
v ) − γ (b−
v − ι−
v + E−
v ) , b−
v }
→
−

  

  degin ( v ) 
 

Ev
Ev
+ min min Φ 1 + side − EB j − γ 2 + side + EB j , 1 − γ 1 + ED j − ΦED j , 1
|F|
) |F|

+



− γ 1 + E f−→u ,−→v , 1

min

(

≤

→
γ E−
h
i, j

|Fi, j |

≡




Evtop
Evtop
→
→
→
1
E−
E−
E−
1
1
v
u
v
+
−
+
+
+
+
−γ 2+
Φ 1+
deg(u) n deg(u) deg(v) deg(v)
deg(u) n deg(u) deg(u) deg(v)


 


 


Evside
Evside
+ min min Φ 1 +
− EB j − γ 2 +
+ EB j , 1 − γ 1 + ED j − ΦED j , 1
|F|
) |F|




−γ 1 + E f−→u ,−→v , 1

≤

→
γ E−
h
i, j

|Fi, j |

37

(36)

These constraints are satisfied provided all the previous constraints hold and the following holds:



Φ 1+





Evside
Ev
− EB j − γ 2 + side + EB j
|F|
|F|







Evside
|F|

+ EB j 
 2+
1
+
≤1 ≡ Φ≤γ


Evside
Evside
1+
1+
− EB j
− EB j
|F|
|F|

(38)








Evside
Evside
Φ 1+
− EB j − γ 2 +
+ EB j − γ 1 + ED j − ΦED j ≤ 1
|F|
|F|


Evside
+
E
+
1
+
E
2
+
B
D
j
j

1
|F|
+
≡ Φ≤γ


Evside
Evside
− EB j + ED j
− EB j + ED j
1+
1+
|F|
|F|

(39)




Evtop
Evtop
→
→
→
1
1
E−
E−
E−
1
v
u
v
+
−
+
+
+
+
−γ 2+
Φ 1+
deg(u) n deg(u) deg(v) deg(v)
deg(u) n deg(u) deg(u) deg(v)




→

 γ E−


Evside
Evside
hi, j
+Φ 1 +
− EB j − γ 2 +
+ EB j − γ 1 + ED j − ΦED j − γ 1 + E f−→u ,−→v ≤
|F|
|F|
|Fi, j |


≡


→
γ E−
Evtop
→
→
1
E−
E−
Evside
hi, j
u
v
 6 + deg(u) + n deg(u) + deg(u) + deg(v) + |F| + EB j + E f−→u ,−→v + ED j + |F | 

i, j 
Φ≤γ

E
→
−
1
Ev
Ev
1

vtop

+
−
+
+ side − EB j + ED j
2+
deg(u) n deg(u) deg(v) deg(v)
|F|


(40)






Evtop
Evtop
→
→
→
1
1
1
E−
E−
E−
v
u
v
Φ 1+
+
−
+
+
+
+
−γ 2+
deg(u) n deg(u) deg(v) deg(v)
deg(u) n deg(u) deg(u) deg(v)








Ev
Ev
+Φ 1 + side − EB j − γ 2 + side + EB j − γ 1 + ED j − ΦED j − γ 1 + E f−→u ,−→v ≤ 1
|F|
|F|

Evtop
→
→
E−
E−
Evside
1
u
v
 6 + deg(u) + n deg(u) + deg(u) + deg(v) + |F| + EB j + E f−→u ,−→v + ED j 

Φ≤γ


Evtop
→
1
E−
Evside
1
v
+
−
+
+
− EB j + ED j
2+
deg(u) n deg(u) deg(v) deg(v)
|F|
1
+
Evtop
→
1
E−
Ev
1
v
+
−
+
+ side − EB j + ED j
2+
deg(u) n deg(u) deg(v) deg(v)
|F|

(41)



≡

(42)

There are many choices of parameters γ , Φ and Ey ’s satisfying inequalities (17)–(26); we exhibit just one:

γ = 4 n−1000

Φ = n−1000

∀ u ∈ V left ∀ v ∈ V right : E f−→u ,−→v = 1

→
∀ u ∈ V left ∪V right : E−
u =1

Evtop = n3

→=1
∀ hi, j ∈ Fsuper ∀ fu,v ∈ Fi, j : E−
h
i, j

38

Evside = n2 |F|
1
∀ j : EB j = EB j =
4

Remembering that 10 ≤ deg(u) < n for any node u ∈ V left ∪V right and |Fi, j | < |F|, it is relatively straightforward to verify that all the inequalities are satisfied for all sufficiently large n. Note that
E = Evtop + Evside +

∑ E−→u +

u ∈V left ∪V right

∑ E f−→u ,−→v +

{u,v}∈F

∑ E−h→ +

hi, j ∈ Fsuper

i, j

|F|

∑

j=1

EB j + ∑ ED j



3
= n3 + n2 |F| + n + |F| + |Fsuper |
2

and thus the ratio of total external assets to total internal assets E/I is large. We can now finish our proof by
→
−
selecting δ such that log1−δ n = log1−ε | V | − 1 and showing the following:
−
→ 
(completeness) If M INREP has a solution of size α + β on G then SI∗ G , T ≤ α + β + 2.
(soundness) If every solution of M INREP on G is of size at least (α + β )2log
→
−  α + β log1−δ n
2
SI∗ G , T ≥
.
2

1−δ

n

then

Proof of Completeness (M INREP has a solution of size α + β )
Let V1 ⊆ V left and V2 ⊆ V right be a solution of M INREP such that |V1 | + |V2 | = α + β . We shock the nodes
→
u for every u ∈ V left ∪ V right . By (I-a) vtop fails at t = 1, and by (I-b) and
vtop and vside , and every node −
S
right
β
(II-a) every node in ∪αi=1Vileft ∪ j=1V j
fails on or before t = 2. By (III-a), (III-b) and (III-c) every node
in {Vshock } ∪ B ∪ D fails on or before t = 3. Since V1 and V2 are a valid solution of M INREP , for every
super-edge hi, j there exists u ∈ V1 and v ∈ V2 such that u ∈ Vileft , v ∈ V jright and {u, v} ∈ F; since we shock
→
−
→
→
→−
→ fails at t = 2, and by
the nodes −
u and →
v , by (II-a) both −
u and −
v fail at t = 1, by (II-b) the node f−
→ u, v
−→
→
−
∗ −
(II-c) the node hi, j fails at t = 3. Thus, the network G fails at t = 3 and SI G , T = α + β + 1 for t ≥ 4.
1−δ

Proof of Soundness (every solution of M INREP is of size at least (α + β )2log

n)

−
→ 
We will prove the logically equivalent contrapositive of our claim, i.e., we will show that if SI∗ G , T <
α +β
2

1−δ

1−δ

then M INREP has a solution of size strictly less than (α + β )2log n . Consider a solution of
→
−
1−δ
S TABT,Φ on G that shocks at most z = α +2 β 2log n nodes. Note that the nodes vtop and vside must be shocked
at t = 1 by Proposition 7.1(a). By (I-a) and (III-a), the nodes vtop and vside fails at t = 1, by (I-b) and (III-c)
−−→ −−−→
every node in V left ∪ V right ∪ B fails at t = 2, by (III-e) every node in D fails at t = 3, by (III-f) every node
−
→
−→
−→
→
→
f−
u ,−
u fails at t = 4 unless it was shocked at t = 1 and by (IV) a node hi, j fails only if hi, j , fovru,ovru ∈ Fi, j or
→
→
both the nodes −
u and −
v were shocked at t = 1. We “normalize” this given solution in the following manner
(each step of the normalization assumes that the previous steps have been already carried out):
2log

n

• If a node from D ∪ B was shocked at t = 1, we do not shock it. By (III) this has no effect on the failure
of the network.
−→
→
−
→
−
→
→
• If a node f−
u ,−
v ∈ Fi, j was shocked, we do not shock it but instead shock the nodes u and v if they
were not already shocked in the given solution. This at most doubles the number of nodes shocked
−
→
and, by (II-b), the node fu,v fails at t = 2 and the node hi, j fails at t = 3 if it was not shocked at t = 1.
→
→
Thus, after this sequence of normalization steps, we may assume that no f−
u ,−
v node was shocked.
39

−→
→
→
• If a node hi, j was shocked at t = 1, we do not shock it but instead shock the nodes −
u and −
v (for
some u and v such that {u, v} ∈ Fi, j ) if they were not already shocked in the given solution. This at
−→
most doubles the number of nodes shocked and, by (II-b), the node fu,v fails at t = 2 and the node hi, j
−→
fails at t = 3. Thus, after this sequence of normalization steps, we may assume that no hi, j node was
shocked.
These normalizations result in a solution of S TABT,Φ of size at most 2 z in which the nodes vtop , vside , a
−−
→
→ −−→
−
→ −
−
→
−
→
subset V1 ⊆ V left and a subset V2 ⊆ V right of nodes. Our solution of M INREP is V1 = { v | −
v ∈ V1 } ⊆ V left
−→
→
−
→
and V2 = { v | −
v ∈ V2 } ⊆ V right of size 2z − 2 < 2z. Since failure of every hi, j is attributed to shocking two
−
→
→
→
→
→
nodes −
u and −
v such that f−
u ,−
v ∈ Fi, j , every super-edge hi, j of G is witnessed by the two nodes u and v. 

15 Homogeneous Networks, D UAL -S TABT,Φ,κ , any T , hardness and exact
algorithm
Theorem 15.1.
−1
, for any
(a) Assuming P , NP, DSI∗ (G, T, κ ) cannot be approximated within a factor of 1 − e −1 + δ
δ > 0, even if G is a DAG (e is the base of natural logarithm).


κ 
Φ
1 + degmax
(b) If G is a rooted in-arborescence then DSI∗ (G, T, κ ) <
−
1
, where degmax
in
in = maxv∈V {degin (v)}
γ
n
is the maximum in-degree over all nodes of G. Moreover, under the assumption that any individual node of
the network can be failed by shocking, DSI∗ (G, T, κ ) can be computed exactly in O(n3 ) time.
Proof.
(a) The max κ -cover problem is defined as follows. An instance of the problem is an universe U of n
elements, a collection of m sets S over U , and a positive integer κ . The goal is to pick a sub-collection
S ′ ⊆ S of κ sets such that the number of elements covered, namely ∪S∈S ′ S , is maximized. Let OPT
denote the maximum number of elements covered by an optimal solution of the max κ -cover problem. It
was shown in [28] that, assuming P , NP, the max κ -cover problem cannot be approximated within a factor
1
 for any constant δ > 0. More precisely, [28] provides a polynomial-time reduction for a
of
1 − e1 + δ
restricted but still NP-hard version of the Boolean satisfiability problem (3-CNF5) instances of max κ -cover
α
with κ = U , for some constant 0 < α < 1, and shows that
(1) if the CNF formula is satisfiable, then OPT = U ;


1
(2) if the CNF formula is not satisfiable, then OPT < 1 − + g(κ ) U , where g(κ ) → 0 as κ → ∞.
e
Our reduction from max κ -cover to D UAL -S TABT,κ is as follows4 . In our graph G = (V, F), we have an
element node ũ for every element u ∈ U , a set node S̃ for every set S ∈ S , and directed edges (ũ, S̃) for
every element u ∈ U and set S ∈ S such that u ∈ S. Thus, n = |V | = |U | + |S | and |F| = ∑S∈S |S|. We
now set the remaining parameters as follows: E = n, γ = n−2 and Φ = 1. Now, we observe the following:

• If an element node ũ is shocked, it does not fail since Φ degin (ũ) − degout (ũ) + En ≤ 0 whereas

γ degin (ũ) + En = n−2 > 0.
4 However,

this exact construction will not work in the proof of Theorem 8.1 since the entire network needs to fail in that proof.

40

• If a set node S̃ is shocked,


γ degin S̃ + En ≤ n+1
< 1.
n2




it fails since Φ degin S̃ − degout S̃ + En ≥ 2 whereas

• If a set node S̃ is shocked, then every element node ũ for u ∈ S fails at t = 2. To observe this, note that






min Φ degin S̃ − degout S̃ + En − γ degin (ũ) + En , degin S̃

degin S̃


 E
2 − n+1
n+1
n2
> 2 ≥ γ degin S̃ +
≥
n
n
n

• Since the longest directed path in G has one edge, no new nodes fails during t > 2.
Based on the above observations, one can identify the sets selected in max k-cover with the set nodes selected
for shocking in D UAL -S TABT,κ on G to conclude that DSI∗ (G, T, κ ) = OPT + κ . Thus, using (1) and (2),
inapproximability gap is
α

U +κ
U + U


=
1
1 − e + g(κ ) U + κ
1 − e1 + g(κ ) U + U

α

→

1
1 − e1 + δ

as U → ∞ for any δ > 0

(b) Using Lemma 11.4, we have

κ
DSI (G, T, κ ) <
∗



n

max iz(u)
u∈V

n

o

κ
<
n



1 + degmax
in




Φ
−1
γ

To provide a polynomial time algorithm for DSI∗ (G, T, κ ), we suitably modify the algorithm described in
the proof of Theorem 11.1. We redefine SI∗S A NS (G, T, u, v) and SI∗S A S (G, T, u) in the following manner:
• For every node u′ ∈ ∇(u) and every integer 0 ≤ k ≤ κ , DSI∗S A NS (G, T, u, u′ , k) is the number of nodes
in an optimal solution of D UAL -S TABT,Φ,κ (or ∞ if there is no feasible solution of D UAL -S TABT,Φ,κ )
for the subgraph induced by the nodes in ∆(u) assuming the following:
– u′ was shocked,
– u was not shocked,
– no node in the path u′ { u except u′ was shocked, and
– total number of shocked nodes in ∆(u) is exactly k.
• For every integer 0 ≤ k ≤ κ , DSI∗S A S (G, T, u, k) is the number of nodes in an optimal solution of
D UAL -S TABT,Φ,κ for the subgraph induced by the nodes in ∆(u) (or ∞, if there is no feasible solution
of S TABT,Φ under the stated conditions) assuming that the node u was shocked (and therefore failed),
and the number of shocked nodes in ∆(u) is exactly k.
Computing these quantities becomes slightly more computationally involved as shown below.
Computing DSI∗S A S (G, T, u, k) when degin (u) = 0:
DSI∗S A S (G, T, u, 1) = 1 and DSI∗S A S (G, T, u, k) = −∞ for any k , 1.

Computing DSI∗S A NS (G, T, u, u′ , k) when degin (u) = 0:
41

• If u ∈ iz(u′ ) then shocking node v makes node u fail. Thus, SI∗S A NS (G, T, u, u′ , 1) = 1 and
SI∗S A NS (G, T, u, u′ , k) = −∞ for any k , 1.
• Otherwise, node u does not fail. Thus, DSI∗S A NS (G, T, u, u′ ) = −∞.

Computing DSI∗S A S (G, T, u) when degin (u) > 0: In this case we have
DSI∗S A S (G, T, u, k) = 1 +

min

k1 +k2 +···+kdegin (u) =k−1

(

k

∑ min

i=1

n

DSI∗S A S (G, T, vi , ki ), DSI∗S A NS (G, T, vi , u, ki )

o

)

Computing DSI∗S A NS (G, T, u, u′ , k) when degin (u) > 0: Since u′ is shocked and u is not shocked, the following cases arise:
• If u < iz(u′ ) then then u does not fail. Then,
DSI∗S A NS (G, T, u, u′ , k) =

min

k1 +k2 +···+kdegin (u) =k

(

degin (u)

∑

n

min DSI∗S A S (G, T, vi , ki ), SI∗S A NS (G, T, vi , u′ , ki )

i=1

o

)

• Otherwise, u ∈ iz(u′ ), and therefore u fails when u′ is shocked. Then,
DSI∗S A NS (G, T, u, u′ , k) = 1 +

min

k1 +k2 +···+kdegin (u) =k

(

degin (u)

∑

min

i=1

n

DSI∗S A S (G, T, vi , ki ),

DSI∗S A NS (G, T, vi , u′ , ki )

o

)

It only remains to(
show how we compute
)
degin (u)
n
o
min
∑ min DSI∗S AS (G, T, vi , ki ), DSI∗S ANS (G, T, vi , u′ , ki ) for ̥ ∈ {k − 1, k} in polyk1 +k2 +···+kdegin (u) =̥

i=1

nomial time. It is easy to cast this problem as an instance of the unbounded integral knapsack problem in
the following manner:
• We have degin (u) objects O1 , O2 , . . . , Odegin (u) , each of unlimited supply and weight 1.
• The cost of selecting ki objects of the type Oi is
n
o
min DSI∗S A S (G, T, vi , ki ), DSI∗S A NS (G, T, vi , u′ , ki )
• The goal is to select a total of exactly ̥ objects such that the total cost is minimum.
The standard pseudo-polynomial time dynamic programming algorithm for Knapsack can be used to solve



the above instance in O k degin (u) = O n2 time. Thus, the total running time of our algorithm is O n3 .


42

16 Heterogeneous Networks, D UAL -S TAB2,Φ,κ , Stronger Inapproximability
We show that DSI∗ (G, 2, κ ) cannot be approximated within a large approximation factor provided a complexitytheoretic assumption is satisfied. To understand this assumption, we recall the following definitions from [6].
A random (m, n, d) hyper-graph H is a random hyper-graph of n nodes, m hyper-edges each having
having exactly d nodes obtained by choosing each hyper-edge independently and uniformly at random. For
our purpose, assume that d is a constant, and m ≥ nc for some constant c > 3. Let Q : {0, 1}d 7→ {0, 1} denote
a d-ary predicate, and let FQ,m be a distribution over d-local functions from {0, 1}n to {0, 1}m by defining
the random d-local function fH,Q : {0, 1}n 7→ {0, 1}m to be the function whose ith output is computed by
applying the predicate Q to the d inputs that are indexed by the ith hyper-edge of H. Finally, the κ densest
sub-hypergraph problem (DSκ ) is defined as follows: given an hyper-graph G = (V, F ) with n = |V | and
m = |F| such that every hyper-edge contains exactly d nodes and an integer κ > 0, select a subset V ′ ⊆ V

of exactly κ nodes which maximizes {u1 , u2 , . . . , ud } ∈ F | u1 , u2 , . . . , ud ∈ V ′ .
The essence of the complexity-theoretic assumption is that if, for a suitable choice of Q, FQ,m is a
collection of one-way functions, then DSκ is hard to approximate. More precisely, the assumption is:
c−3
√
(⋆⋆) If FQ,m is 1/o(1/ n log n)-pseudorandom, then for κ = n1− 2d for some constant c > 3 there exists
instances G = (V, F) of DSκ with m ≥ nc such that it is not possible to decide in polynomial time if there
(1 + o(1)) m
is a solution of DSκ with at least (c−3)
edges (the “yes” instance), or if every solution of DSκ has
1
n 2 (1− d )
(1 − o(1)) m
at most
edges (the “no” instance).
c−3
n 2
Theorem 16.1. Under the technical assumption (⋆⋆), DSI∗ (G, 2, κ ) cannot be approximated within a ratio
of nδ for some constant δ > 0 even if G is a DAG.
→
−
→−
−
→
Proof. Given an instance G = (V, F) of DSκ as stated in (⋆⋆), we construct an instance graph G = ( V , F )
as follows:
→
−
→
• For every node u ∈ V , we have a node −
u ∈ V , and for every edge e = {u1 , u2 , . . . , ud } ∈ F, we have a
−
−
−
−
−
−
−
−
−
−
→
→ −
−
→
−
→
−
node →
e (also denoted by {u1 , u2 , . . . , ud } ) in V . Thus, the total number of nodes of G is | V | = m + n.

→
−
• For every hyper-edge e = (u1 , u2 , . . . , ud ) ∈ F, we have d edges (e, u1 ), (e, u2 ), . . . , (e, ud ) ∈ F . We set
the weight (share of internal asset) of every edge (e, ui ) to 2. Thus, |I| = 2dm.

→
−
→
→
→ E−
−
→
Let the share of external assets for a node (bank) −
y ∈ V be denoted by E−
→
y (thus, ∑−
y = E). We
y ∈V
→
will select the remaining network parameters as follows. For each e ∈ F, E−
=
1.99d,
and
for
each u ∈ V ,
e
1
→
E−
u = 0. Thus, E = 1.99dm. Finally, we set Φ = 1 and γ = /2. We prove the following:

1 + o(1) m
(completeness) If DSκ has a solution with α ≥
hyper-edges then then
c−3
1
n 2 (1− d )

−
→
DSI∗ G , 2, κ ≥ κ + α .
(soundness) If every solution of DSκ has at most β =

−
→
DSI∗ G , 2, κ ≤ κ + β .

43


1 − o(1) m
n

c−3
2

hyper-edges then

Note that with c = 5 (and, thus m ≥ n5 ), and sufficiently large d and n, we have


1+o(1) m
c−3
1+o(1) m
1
1−
1−
n 2d + c−3 1− 1
n d+
1
 1
κ +α
n 2 ( d )
n1− d 
≥ 1 − o(1) n /d
=
=
κ +β
1−o(1) m
1−o(1) m
c−3
1
n1− 2d +
n1− d +
c−3
n
n

2

which proves the theorem with δ = 1/d .

Proof of Completeness (DSκ has a solution with α hyper-edges)
→
Let V ′ ⊆ V be a solution of DSκ with at least α hyper-edges. We shock all the nodes in Vshock = {−
u | u ∈ V ′ }.
→
−
→
−
→
−
→
→
→
→
→
Every shocked node u fails at t = 1 since Φ (b−
u + E−
u ) = 2 degin ( u ) > degin ( u ) = γ (b−
u + E−
u ).
u − ι−
→
−
′
Now, consider a hyper-edge e = (u1 , u2 , . . . , ud ) ∈ F such that u1 , u2 , . . . , ud ∈ V . Then, the node e fails at
t = 2 since



d min Φ b−
→
→
→
→
→
→
ui + E−
ui − γ b−
ui + E−
ui , b−
ui
ui − ι−
→
→
= d > 0.995d = γ (b−
∑
e + E−
e)
−
→
deg
(
u
)
in i
i=1

Proof of Soundness (every solution of DSκ has at most β hyper-edges)
−

→
We will prove the logically equivalent contrapositive of our claim, i.e., we will show that if DSI∗ G , 2, κ >
β + κ then DSκ has a solution of with strictly more than β hyper-edges. First, note that we can assume
→
without loss of generality that, for any hyper-edge e ∈ F, the node −
e is not shocked. Otherwise, if we shock
→
→
→
−
→
−
→
→
node −
e , then it does not fail since at t = 1 since Φ (b−
−
+
E
ι
e
e
e ) = −0.01d < 0.995d = γ (b−
e + E−
e ),
→
−
and in fact doing so increases its equity to 1.005d. Since the equity of e increased by shocking it, if this
node failed in the given solution then it would also fail if it was not shocked. So, we can instead shock a
→
node −
u that was not shocked in the given solution; such a node must exist since κ < n.
Note that we have already shown in the proof of the completeness part that, for any e = (u1 , u2 , . . . , ud ) ∈
→
→
→
→
F, if the d nodes −
u1 , −
u2 , . . . , −
ud are shocked then −
e fails at t = 2. Thus, our proof is complete provided we
→
−
→
→
→
show that such a node e does not fail at t = 2 if at least one of the nodes −
u1 , −
u2 , . . . , −
ud is not shocked. Let
→
−
→
−
→
−
→
−
S ⊂ { u1 , u2 , . . . , ud } be the set of shocked nodes among these d nodes. Then, e does not fail at t = 2 since



→
→
→
→
→
→
min Φ b−
ui + E−
ui − γ b−
ui − ι−
ui + E−
ui , b−
ui
→
→
≤ d − 1 ≤ 0.995d = γ (b−
∑
e + E−
e)
→
−
deg
(
u
)
in i
ui ∈S
for all sufficiently large d.



17 Software Availability
An interactive software (called FIN-STAB) implementing an expanded version of the shock propagation
algorithm shown in Table 1 is available from the website
http://www2.cs.uic.edu/˜dasgupta/financial-simulator-files

44

18 Conclusions
In this paper, we have formalized a model for idiosyncratic propagation of shocks to a banking network,
defined two possible stability measures, provided their computational properties and discussed the implications of our results on the banking system. We view our work as a necessary first step towards understanding
vulnerabilities of banking systems due to sudden loss of external assets, and hope that it will generate sufficient interests in both the banking network community and the network algorithms community to further
investigate and refine these stability issues.

Acknowledgements
The authors would like to thank the organizers of the Industrial-Academic Workshop on Optimization in
Finance and Risk Management at the Fields Institute in Toronto (Canada) for an opportunity to discuss
some of the results in this paper and receive valuable feedbacks.

References
[1] F. Allen and A. Babus. Networks in Finance, in Network-based Strategies and Competencies, P. Kleindorfer and J. Wind (eds.), 367-382, Wharton School Publishing, 2009.
[2] F. Allen and D. Gale. Financial Contagion, Journal of Political Economy, 108 (1), 1-33, 2000.
[3] P. Alimonti and V. Kann. Some APX-completeness results for cubic graphs, Theoretical Computer
Science, 237 (1-2), 123-134, 2000.
[4] F. Allen and D. Gale. Financial contagion, Journal of Political Economy, 108 (1), 1-33, 2001.
[5] H. Amini, R. Cont and A. Minca. Resilience to contagion in financial networks, arXiv:1112.5687v1,
December 2011.
[6] B. Applebaum. Pseudorandom Generators with Long Stretch and Low locality from Random Local
One-Way Functions, 44th ACM Symposium on Theory of Computing, 805-816, 2012.
[7] A. Babus. The Formation of Financial Networks, Tinbergen Institute Discussion Paper No. 2006-093/2;
FEEM Working Paper No. 69.2007, 2007.
[8] A. Babus. Contagion Risk in Financial Networks, in K. Liebscher (ed.), Financial Development, Integration and Stability, 423-440, 2006.
[9] R. Bar-Yehuda and S. Moran. On approximation problems related to the independent set and vertex
cover problems, Discrete Applied Mathametics, 9, 1-10, 1984.
[10] P. Berman and M. Karpinski. On some tighter inapproximability results, Further Improvements, Electronic Colloquium on Computational Complexity, Technical Report TR98-029, 1998.
[11] L. Blume, D. Easley, J. Kleinberg, R. Kleinberg and E. Tardos. Which Networks Are Least Susceptible
to Cascading Failures?, 52nd IEEE Annual Symposium on Foundations of Computer Science, 393402, 2011.
45

[12] L. Blume, D. Easley, J. Kleinberg, R. Kleinberg and E. Tardos. Network Formation in the Presence of
Contagious Risk, 12th ACM conference on Electronic commerce, 1-10, 2011.
[13] A. Borodin, Y. Filmus and J. Oren. Threshold models for competitive influence in social networks, 6th
international conference on Internet and network economics, 539-550, 2010.
[14] C. W. Calomiris and G. Gorton. The Origins of Banking Panics: Models, Facts, and Bank Regulation,
in Financial Markets and Financial Crises, R. G. Hubbard (Eds.), 109-174, University of Chicago
Press, 1991.
[15] F. Castiglionesi and N. Navarro. Optimal Fragile Financial Networks, Tilburg University Discussion
Paper no. 2007-100. Tilburg, The Netherlands: Tilburg University, 2007.
[16] N. Chen. On the approximability of influence in social networks, 19th annual ACM-SIAM symposium
on Discrete algorithms, 1029-1037, 2008.
[17] W. Chen, Y. Wang and S. Yang. Efficient influence maximization in social networks, 15th ACM
SIGKDD international conference on Knowledge discovery and data mining, 199-208, 2009.
[18] F. C. Coelho, O. G Cruz and C. T Codeo Epigrass: a tool to study disease spread in complex networks,
Source Code for Biology and Medicine, 3 (3), 2008.
[19] R. Cont, A. Moussa and E. B. Santos. Network Structure and Systemic Risk in Banking Systems, Working paper, December, 2010.
[20] J. Corbo and G. Demange. Contagion in Financial Networks: A Random Graph Model, 3rd financial
Risks International Forum, Paris, France, 2010.
[21] B. Dasgupta. Capital Accumulation in the Presence of Informal Credit Contracts: Does the Incentive
Mechanism Work Better than Credit Rationing Under Asymmetric Information?, Working papers 200432, University of Connecticut, Department of Economics, 2004.
[22] B. DasGupta and L. Kaligounder. Global Stability of Financial Networks Against Contagion: Measure,
Evaluation and Implications, arXiv:1208.3789v1, 2012.
[23] D. W. Diamond and P. H. Dybvig. Bank runs, deposit insurance and liquidity, Journal of Political
Economy, 91, 401-419, 1983.
[24] G. Dobson. Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative
Data, Mathematics of Operations Research, 7 (4), 515-531, 1982.
[25] M. Eboli. Systemic Risk in Financial Network: a Graph Theoretical Approach, Mimeo, Univ. di Chieti,
Pescara, 2004.
[26] S. Eubank. Network based models of infectious disease spread, Japanese Journal of Infectious Diseases, 58, S19-S13, 2005.
[27] S. Eubank, H. Guclu, V. S. A. Kumar, M. V. Marathe, A. Srinivasan, Z. Toroczkai, and N. Wang.
Modeling Disease Outbreaks in Realistic Urban Social Networks, Nature, 429, 180-183, 2004.

46

[28] U. Feige. A threshold of ln n for approximating set cover, Journal of the ACM, 45, 634-652, 1998.
[29] I. Fisher. The Debt-Deflation Theory of Great Depressions, Econometrica, 1, 337-357, 1933.
[30] X. Freixas, B. M. Parigi and J.-C. Rochet. Systemic risk, interbank relations, and liquidity provision
by the central bank, Journal of Money, Credit and Banking, 32(3), 611-638, 2000.
[31] C. H. Furfine. Interbank exposures: Quantifying the risk of contagion, Journal of Money, Credit and
Banking, 35 (1), 111-128, 2003.
[32] P. Gai and S. Kapadia. Contagion in financial networks, Proc. R. Soc. A, 466 (2120), 2401-2423, 2010.
[33] D. Gale and S. Kariv. Financial networks, American Economic Review, 99-103, 2007.
[34] A. Haldane. Why Banks Failed the Stress Test, speech given at the Marcus-Evans Conference on StressTesting, 9-10 February 2009, available at http://www.bankofengland.co.uk/publications/
speeches/2009/speech374.pdf.
[35] C. Iazzetta and M. Manna. The Topology of the Interbank Market Developements in Italy Since 1990,
Bank of Italy Temi di Discussione (Working Paper) No. 711, 2009.
[36] D. Kempe, J. Kleinberg and E. Tardos. Maximizing the spread of influence through a social network,
9th ACM SIGKDD international conference on Knowledge discovery and data mining, 137-146, 2003.
[37] J. M. Keynes. The General Theory of Employment, Interest, and Money, New York: Harcourt, Brace
and Company, 1936.
[38] S. Khuller, A. Moss and J. Naor. The budgeted maximum coverage problem, Information Processing
Letters, 70 (1), 39-45, 1999.
[39] P. R. Kleindorfer, Y. Wind and R. E. Gunther. The Network Challenge: Strategy, Profit and Risk in an
Interlinked World, Pearson Prentice Hall, 2009.
[40] G. Kortsarz, R. Krauthgamer and J. R. Lee. Hardness of Approximating Vertex-Connectivity Network
Design Problems, SIAM Journal of Computing, 33 (3), 704-720, 2004.
[41] R. Lagunoff and S. Schreft. A Model of Financial Fragility, Journal of Economic Theory, 99 (1-2),
220-264, 2001.
[42] F. R. Liedorp, L. Medema, M. Koetter, R. H. Koning and I. van Lelyveld. Peer monitoring or contagion? Interbank market exposure and bank risk, DNB working paper No. 248, 2010.
[43] Y. Leitner. Financial Networks: Contagion, Commitment, and Private Sector Bailouts, Journal of
Finance, 60, 2925-2953, 2005.
[44] H. Minsky. A Theory of Systemic Fragility, in Financial Crises: Institutions and Markets in a Fragile
Environment, E. I. Altman & A. W. Sametz (eds.), John Wiley & Sons, 1977.
[45] P. E. Mistrulli. Assessing fiancial contagion in the interbank market: Maximum entropy versus observed interbank lending patterns, Bank of Italy Research, 2007.

47

[46] E. Nier, J. Yang, T. Yorulmazer and A. Alentorn. Network models and financial stability, Journal of
Economics Dynamics and Control, 31, 2033-2060, 2007.
[47] R. Raz. A parallel repetition theorem, SIAM Journal of Computing, 27 (3), 763-803, 1998.
[48] D. Stauffer and A. Aharony. Introduction to Percolation Theory, 2nd edition, CRC Press, 1994.
[49] C. Upper and A. Worms. Estimating bilateral exposures in the german interbank market: Is there a
danger of contagion?, European Economic Review, 48 (4), 827-849, 2004.
APPENDIX
For the benefit of the reader, we provide explanations for a few finance terminologies frequently used in
this paper.
External asset: refers to the case of financial institutions borrowing from investors and similar outside
entities.
Interbank exposure: refers to the case of financial institutions borrowing from other financial institutions.
Net worth or equity: a fixed proportion of the total asset of a bank. In general, higher equity imply better
stability for an individual bank.

48

