[1]David C. Kutner

Partially supported by the EPSRC grant EP/P020372/1.

1]Department of Computer Science, Durham University, Upper Mountjoy Campus,
Stockton Road, Durham DH1 3LE, UK

# Payment Scheduling in the Interval Debt Model

Tom Friedetzky<EMAIL_ADDRESS><EMAIL_ADDRESS>George
B. Mertzios<EMAIL_ADDRESS>Iain A. Stewart
<EMAIL_ADDRESS>Amitabh Trehan<EMAIL_ADDRESS>[

###### Abstract

The network-based study of financial systems has received considerable
attention in recent years but has seldom explicitly incorporated the dynamic
aspects of such systems. We consider this problem setting from the temporal
point of view and introduce the Interval Debt Model (IDM) and some scheduling
problems based on it, namely: Bankruptcy Minimization/Maximization, in which
the aim is to produce a payment schedule with at most/at least a given number
of bankruptcies; Perfect Scheduling, the special case of the minimization
variant where the aim is to produce a schedule with no bankruptcies (that is,
a perfect schedule); and Bailout Minimization, in which a financial authority
must allocate a smallest possible bailout package to enable a perfect
schedule. We show that each of these problems is NP-complete, in many cases
even on very restricted input instances. On the positive side, we provide for
Perfect Scheduling a polynomial-time algorithm on (rooted) out-trees although
in contrast we prove NP-completeness on directed acyclic graphs, as well as on
instances with a constant number of nodes (and hence also constant treewidth).
When we allow non-integer payments, we show by a linear programming argument
that the problem Bailout Minimization can be solved in polynomial time.

###### keywords:

temporal graph, financial network, payment scheduling, computational
complexity

##  1 Introduction

A natural problem in the study of financial networks is that of whether and
where a failure will occur if no preventative action is taken. We focus
specifically on the flexibility that financial entities are afforded as
regards the precise timing of their outgoings and for this purpose introduce
the _Interval Debt Model (IDM)_ in which a set of financial entities is
interconnected by debts due within specific time intervals. In the IDM, a
_payment schedule_ specifies timings of payments to serve the debts. We
examine the computational hardness of determining the existence of a schedule
of payments with “good” properties, e.g., no or few bankruptcies, or
minimizing the scale of remedial action. In particular, we establish how
hardness depends on variations in the exact formalism of the model (to allow
some small number of bankruptcies or insist on none at all) and on
restrictions on the structure or lifetime of the input instance. A unique and
novel feature of the IDM is its capacity to capture the temporal aspects of
real-world financial systems; previous work has seldom explicitly dealt with
this intrinsic facet of real-world debt.

Graph theory provides models for many problems of practical interest for
analyzing (or administering) financial systems. For example, Eisenberg and
Noe’s work [1] abstracts a financial system to be a weighted digraph (in which
each node is additionally labeled according to the corresponding entity’s
assets). The authors of that work are focused on the existence and computation
of a _clearing vector_ , which is essentially a set of payments among nodes of
the graph which can be executed synchronously without violating some validity
constraints. Their model provides the basis for much subsequent work in the
network-based analysis of financial systems: it has been adapted to
incorporate default costs [2], Credit Default Swaps [3] (CDSs) (that is,
derivatives through which banks can bet on the default of another bank in the
system) and the sequential behavior of bank defaulting in real-world financial
networks [4]. Previous research on financial networks has also drawn from
ecology [5], statistical physics [6] and Boolean networks [7].

A central motivation of financial network analysis is to inform central banks’
and regulators’ policies. The concepts of _solvency_ and _liquidity_ are core
to this task: a bank is said to be _solvent_ if it has enough assets
(including, e.g., debts owed to it) to meet all its obligations; and it is
said to be _liquid_ if it has enough liquid assets (that is, cash) to meet its
obligations on time. An illiquid but solvent bank may exist even in modern
interbank markets [8]. In such cases, a central bank may act as a _lender of
last resort_ and extend loans to such banks to prevent them defaulting on
debts [9, 8]. The optimal allocation of bailouts to a system in order to
minimize damage has also been studied as an extension of Eisenberg and Noe’s
model [10]. Here, bailouts refer to funds provided by a third party (such as
the government) to entities to help them avoid bankruptcy.

Temporal graphs are graphs whose underlying connectivity structure changes
over time. Such graphs allow us to model real-world networks which have
inherent dynamic properties, such as transportation networks [11], contact
networks in an epidemic [12, 13] and communication networks; for an overview
see [14, 15]. Most commonly, following the formulation introduced by Kempe,
Kleinberg and Kumar [16], a temporal graph has a fixed set of vertices
together with edges that appear and disappear at integer times up to an
(integer) lifetime. Often, a natural extension of a problem on static graphs
to the temporal setting yields a computationally harder problem; for example,
finding node-disjoint paths in a temporal graph remains NP-complete even when
the underlying graph is itself a path [17], and finding a temporal vertex
cover remains NP-complete even on star temporal graphs [18].

In this paper we present a novel framework, the _Interval Debt Model_ (IDM),
for considering problems of bailout allocation and payment scheduling in
financial networks by using temporal graphs to account for the isochronal
aspect of debts between financial entities (previous work has almost
exclusively focused on static financial networks). In particular, the IDM
offers the flexibility that entities can pay debts earlier or later, within
some agreed interval. We introduce several natural problems and problem
variants in this model and show that the tractability of such problems depends
greatly on the network topology and on the restrictions on payments (i.e., the
admission or exclusion of partial and fractional payments on debts).

Our work explores the natural question of whether and how payments can be
scheduled to avert large-scale failures in financial networks. Broadly, we
establish that computing a zero-failure schedule (a _perfect schedule_) is NP-
complete even when the network topology is highly restricted, unless we admit
fractional payments, in which case determining the existence of a perfect
schedule is tractable in general. Interestingly, if we allow a small number
$k$ of bankruptcies to occur then every problem variant is computationally
hard even on inputs with $O(1)$ nodes. This can be thought of analogously to
Max 2SAT being strictly harder than 2SAT (unless P=NP) despite being a
“relaxation”: in Max 2SAT we allow up to $k$ clauses to not be satisfied.
Furthermore, in the setting where we insist not only on payments being for
integer amounts but more strongly that any payment is for the full amount of
the corresponding debt, finding a perfect schedule is NP-complete even if
there are only four nodes.

We begin by introducing, first by example and then formally, the Interval Debt
Model in Section 2. In Section 3 we present our results: in Section 3.1–3.3 we
establish some sufficent criteria for NP-hardness for each of the problems we
consider; and in Section 3.4 we present two polynomial-time algorithms. Our
conclusions and directions for further research are given in Section 4.

##  2 The Interval Debt Model

In this section, we introduce (first by example and then formally) the
_Interval Debt Model_ , a framework in which temporal graphs are used to
represent the collection of debts in a financial system.

###  2.1 An illustrative example

As an example, consider a tiny financial network consisting of the 3 banks
$u$, $v$ and $w$ with €30, €20 and €10, respectively, in initial external
assets and where there are the following inter-bank financial obligations:

  * •

bank $u$ owes bank $v$ €20 which it must pay by time 3 and €15 which it must
pay at time 4 or time 5 (note that all payments must be made at integer times)

  * •

bank $v$ must pay bank $w$ a debt of €25 at time 2 exactly

  * •

bank $w$ must pay €25 to bank $v$ between times 4 and 6 (that is, at time 4, 5
or 6).

A graphical representation of this system is shown in Fig. 1 (the descriptive
notation used should be obvious and is retained throughout the paper).

$u$$30$$v$$20$$w$$10$$20@[1,3]$$15@[4,5]$$25@2$$25@[4,6]$ Figure 1: A simple
instance of the Interval Debt Model (IDM). Numbers in square boxes represent
the assets of the node (for example, €30 for node $u$), directed edges
represent debts, and the label on an edge represents the terms of the
associated debt (for example, $u$ must pay $v$ €20 between time 1 and time 3).

Several points can be made about this system: node $u$ is insolvent as its €30
in external assets are insufficient to pay all its debts; node $v$ may be
illiquid for it may default on part of its debt to $w$, e.g., if $u$ pays all
of its first debt at time 3, or may remain liquid, e.g., if it receives at
least €5 from $u$ by time 2; and node $w$ is solvent and certain to remain
liquid in any case. The choices made by the various banks, in the form of a
(payment) schedule, clearly affect the status of the overall financial system.
Note that solvency is determined solely by whether sufficient funds exist
whereas liquidity depends upon when debts are paid and owed.

One may ask several questions about our toy financial system such as: Are
partial payments allowed (e.g., $u$ paying €18 of the €20 debt at time 1, and
the rest later)? If so, are non-integer payments allowed? Can money received
be immediately forwarded (e.g., $u$ paying $v$ €20 at time 2 and $v$ paying
$w$ €25 at time 2)? Does $v$ necessarily have to pay its debt to $w$ at time 2
if it has the external assets to do so? We now expand upon these questions and
specify in detail the setting we consider in the remainder of the paper. Note
that throughout the paper we use the euro € as our monetary unit of resource
even though, as we will see, we have a variant of the Interval Debt Model
within which payments can be made for any rational fraction of a euro. We
often prefix monetary payments with the symbol € to make our proofs more
readable.

###  2.2 Formal setting

Formally, an _Interval Debt Model_ (_IDM_) instance is a 3-tuple $(G,D,A^{0})$
as follows.

  * •

$G=(V,E)$ is a finite digraph with the set of $n$ nodes (or, alternatively,
_banks_) $V=\\{v_{i}:i=1,~{}2,~{}\ldots,~{}n\\}$ and the set of $m$ directed
labelled edges $E\subseteq V\times V\times\mathbb{N}$, with the edge
$(u,v,id)\in E$ denoting that there is an edge, or _debt_ , whose label is
$id$, from the _debtor_ $u$ to the _creditor_ $v$. We can have multi-edges but
the labels of the edges from some node $u$ to some node $v$ must be distinct
and form a contiguous integer sequence $0,1,2,\ldots$. We refer to the subset
of edges directed out of or in to some specific node $v$ by
$E_{\text{out}}(v)$ and $E_{\text{in}}(v)$, respectively. We also refer to the
undirected graph obtained from $G$ by ignoring the orientations on directed
edges as the _footprint_ of $G$.

  * •

$D:E\to\\{(a,t_{1},t_{2}):a,t_{1},t_{2}\in\mathbb{N}\setminus\\{0\\},t_{1}\leq
t_{2}\\}$ is the _debt function_ which associates _terms_ to every debt
(ordinarily, we abbreviate $D((u,v,id))$ as $D(u,v,id)$). Here, if $e$ is a
debt with terms $D(e)=(a,t_{1},t_{2})$ then $a$ is the _monetary amount_ (or
_monetary debt_) to be paid and $t_{1}$ (resp. $t_{2}$) is the first (resp.
last) time at which (any portion of) this amount can be paid. For any debt
$e\in E$, we also write $D(e)=(D_{a}(e),D_{t_{1}}(e),D_{t_{2}}(e))$. For
simplicity of notation, we sometimes denote the terms $D(e)=(a,t_{1},t_{2})$
by $a@[t_{1},t_{2}]$ or by $a@t_{1}$ when $t_{1}=t_{2}$ (as we did in Fig. 1);
also, for simplicity, we sometimes just refer to $a@[t_{1},t_{2}]$ as the
debt.

  * •

$A^{0}=(e_{v_{1}}^{0},e_{v_{2}}^{0},...e_{v_{n}}^{0})\in\mathbb{N}^{n}$ is a
tuple with $e_{v_{i}}^{0}$ denoting the _initial external assets_ of bank
$v_{i}$.

We refer to the greatest time-stamp $T$ that appears in any debt for a given
instance as the _lifetime_ and assume that all network activity ceases after
time $T$. The instance shown in Fig. 1, which has lifetime $T=6$, is formally
given by: $V=\\{u,v,w\\}$, $E=\\{(u,v,0),(u,v,1),(v,w,0),(w,v,0)\\}$,
$D(u,v,0)=(20,1,3)$, $D(u,v,1)=(15,4,5)$, $D(v,w,0)=(25,2,2)$,
$D(w,v,0)=(25,4,6)$ and $A^{0}=(e_{u}^{0},e_{v}^{0},e_{w}^{0})$, where
$e_{u}^{0}=30$, $e_{v}^{0}=20$ and $e_{w}^{0}=10$. Similarly, the instance
shown in Fig. 2 has lifetime $T=2$ and is given by $V=\\{u,v,w\\}$,
$E=\\{(u,v,0),(v,w,0)\\}$, $D(u,v,0)=(1,1,2)$, $D(v,w,0)=(1,1,1)$ and
$A^{0}=(e_{u}^{0},e_{v}^{0},e_{w}^{0})$, where $e_{u}^{0}=1$, $e_{v}^{0}=0$
and $e_{w}^{0}=0$.

$u$$1$$v$$0$$w$$0$$1@[1,2]$$1@1$ Figure 2: An IDM instance for which every
schedule is described by four payment values $p_{(u,v,0)}^{1}$,
$p_{(v,w,0)}^{1}$, $p_{(u,v,0)}^{2}$ and $p_{(v,w,0)}^{2}$.

The _size_ of the instance $(G,D,A^{0})$ is defined as $n+m+\log(T)+b$, where
$b$ is the maximum number of bits needed to encode any of the (integer)
numeric values appearing as the monetary amounts in the debts. Note that in
what follows, we usually do not mention the label $id$ of a debt $(u,v,id)$
but just refer to the debt as $(u,v)$ when this causes no confusion.

###  2.3 Schedules

Given an IDM instance $(G,D,A^{0})$, a (_payment_) _schedule_ $\sigma$
describes the times at which the banks transfer _assets_ to one another via
_payments_. Formally, a schedule $\sigma$ is a set of $|E|T$ _payment values_
$p_{e}^{t}\geq 0$, one for each edge-time pair $(e,t)$ (note that no payments
are made at time 0). Equivalently, a schedule can be expressed as an
$|E|\times T$ matrix $S$ with the payment values $p_{e}^{t}$ the entries of
the matrix. The value $p_{e}^{t}$ is the monetary amount of the debt $e$ paid
at time $t$. Our intention is that at any time $1\leq t\leq T$, every payment
value $p_{e}^{t}>0$ of a schedule $\sigma$ is paid by the debtor of $e$ to the
creditor of $e$, not necessarily for the full monetary amount $D_{a}(e)$ but
for the amount $p_{e}^{t}$. A schedule for the instance of Fig. 2 consists of
the four payments values $p_{(u,v,0)}^{1}$, $p_{(v,w,0)}^{1}$,
$p_{(u,v,0)}^{2}$ and $p_{(v,w,0)}^{2}$. Note that, using the above
representation of a schedule $\sigma$, we might have a large number of zero
payments. Therefore, for simplicity of presentation, in the remainder of the
paper we specify schedules by only detailing the non-zero payments. An example
schedule for the IDM instance in Fig. 2 is then $p_{(u,v,0)}^{1}=1$,
$p_{(v,w,0)}^{1}=1$.

We now introduce some auxiliary variables which are not strictly necessary but
help us to concisely express constraints on and properties of schedules. For
nodes $u,v\in V$ and time $0\leq t\leq T$, the following values are with
respect to some specific schedule.

  * •

Denote by $I_{v}^{t}$ the total monetary amount of incoming payments of node
$v$ at time $t$.

  * •

Denote by $O_{v}^{t}$ the total monetary amount of outgoing payments
(expenses) of node $v$ at time $t$.

  * •

We write $p_{u,v}^{t}$ to denote the total amount of all payments made from
debtor $u$ to creditor $v$ at time $t$ in reference to _all_ debts from $u$ to
$v$; that is, $p_{u,v}^{t}=\sum_{i}p_{(u,v,i)}^{t}$.

  * •

The vector $A^{0}=(e_{v_{1}}^{0},e_{v_{2}}^{0},\ldots,e_{v_{n}}^{0})$
specifies the external assets of each node at time $0$. For $t>0$, we denote
by $e_{v}^{t}$ node $v$’s external assets at time $t$; that is,
$e_{v}^{t}=e_{v}^{t-1}+I_{v}^{t}-O_{v}^{t}$.

For clarity, when we refer to external assets ‘at time $t$’ (resp. ‘prior to
time $t$’) we mean after all (resp. before any) of the payments associated
with time $t$ have been executed.

We have been a little vague so far as regards the form of the payment values
in any schedule and have not specified whether these values are integral,
rational or do not necessarily equal the full monetary amount of the debt. As
we detail below, we have variants of the model covering different
circumstances (with perhaps the standard version being when payment values are
integral but do not necessarily equal the full monetary amount of the debt).

Recall the example schedule from Fig. 2, which we can represent as
$p_{u,v}^{1}=1$, $p_{v,w}^{1}=1$. As we shall soon see, the payments in this
schedule can be legitimately discharged in order to satisfy the terms of all
debts but in general this need not be the case. However, there might be
schedules that are not _valid_ , as well as valid schedules in which banks
default on debts (that is, go _bankrupt_). We deal with the key notions of
validity and bankruptcy now.

######  Definition 1.

A schedule is _valid_ if it satisfies the following properties (for any debt
$e$, terms $D(e)=(a,t_{1},t_{2})$ and node $v$):

  * •

all payment values are non-negative; that is, $p_{e}^{t}\geq 0$, for $1\leq
t\leq T$

  * •

all asset values (as derived from payment values and initial external assets)
are non-negative; that is, $e_{v}^{t}\geq 0$, for $0\leq t\leq T$

  * •

no debts are overpaid; that is, $\sum_{t=1}^{T}p_{e}^{t}\leq a$

  * •

no debts are paid too early; that is, $\sum_{t=1}^{t_{1}-1}p_{e}^{t}=0$.

Given some IDM instance, some schedule and some debt $e$ with terms
$D(e)=(a,t_{1},t_{2})$, the debt $e$ is said to be _payable_ at any time in
the interval $[t_{1},t_{2}-1]$. At time $t_{2}$, $e$ is said to be _due_. At
time $t_{2}\leq t\leq T$, if the full amount $a$ has not yet been paid
(including payments made at time $t_{2}$) then $e$ is said to be _overdue_ at
time $t$. A debt is _active_ whenever it is payable, due or overdue.

However, a bank is said to be _withholding_ if, at some time $1\leq t\leq T$,
it has an overdue debt and sufficient external assets to pay (part of, where
fractional or partial payments are permitted; see below) the debt. If any bank
is withholding (at any time) in the schedule then the schedule is not valid.

So, for example and with reference to the IDM instance in Fig. 2, if,
according to some schedule, bank $u$ pays $1$ to bank $v$ at time $1$ but $v$
makes no payment to $w$ at time 1 then $v$ is withholding and the schedule is
not valid.

######  Definition 2.

With reference to some schedule, a bank is said to be _bankrupt_ (at time $t$)
if it is the debtor of an overdue debt (at time $t$). We say that a schedule
has $k$ _bankruptcies_ if $k$ distinct banks are bankrupt at some time in the
schedule (the times at which these banks are bankrupt might vary). A bank may
_recover_ from bankruptcy if it subsequently receives sufficient income to pay
off all its overdue debts.

######  Definition 3.

A bank $v$ is said to be _insolvent_ if all its assets (that is, the sum of
all debts due to $v$ and of $v$’s initial external assets) are insufficient to
cover all its obligations (that is, the sum of all debts $v$ owes). Formally,
$v$ is insolvent if

$e_{v}^{0}+\sum_{e\in E_{\text{in}}(v)}D_{a}(e)~{}~{}<\sum_{e\in
E_{\text{out}}(v)}D_{a}(e).$

A bank which is insolvent will necessarily be bankrupt in any schedule.

We will not be concerned with the precise timing of bankruptcy or the recovery
or not of any bank in this paper.

We now detail three variants of the model (alluded to earlier) in which
different natural constraints are imposed on the payment values.

######  Definition 4.

In what follows, $e$ is an arbitrary debt and $1\leq t\leq T$ some time.

  * •

In the _Fractional Payments_ (_FP_) variant, the payment values may take
rational values; that is, $p_{e}^{t}\in\mathbb{Q}$ and we allow payments for a
smaller amount than the full monetary amount of $e$.

  * •

In the _Partial Payments_ (_PP_) variant, the payment values may take only
integer values; that is, $p_{e}^{t}\in\mathbb{N}$ and we allow payments for a
smaller amount than the full monetary amount of $e$.

  * •

In the _All-or-Nothing_ (_AoN_) variant, every payment value must fully cover
the relevant monetary amount of $e$; that is, every payment value must be for
the full monetary amount of $e$ or zero. So, $p_{e}^{t}\in\\{D_{a}(e),0\\}$.

For example, the instance of Fig. 2 has the following valid schedules:

  * •

(in all variants) the schedule above in which
$p_{u,v}^{1}=p_{v,w}^{1}=\textup{€}1$ (all debts are paid in full at time 1)

  * •

(in all variants) the schedule in which $p_{u,v}^{2}=p_{v,w}^{2}=\textup{€}1$
(all debts are paid in full at time 2)

    * –

under this schedule, node $v$ is bankrupt at time 1 as €1 of the debt
$(v,w,0)$ is unpaid and that debt is overdue

  * •

(in the FP variant only) for every $a\in\mathbb{Q}$, where $0<a<1$, the
schedule in which $p_{u,v}^{1}=p_{v,w}^{1}=\textup{€}a$ and
$p_{u,v}^{2}=p_{v,w}^{2}=\textup{€}1-a$

    * –

under each of these schedules, node $v$ is bankrupt at time 1 as €$1-a$ of the
debt $(v,w,0)$ is unpaid and that debt is overdue.

It is worthwhile clarifying the concepts of instant forwarding and payment-
cycles. We emphasize that we allow a bank to instantly spend income received.
Note that in any valid schedule for the instance in Fig. 2, $v$ _instantly
forwards_ money received from $u$ to $w$ (so as not to be withholding); so,
the external assets of $v$ never exceed 0 in any valid schedule. This
behaviour is consistent with the Eisenberg and Noe model [1] in which
financial entities operate under a single clearing authority which
synchronously executes payments. Indeed, in such cases a payment-chain of any
length is permitted and the payment takes place instantaneously regardless of
chain length.

Furthermore, and still consistent with the Eisenberg and Noe model, there is
the possibility of a _payment-cycle_ which is a set of banks
$\\{u_{1},u_{2},\ldots,u_{c}\\}$, for some $c\geq 2$, with a set of debts
$\\{e_{i}=(u_{i},u_{i+1},l_{i}):1\leq i\leq
c-1\\}\cup\\{e_{c}=(u_{c},u_{0},l_{c})\\}$ so that at some time $t$, all debts
are active yet none has been fully paid and where each bank makes a payment,
at time $t$, of the same value $a$ towards its debt. As an illustration, Fig.
3 shows three ‘cyclic’ IDM instances, all with lifetime $T=2$. By our
definition of a valid schedule, the schedule
$p_{u,v}^{1}=p_{v,w}^{1}=p_{w,x}^{1}=p_{x,u}^{1}=\textup{€}1$, forming a
payment-cycle, is valid in all three instances. Fig. 3a is somewhat routine.
In Fig. 3b, we may imagine that the €1 moves from node $u$ along the cycle,
satisfying every debt at time 1. This is a useful abstraction but not strictly
accurate: rather, we should imagine that all four banks simultaneously order
payments forward under a single clearing system. The clearing system
calculates the balances that each bank would have with those payments
executed, ensures they are all non-negative (one of our criteria for schedule
validity) and then executes the payments by updating all accounts
simultaneously. This distinction is significant when we consider Fig. 3c in
which no node has external assets. A clearing system ordered to simultaneously
pay all debts would have no problem doing so in the Eisenberg and Noe model
and in our model this constitutes a valid schedule. We highlight that there
also exist valid schedules for the instance in Fig. 3c in which all four banks
go bankrupt, one schedule being where all payments at any time are 0: here, no
bank is withholding (they all have zero external assets), so the schedule is
valid, but every bank has an overdue debt and so is bankrupt.

$u$$1$$v$$1$$w$$1$$x$$1$$1@[1,2]$$1@[1,2]$$1@[1,2]$$1@[1,2]$ (a) All nodes
start with €1.

$u$$1$$v$$0$$w$$0$$x$$0$$1@[1,2]$$1@[1,2]$$1@[1,2]$$1@[1,2]$ (b) Only $u$
starts with €1.

$u$$0$$v$$0$$w$$0$$x$$0$$1@[1,2]$$1@[1,2]$$1@[1,2]$$1@[1,2]$ (c) All nodes
start with €0.

Figure 3: Examples illustrating the behaviour of cycles in the IDM. In all
instances shown the schedule in which all nodes pay their debts in full at
time 1 is valid.

We use payment-cycles throughout our constructions in a context such as that
in Fig. 4. Here, a valid schedule is where all nodes pay their corresponding
debts in full at time $t$. The effect is that the €1 of external assets at
node $u$ is ‘transferred’ to €1 of external assets at node $v$.

$u$$1$$w$$0$$x$$0$$v$$0$$y$$0$$1@t$$1@t$$1@t$$2@t$$2@t$

Figure 4: Using a payment-cycle to effectively transfer €1 of assets from node
$u$ to node $v$.

###  2.4 Canonical instances

We wish to replace certain IDM instances with equivalent yet simpler ones. For
example, consider the instance given in Fig. 1 but where every time-stamp in
the instance is multiplied by a factor of $100$ (so that, for example, the
debt from $w$ to $v$ becomes $25@[400,600]$). This ‘inflated’ instance is in
essence equivalent to the original one but has a lifetime of $600$.

######  Definition 5.

Let $(G,D,A^{0})$ be an instance. Then the set of time-stamps
$\\{t:D_{t_{1}}(e)=t\text{ or }D_{t_{2}}(e)=t\text{, for some edge }e\\}$ is
the set of _extremal_ time-stamps.

There is a simple preprocessing step such that we can assume that the lifetime
$T$ of any IDM instance is polynomially bounded in $n$ and $m$ (that is, the
numbers of banks and debts, respectively). This preprocessing step modifies
the instance such that every $1\leq t\leq T$ is an extremal time-stamp with
the process being to simply omit non-extremal time-stamps and then compact the
remaining time-stamps. Observe that this procedure is such that any valid
schedule in the original IDM instance can be transformed into a valid schedule
in the compacted instance so that these schedules have the same number of
bankruptcies, eventual assets and so forth, and vice versa when the compacted
instance is expanded into the original instance. Hence, we need not consider
pathological cases in which the lifetime is, say, exponential in the number of
nodes and debts. Given this restriction, we can now revise the notion of the
size of an IDM instance to say that it is $n+m+b$ where $n$ is the number of
banks, $m$ is the number of debts and $b$ is the maximum number of bits needed
to encode any of the numeric values appearing as monetary amounts of debts.

######  Lemma 1.

For any given IDM instance and any schedule, in any of the FP, PP or AoN
variants, it is possible in polynomial-time both to check whether the schedule
is valid and to compute the number of bankruptcies under the schedule.

###### Proof sketch.

It is possible to iterate over the schedule once and calculate: the external
assets of every node; the number of debts which are overdue; and the number of
nodes which have overdue debts, all at each time-stamp. The validity of the
schedule (that is, no withholding banks, non-negative assets at every time, no
overpaid debts and no debts paid too early, subject to the FP, PP or AoN
constraint) can similarly be verified in a single iteration over the schedule.

###  2.5 Problem definitions

We now define some decision problems with natural real-world applications.

Bankruptcy Minimization

Instance: an IDM instance $(G,D,A^{0})$ and an integer $k$

Yes-instance: an instance for which there exists a valid schedule $\sigma$
such that at most $k$ banks go bankrupt at some time in the schedule $\sigma$.

Perfect Scheduling

Instance: an IDM instance $(G,D,A^{0})$

Yes-instance: an instance for which there exists a valid schedule $\sigma$
such that no debt is ever overdue in $\sigma$; that is, a _perfect schedule_.

Bailout Minimization

Instance: an IDM instance $(G,D,A^{0})$ (with $n$ banks) and an integer $b$

Yes-instance: an instance for which there exists a positive bailout vector
$B=(b_{1},b_{2},\ldots,b_{n})$ with $\sum_{i=1}^{n}b_{i}\leq b$ and valid
schedule $\sigma$ such that $\sigma$ is a perfect schedule for the instance
$(G,D,A^{0}+B)$.

The problem Perfect Scheduling is equivalent to the Bailout Minimization
problem where $b=0$ and to the Bankruptcy Minimization problem where $k=0$.

Bankruptcy Maximization

Instance: an IDM instance $(G,D,A^{0})$ and an integer $k$

Yes-instance: an instance for which there exists a valid schedule $\sigma$
such that at least $k$ banks go bankrupt at some time in the schedule
$\sigma$.

The problem Bankruptcy Maximization is interesting to consider for quantifying
a ‘worst-case’ schedule where banks’ behavior is unconstrained beyond the
terms of their debts.

All of the problems above exist in the AoN, PP and FP variants and are in NP:
for every yes-instance, there exists a witness schedule, polynomial in the
size of the input, the validity of which can be verified in polynomial time
(see Lemma 1).

Every valid PP schedule is a valid FP schedule whereas not every valid AoN
schedule is a valid PP schedule. In an AoN schedule, a bank may go bankrupt
while still having assets (insufficient to pay off any of its debts) whereas
this is prohibited in any PP schedule as that bank would be withholding. If we
restrict the instances to only those in which for every debt $e$, $D_{a}(e)=1$
then every valid AoN schedule for that instance is a valid PP schedule and a
valid FP schedule.

We call a digraph $G$ from some IDM instance a _multiditree_ whenever the
footprint of $G$ is a tree. We call a multiditree in which every edge is
directed away from the root a _rooted out-tree_ (or just _out-tree_). By an
_out-path_ we mean an out-tree where the footprint is a path and the root is
either of the endpoints.

A summary of some of our upcoming results is given in Table 1 (with NP-c
denoting ‘NP-complete’ and P denoting ‘polynomial-time’). However, note that
there are other, more nuanced results in what follows that do not feature in
Table 1.

problem |  out-tree |  multiditree |  DAG |  general case
---|---|---|---|---
FP Bankruptcy Minimization |  ? |  ? |  NP-c
(Thm 1) |  NP-c
(Thm 1)
PP Bankruptcy Minimization |  ? |  NP-c
(Thm 4) |  NP-c
(Thm 1) |  NP-c
(Thm 1)
AoN Bankruptcy Minimization |  NP-c
(Thm 6) |  NP-c
(Thm 6) |  NP-c
(Thm 1) |  NP-c
(Thm 1)
FP Perfect Scheduling |  P
(Thm 9) |  P
(Thm 9) |  P
(Thm 9) |  P
(Thm 9)
PP Perfect Scheduling |  P
(Thm 10) |  NP-c
(Thm 4) |  NP-c
(Thm 3) |  NP-c
(Thm 3)
AoN Perfect Scheduling |  NP-c
(Thm 6) |  NP-c
(Thm 6) |  NP-c
(Thm 3) |  NP-c
(Thm 3)
FP Bailout Minimization |  P
(Thm 9) |  P
(Thm 9) |  P
(Thm 9) |  P
(Thm 9)
PP Bailout Minimization |  P
(Thm 10) |  NP-c
(Thm 4) |  NP-c
(Thm 3) |  NP-c
(Thm 3)
AoN Bailout Minimization |  NP-c
(Thm 6) |  NP-c
(Thm 6) |  NP-c
(Thm 3) |  NP-c
(Thm 3)
FP Bankruptcy Maximization |  ? |  ? |  NP-c
(Thm 7) |  NP-c
(Thm 7)
PP Bankruptcy Maximization |  ? |  ? |  NP-c
(Thm 7) |  NP-c
(Thm 7)
AoN Bankruptcy Maximization |  NP-c
(Thm 8) |  NP-c
(Thm 8) |  NP-c
(Thm 8) |  NP-c
(Thm 8)
Table 1: Summary of results.

##  3 Our results

In this section we investigate the complexity of the problems presented above.
We present our hardness results for Bankruptcy Minimization, Perfect
Scheduling and Bankruptcy Maximization in Sections 3.1, 3.2 and 3.3,
respectively, and then in Section 3.4 show that under certain constraints the
problem Bailout Minimization and its subproblem Perfect Scheduling become
tractable.

###  3.1 Hardness results for Bankruptcy Minimization

We begin with our core hardness result.

######  Theorem 1.

For each of the AoN, PP and FP variants, the problem Bankrup- tcy Minimization
is NP-complete, even when we restrict to IDM instances $(G,D,A^{0})$ for
which: $T=1$; $G$ is a directed acyclic graph with a longest path of length 4,
has out-degree at most 2 and has in-degree at most 3; the monetary amount of
any debt is at most €3; and initial external assets are at most €3 per bank.

###### Proof.

We build a polynomial-time reduction from the problem 3-Sat-3 to Bankruptcy
Minimization so that all target instances satisfy the constraints in the
statement of the theorem (the problem 3-Sat-3, defined below, was shown to be
NP-complete in [19]).

3-Sat-3

Instance: a c.n.f. formula $\phi$ over $n$ Boolean variables
$v_{1},v_{2},...,v_{n}$ so that each of the $m$ clauses
$c_{1},c_{2},...,c_{m}$ has size at most 3 and where there are exactly 3
occurrences of $v_{i}$ or $\neg v_{i}$ in the clauses

Yes-instance: there exists a satisfying truth assignment for $\phi$.

We may (and do, throughout the paper) restrict ourselves to those instances in
which every literal appears at least once and at most twice (that is, both
$v_{i}$ and $\neg v_{i}$ appear in some clause, for $1\leq i\leq n$) and where
no clause contains both a literal and its negation. We define the size of an
instance $\phi$ to be $n$.

Suppose that we are given a 3-Sat-3 instance $\phi$ of size $n$. We construct
an IDM instance $(G,D,A^{0})$ as follows. For any variable $v_{i}$, denote by
$count_{v_{i}}$ (resp. $count_{\lnot v_{i}}$) the number of occurrences of the
literal $v_{i}$ (resp. $\lnot v_{i}$) in $\phi$ (of course,
$count_{v_{i}}+count_{\lnot v_{i}}=3$). We build a digraph $G$ with:

  * •

a _source node_ $s_{i}$, for each variable $v_{i}$, so that this node has
initial external assets €3 (every other type of node will have initial
external assets €0)

  * •

two _literal nodes_ $x_{i}$ and $\lnot x_{i}$, for each variable $v_{i}$

  * •

a _clause node_ $q_{j}$, for each clause $c_{j}$

  * •

a _sink node_ $d$.

We then add edges and debts as follows. For every $1\leq i\leq n$:

  * •

we add the debt $(s_{i},x_{i})$ with terms $3@1$

  * •

we add the debt $(s_{i},\lnot x_{i})$ with terms $3@1$

  * •

we add the debt $(x_{i},d)$ with terms $count_{\lnot v_{i}}@1$ (note that the
monetary amount to be paid is either €1 or €2)

  * •

we add the debt $(\lnot x_{i},d)$ with terms $count_{v_{i}}@1$ (note that the
monetary amount to be paid is either €1 or €2)

  * •

for every $1\leq j\leq m$:

    * –

we add the debt $(q_{j},d)$ with terms $1@1$

    * –

if the literal $v_{i}\in c_{j}$ then we add the debt $(x_{i},q_{j})$ with
terms $1@1$

    * –

if the literal $\lnot v_{i}\in c_{j}$ then we add the debt $(\lnot
x_{i},q_{j})$ with terms $1@1$.

Fig. 5 shows a sketch of this construction (where nodes without any depicted
initial external assets start with €0). The IDM instance $(G,D,A^{0})$ can
clearly be built from $\phi$ in polynomial-time.

$s_{i}$$3$$x_{i}$$\lnot x_{i}$$q_{j}$$d$$3@1$$3@1$$count_{\lnot
v_{i}}@1$$count_{v_{i}}@1$$1@1$ if $v_{i}\in c_{j}$$1@1$ if $\lnot v_{i}\in
c_{j}$$1@1$ Figure 5: Construction sketch for an IDM instance from a given
formula $\phi$. Note that each of $x_{i}$ and $\lnot x_{i}$ owes €3 in total.

We claim that the instance $((G,D,A^{0}),2n)$ of Bankruptcy Minimization as
constructed above is a yes-instance of Bankruptcy Minimization (no matter
which of the AoN, PP and FP variants we work with) iff $\phi$ is a yes-
instance of 3-Sat-3.

Before we proceed, we have the following remark. Recall that for each $1\leq
i\leq n$, $count_{v_{i}}+count_{\lnot v_{i}}=3$; consequently,
$count_{v_{i}}=2$ iff $count_{\lnot v_{i}}=1$, and vice versa. For each $1\leq
i\leq n$, node $x_{i}$ (resp. $\lnot x_{i}$) has a total monetary debt to the
clause nodes of $count_{v_{i}}$ (resp. $count_{\lnot v_{i}}$) and a total
monetary debt to the sink node $d$ of $count_{\lnot v_{i}}$ (resp.
$count_{v_{i}}$); so, each literal node has a total monetary debt of €3.

######  Claim 1.

If $\phi$ is a yes-instance of 3-Sat-3 then $((G,D,A^{0}),2n)$ is a yes-
instance of Bankruptcy Minimization.

###### Proof.

Suppose that $\phi$ is satisfiable via some truth assignment $X$. Consider the
schedule $\sigma$ for $(G,D,A^{0})$ in which:

  * •

every source node $s_{i}$ pays €3 (at time 1, as are all payments) to the
literal node $x_{i}$ (resp. $\lnot x_{i}$) if $X(v_{i})=True$ (resp.
$X(v_{i})=False$)

  * •

every literal node $x_{i}$ (resp. $\lnot x_{i}$) for which $X(v_{i})=True$
(resp. $X(v_{i})=False$) pays all its debts in full

    * –

as remarked above, this literal node has total monetary debt €3 but, from
above, it receives €3 from $s_{i}$

  * •

every clause node pays its €1 debt to the sink node $d$

    * –

this is necessarily possible because $X$ is a satisfying truth assignment,
meaning every clause node receives at least €1 from some literal node
corresponding to a literal in that clause set to $True$ by $X$.

Note that $\sigma$ is valid in all three IDM variants. The total number of
bankruptcies in $\sigma$ is $2n$: exactly $n$ bankrupt source nodes and
exactly $n$ bankrupt literal nodes. Hence, if $\phi$ is satisfiable then the
schedule $\sigma$ for $(G,D,A^{0})$ results in at most (in fact, exactly) $2n$
bankruptcies.

######  Claim 2.

If $(G,D,A^{0}),2n)$ is a yes-instance of Bankruptcy Minimization then $\phi$
is a yes-instance of 3-Sat-3.

###### Proof.

Suppose that we have a schedule $\sigma$ for $(G,D,A^{0})$ with at most $2n$
bankruptcies. Consider the set of all literals $L=\\{v_{1},\lnot
v_{1},v_{2},\lnot v_{2},...,v_{n},\lnot v_{n}\\}$ w.r.t. $\phi$. Define the
set of _bankrupt literals_ $B\subseteq L$ to consist of every literal whose
corresponding (literal) node is bankrupt within $\sigma$. Define $X(w)=True$
iff $w\in L\setminus B$. We claim that $X$ is a (complete) truth assignment.
Suppose it is not and that $X(v_{i})=X(\neg v_{i})=True$; so, both $x_{i}$ and
$\neg x_{i}$ are bankrupt within $\sigma$. However, in any valid schedule (no
matter what the IDM variant) every source node $s_{i}$ will necessarily go
bankrupt and at least one of the literal nodes $x_{i}$ and $\lnot x_{i}$ will
go bankrupt. Thus, as we have at most $2n$ bankruptcies, our supposition is
incorrect. Alternatively, suppose that $X(v_{i})=X(\neg v_{i})=False$; so,
neither $x_{i}$ nor $\neg x_{i}$ is bankrupt within $\sigma$. But, as stated,
this cannot be the case. So, $X$ is a truth assignment; moreover, $\sigma$ has
exactly $2n$ bankruptcies with exactly one of any pair of ‘oppositely-
oriented’ literal nodes bankrupt.

Suppose, for contradiction, that $X$ is not a satisfying assignment. So, there
exists at least one clause, $c_{j}$ say, such that every literal in the clause
is made $False$ by $X$. By definition of $X$, we have that every literal node
corresponding to one of these literals is a bankrupt node. Any such literal
node must receive €0 (as the ‘oppositely-oriented’ literal node is not
bankrupt and receives €3); consequently, the clause node $q_{j}$ receives €0
and is bankrupt. This yields a contradiction as we have exactly $2n$ bankrupt
nodes (as detailed above).

Consequently, $\phi$ is satisfiable iff the IDM instance $(G,D,A^{0})$ admits
a schedule with at most $2n$ bankruptcies (again, this holds for each IDM
variant). This concludes our proof.

Our next result is perhaps rather surprising in that we restrict to IDM
instances $(G,D,A^{0})$ where $G$ is a fixed digraph.

######  Theorem 2.

For each of the AoN, PP and FP variants, the problem Bankruptcy Minimization
is weakly NP-complete, even when we restrict to instances $((G,D,A^{0}),k)$
where $G$ is a fixed, specific digraph with 32 nodes and $k=16$.

###### Proof.

We build a polynomial-time reduction from Equal Cardinality Partition to
Bankruptcy Minimization (Equal Cardinality Partition, defined below, was
proven weakly NP-complete in [20]).

Equal Cardinality Partition

Instance: a multi-set of positive integers $S=\\{a_{1},a_{2},...,a_{n}\\}$
where $n$ is even and with sum $sum(S)=2k$

Yes-instance: there exist a partition of $S$ into two equal-sized sets $S_{1}$
and $S_{2}$ such that $sum(S_{1})=sum(S_{2})=k$.

The size of such an instance is $nb$ where $b$ is the least number of bits so
that any integer $a_{i}$ can be represented in binary using $b$ bits.

Given an instance $S=\\{a_{1},a_{2},...,a_{n}\\}$ of Equal Cardinality
Partition (where $n\geq 1$), we construct the IDM instance $(G,D,A^{0})$ that
is illustrated in Fig. 6. Every appearance of the shaded node $p$ in Fig. 6
corresponds to the same single node, that we refer to as the sink, and thus
this instance has 32 nodes in total. We use the symbol ‘$\infty$’ to denote a
suitably high monetary amount (though $2k+n+1$ suffices) and $T=10n+7$. Our
IDM instance can trivially be constructed from $S$ in time polynomial in the
size of the instance $S$. We now show that $(G,D,A^{0})$ admits a valid
schedule with at most 16 bankruptcies iff $S$ is a yes-instance of Equal
Cardinality Partition (no matter whether we are in the AoN, PP or FP variant).
Until further stated, we will work solely within the PP variant and return to
the AoN and FP variants later.

$s$$2k$$m_{1}$$p$$\infty@1$$m_{2}$$m_{3}$$\infty@1$$a_{1}@10,~{}a_{1}@15$$...$$a_{n}@10n,~{}a_{n}@10n+5$$a_{1}@10,~{}a_{1}@15$$...$$a_{n}@10n,~{}a_{n}@10n+5$$a_{1}@[10,15]$$...$$a_{n}@[10n,10n+5]$$m_{4}^{A}$$p$$\infty@1$$m_{5}^{A}$$m_{6}^{A}$$\infty@1$$a_{1}@10$$...$$a_{n}@10n$$a_{1}@10$$...$$a_{n}@10n$$\infty@1$$m_{7}^{A}$$\infty@1$$m_{8}^{A}$$p$$\infty@1$$m_{9}^{A}$$m_{10}^{A}$$m_{11}^{A}$$m_{12}^{A}$$n/2$$1@10$$...$$1@10n$$1@11$$...$$1@10n+1$$1@11$$...$$1@10n+1$$1@11$$...$$1@10n+1$$\infty@1$$\infty@1$$1@11$$...$$1@10n+1$$m_{13}^{A}$$p$$\infty@1$$m_{14}^{A}$$m_{15}^{A}$$m_{16}^{A}$$k@[1,T]$$a_{1}@12$$...$$a_{n}@10n+2$$a_{1}@12$$...$$a_{n}@10n+2$$\infty@1$$\infty@1$$m_{4}^{B}$$p$$\infty@1$$m_{5}^{B}$$m_{6}^{B}$$\infty@1$$a_{1}@15$$...$$a_{n}@10n+5$$a_{1}@15$$...$$a_{n}@10n+5$$\infty@1$$m_{7}^{B}$$\infty@1$$m_{8}^{B}$$p$$\infty@1$$m_{9}^{B}$$m_{10}^{B}$$m_{11}^{B}$$m_{12}^{B}$$n/2$$1@15$$...$$1@10n+5$$1@16$$...$$1@10n+6$$1@16$$...$$1@10n+6$$1@16$$...$$1@10n+6$$\infty@1$$\infty@1$$1@16$$...$$1@10n+6$$m_{13}^{B}$$p$$\infty@1$$m_{14}^{B}$$m_{15}^{B}$$m_{16}^{B}$$k@[1,T]$$a_{1}@17$$...$$a_{n}@10n+7$$a_{1}@17$$...$$a_{n}@10n+7$$\infty@1$$\infty@1$$d$$k@T$$k@T$

Figure 6: Construction of an IDM instance (with $k=16$) corresponding to the
Equal Cardinality Partition instance $S=\\{a_{1},\ldots,a_{n}\\}$. Dashed red
edges are “practically infinite” bankrupting debts.

######  Claim 3.

If the IDM instance $((G,D,A^{0}),16)$ is a yes-instance of Bankruptcy
Minimization then $S$ is a yes-instance of Equal Cardinality Partition.

###### Proof.

Suppose that $(G,D,A_{e}^{0})$ admits a valid schedule $\sigma$ with at most
16 bankruptcies. Note that the 14 nodes $m_{1}$, $m_{3}$, $m_{4}^{A}$,
$m_{6}^{A}$, $m_{8}^{A}$, $m_{11}^{A}$, $m_{13}^{A}$, $m_{15}^{A}$,
$m_{4}^{B}$, $m_{6}^{B}$, $m_{8}^{B}$, $m_{11}^{B}$, $m_{13}^{B}$ and
$m_{15}^{B}$ are necessarily bankrupt in _every_ valid schedule because they
are debtors of debts of monetary amount $\infty$ at time 1 and no payments are
made before time 10 (these nodes are dashed and highlighted in red in Fig. 6
as are the debts at time 1 of monetary amount $\infty$). Note also that these
nodes can never have any external assets at any time and nor can the nodes
$m_{2}$, $m_{5}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$, $m_{14}^{A}$, $m_{5}^{B}$,
$m_{9}^{B}$, $m_{10}^{B}$ and $m_{14}^{B}$ (as they would otherwise be
withholding). Consequently, we can only have at most another 2 nodes going
bankrupt within $\sigma$. We begin by showing that one of
$\\{m_{7}^{A},m_{12}^{A}\\}$ must be bankrupt and one of
$\\{m_{7}^{B},m_{12}^{B}\\}$ must be bankrupt (which will account for all
bankrupt nodes).

Suppose that none of the nodes $m_{7}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$ and
$m_{12}^{A}$ are bankrupt in $\sigma$. By considering $m_{12}^{A}$ at the
times $t\in\\{11,21,\ldots,10n+1\\}$, on at least $\frac{n}{2}$ of these
occasions $m_{12}^{A}$ must have received at least €1 via payments from
$m_{11}^{A}$ (so as to service all its debts to $m_{7}^{A}$). Consider the
first occasion $t^{\prime}\in\\{11,21,\ldots,10n+1\\}$ that $m_{12}^{A}$
receives a non-zero payment from $m_{11}^{A}$ (note that all payments from
$m_{11}^{A}$ to $m_{12}^{A}$ are made at some time from
$\\{11,21,\ldots,10n+1\\}$). There must have been a payment of €1 from
$m_{10}^{A}$ to $m_{11}^{A}$ at time $t^{\prime}$ as well as payments of €1
from $m_{9}^{A}$ to $m_{10}^{A}$ and from $m_{8}^{A}$ to $m_{9}^{A}$ at time
$t^{\prime}$. So, $m_{8}^{A}$ must receive at least €1 from $m_{7}^{A}$ and
$m_{11}^{A}$ at time $t^{\prime}$. As $m_{11}^{A}$ makes a non-zero payment to
$m_{12}^{A}$ at time $t^{\prime}$, any payment from $m_{11}^{A}$ to
$m_{7}^{A}$ at time $t^{\prime}$ must be for some amount strictly less than
€1. Consequently, $m_{8}^{A}$ must receive a non-zero payment from $m_{7}^{A}$
at time $t^{\prime}$. The only way that this can happen is if there is an
overdue debt from $m_{7}^{A}$ to $m_{8}^{A}$; that is, $m_{7}^{A}$ is
bankrupt, which yields a contradiction. Hence, at least one of $m_{7}^{A}$,
$m_{9}^{A}$, $m_{10}^{A}$ and $m_{12}^{A}$ is bankrupt. An analogous argument
shows that at least one of $m_{7}^{B}$, $m_{9}^{B}$, $m_{11}^{B}$ and
$m_{12}^{B}$ is bankrupt. Hence, exactly one of $m_{7}^{A}$, $m_{9}^{A}$,
$m_{10}^{A}$ and $m_{12}^{A}$ is bankrupt and exactly one of $m_{7}^{B}$,
$m_{9}^{B}$, $m_{11}^{B}$ and $m_{12}^{B}$ is bankrupt.

Suppose that $m_{9}^{A}$ is bankrupt. So, $m_{10}^{A}$ is necessarily
bankrupt. Conversely, if $m_{10}^{A}$ is bankrupt then $m_{9}^{A}$ must be
bankrupt also. Consequently, neither $m_{9}^{A}$ nor $m_{10}^{A}$ is bankrupt
and we must have that either $m_{7}^{A}$ or $m_{12}^{A}$ is bankrupt and
analogously either $m_{7}^{B}$ or $m_{12}^{B}$ is bankrupt. In particular,
$s$, $m_{2}$, $m_{5}^{A}$, $m_{13}^{A}$, $m_{15}^{A}$, $m_{5}^{B}$,
$m_{13}^{B}$ and $m_{15}^{B}$ are not bankrupt.

Let us turn to analysing the flow of resource via the schedule $\sigma$. As
$\sigma$ is valid, we must have that both debts from $m_{16}^{A}$ and
$m_{16}^{B}$ are paid on time with €$2k$ in total reaching $d$. The question
is: does this resource consist of the €$2k$ emanating from $s$ or does it
consist of resource emanating from $s$ but supplemented with resource
emanating from $m_{12}^{A}$ or $m_{12}^{B}$? Let us look at the possible debt
payments at time 10 (which is the earliest time that payments can be made). In
particular, let us look at payments made by $m_{6}^{A}$ to $m_{7}^{A}$ at time
10. Note that all payments made from $m_{6}^{A}$ to $m_{7}^{A}$ are at a time
from $\\{10,20,\ldots,10n\\}$.

Case (_a_): An amount of €$x>0$ is paid from $m_{6}^{A}$ to $m_{7}^{A}$ at
time 10.

There are two essential sub-cases at time 10:

  * (_i_)

$m_{7}^{A}$ services its debt to $m_{8}^{A}$, which pays €1 to the sink, with
perhaps €$y\geq 0$ paid from $m_{7}^{A}$ to $m_{13}^{A}$ and from there to the
sink, so that €$x-y-1\geq 0$ resides at $m_{7}^{A}$ in external assets at time
10

  * (_ii_)

$m_{7}^{A}$ does not service its debt to $m_{8}^{A}$ and pays €$x$ to
$m_{13}^{A}$ with this payment immediately going to the sink, so that €0
resides at $m_{7}^{A}$ in external assets at time 10; hence, $m_{7}^{A}$ is
bankrupt (note that no external assets can reside at $m_{7}^{A}$ at time 10 as
otherwise $m_{7}^{A}$ would be withholding).

Now consider what happens at time 11. Suppose that we are in Case (_a_._i_).
There must be a payment-cycle involving $m_{8}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$
and $m_{11}^{A}$ and as $\frac{n}{2}\geq 1$, $m_{12}^{A}$ must service its
debt to $m_{7}^{A}$, with perhaps $m_{7}^{A}$ paying €$z\geq 0$ to
$m_{13}^{A}$ which is immediately paid to the sink. The €1 from $m_{12}^{A}$
does not supplement the resource emanating from $s$ but just ‘replaces’ €1
which was ‘lost’ to the sink at time 10. Note that the external assets of
$m_{12}^{A}$ at time 11 are $\frac{n}{2}-1$.

Suppose that we are in Case (_a_._ii_). Note that as $m_{7}^{A}$ is bankrupt,
$m_{12}^{A}$ can never become bankrupt and so must service its debts when
required. There are four possibilities as regards what happens at time 11
(bearing in mind the overdue debt from $m_{7}^{A}$ to $m_{8}^{A}$):

  * (1)

$m_{12}^{A}$ pays €1 to $m_{7}^{A}$ which pays €1 to $m_{8}^{A}$ which
immediately goes to the sink, with a payment-cycle involving $m_{8}^{A}$,
$m_{9}^{A}$, $m_{10}^{A}$ and $m_{11}^{A}$

  * (2)

$m_{12}^{A}$ pays €1 to $m_{7}^{A}$ which pays €1 to $m_{8}^{A}$ which pays €1
to $m_{9}^{A}$ which pays €1 to $m_{10}^{A}$ which pays €1 to $m_{11}^{A}$
which pays €1 to $m_{8}^{A}$ which immediately goes to the sink

  * (3)

$m_{12}^{A}$ pays €1 to $m_{7}^{A}$ which pays €1 to $m_{13}^{A}$ which
immediately goes to the sink, with a payment-cycle involving $m_{8}^{A}$,
$m_{9}^{A}$, $m_{10}^{A}$ and $m_{11}^{A}$

  * (4)

$m_{12}^{A}$ pays €1 to $m_{7}^{A}$ which pays €1 to $m_{8}^{A}$ which pays €1
to $m_{9}^{A}$ which pays €1 to $m_{10}^{A}$ which pays €1 to $m_{11}^{A}$
which pays €1 to $m_{12}^{A}$; that is, we have a payment cycle involving
$m_{7}^{A}$, $m_{8}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$, $m_{11}^{A}$ and
$m_{12}^{A}$.

In (1-3) above, the €1 from $m_{12}^{A}$ does not supplement the resource
emanating from $s$ but is lost to the sink (as are the €$x>0$ at time 10).
Note that in (3), the debt from $m_{7}^{A}$ to $m_{8}^{A}$ at time 10 is
overdue and cannot be paid at time 11 as $m_{7}^{A}$ has no external assets at
time 10; so it remains overdue. In (4), again no supplement is made, although
€$\frac{n}{2}$ still resides at $m_{12}^{A}$ in external assets at time 11,
and €$x>0$ emanating from $s$ has been lost to the sink.

In both Case (_a_._i_) and Case (_a_._ii_), at time 12, the only possible non-
payment-cycle payments involve $s$, $m_{1}$, $m_{7}^{A}$, $m_{13}^{A}$,
$m_{14}^{A}$ and $m_{15}^{A}$ but any such payments do not affect whether the
resources emanating from $m_{12}^{A}$ or $m_{12}^{B}$ supplement the resource
emanating from $s$. In Case (_a_._ii_.3), the debt from $m_{7}^{A}$ to
$m_{8}^{A}$ at time 10 is overdue and so must be paid from the external assets
of $m_{7}^{A}$ at time 12, if it has any and unless all of these assets are
paid to $m_{13}^{A}$. All such payments by $m_{7}^{A}$ will immediately go to
the sink.

Case (_b_): No payment is made from $m_{6}^{A}$ to $m_{7}^{A}$ at time 10.

Consequently, $m_{7}^{A}$ cannot pay its debt to $m_{8}^{A}$ and becomes
bankrupt. At time 11, $m_{12}^{A}$ must necessarily service its debt to
$m_{7}^{A}$ and there are four possibilities with these possibilities being
exactly the possibilities (1-4) in Case (_a_._ii_). As before, at time 12, the
only possible non-payment-cycle payments made involve $s$, $m_{1}$,
$m_{7}^{A}$, $m_{13}^{A}$, $m_{14}^{A}$ and $m_{15}^{A}$ but any such payments
do not affect whether the resources emanating from $m_{12}^{A}$ or
$m_{12}^{B}$ supplement the resources emanating from $s$. Note that in (3),
the debt from $m_{7}^{A}$ to $m_{8}^{A}$ at time 10 is still overdue at time
11 and cannot be paid at time 12 as $m_{7}^{A}$ has no external assets at time
12; so it remains overdue. In (4), again no supplement is made, although
€$\frac{n}{2}$ still resides at $m_{12}^{A}$ in external assets at time 12.

So, the resources emanating from $m_{12}^{A}$ cannot supplement the resources
emanating from $s$ at any time $t<15$. An identical argument can be applied to
time 15 so as to yield a similar conclusion as regards the resources emanating
from $m_{12}^{B}$ at any time $t<20$.

Consider the situation at time 20. With regard to the sub-network involving
$m_{6}^{A}$, $m_{7}^{A}$, $m_{8}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$,
$m_{11}^{A}$, $m_{12}^{A}$ and $m_{13}^{A}$ (that is, the sub-network of study
above), the situation is similar to that at time 10 except that there may be
additional restrictions on what can happen given: a possible existing overdue
debt from $m_{7}^{A}$ to $m_{8}^{A}$ (the debt due at time 10); possible non-
zero external assets at $m_{7}^{A}$; and possibly reduced external assets at
$m_{12}^{A}$ of $\frac{n}{2}-1$. Note that if $m_{7}^{A}$ has external assets
prior to time 20 then this can be thought of as $m_{7}^{A}$ having acquired
these assets from $m_{6}^{A}$ at time 20; that is, we are in Case (_a_) above.
Given the fact that the situation at time $20$ is a restricted version of the
situation at time $10$ where the resources emanating from $m_{12}^{A}$ could
not supplement those emanating from $s$, the same is true again. By analysing
each time $t=25,30,35,\ldots$, we can see that no resources emanating from
either $m_{12}^{A}$ or $m_{12}^{B}$ can supplement those emanating from $s$.
Hence, in order to secure total external assets of €$2k$ at $d$ after time
$T$, we need that all of the €$2k$ resource emanating from $s$ reaches $d$;
that is, none of it is lost to the sink en route (although some of it might
have been ‘replaced’ as per Case (_a_._i_)).

We can now repeat the above analysis except that now we know that we cannot
lose resource emanating from $s$ unless it is replaced as in Case (_a_._i_).
This simplifies things considerably. If $m_{7}^{A}$ has €$x>0$ at time
$t\in\\{10,20,\ldots,10n\\}$ (either as external assets or from a payment by
$m_{6}^{A}$ at time $t$) then it must be the case that $m_{7}^{A}$ services
the debt to $m_{8}^{A}$ at time $t$, €1 is lost to the sink and $m_{7}^{A}$
retains $x-1$ in external assets. At time $t+1$, $m_{12}^{A}$ must service its
debt to $m_{7}^{A}$ so as to replace the lost €1, with €$x$ residing at
$m_{7}^{A}$ in external assets at time $t+1$. Consequently, there can only be
at most $\frac{n}{2}$ times in $\\{10,20,\ldots,10n\\}$ when $m_{7}^{A}$
receives a payment from $m_{6}^{A}$ (recall that $m_{6}^{A}$ only makes
payments to $m_{7}^{A}$ at times from $\\{10,20,\ldots,10n\\}$). When
$m_{7}^{A}$ either has no external assets or receives no payment from
$m_{6}^{A}$ at time $t\in\\{10,20,\ldots,10n\\}$, we either lose €1 of
external assets from $m_{12}^{A}$ to the sink (and so we also lose some
capacity to ‘replace’ resource emanating from $s$ that is lost to the sink) or
we are in case (4) above and have a payment cycle involving $m_{7}^{A}$,
$m_{8}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$, $m_{11}^{A}$ and $m_{12}^{A}$.
Analogous comments can be made as regards the corresponding nodes
superscripted $B$ and times in $\\{15,25,\ldots,10n+5\\}$.

Bearing in mind that none of the resource emanating from $s$ goes to the sink
before it reaches either $m_{6}^{A}$ or $m_{6}^{B}$, at least $n$ distinct
payments are made from $s$ and these payments result in at least $n$ payments
in total from $m_{6}^{A}$ to $m_{7}^{A}$ or from $m_{6}^{B}$ to $m_{7}^{B}$.
Thus, from above, $m_{6}^{A}$ must make exactly $\frac{n}{2}$ payments to
$m_{7}^{A}$ and $m_{6}^{B}$ must make exactly $\frac{n}{2}$ payments to
$m_{7}^{B}$. This means that any payment from $m_{6}^{A}$ to $m_{7}^{A}$ or
from $m_{6}^{B}$ to $m_{7}^{B}$ must be for an amount from
$\\{a_{1},a_{2},\ldots,a_{n}\\}$ and we have a partition of
$\\{a_{1},a_{2},\ldots,a_{n}\\}$ into equal-sized sets both of whose sum is
$k$; that is, our instance $S$ of Equal Cardinality Partition is a yes-
instance and the claim follows.

######  Claim 4.

If $S$ is a yes-instance of Equal Cardinality Partition then
$((G,D,A^{0}),16)$ is a yes-instance of Bankruptcy Minimization.

###### Proof.

Suppose that our instance $S=\\{a_{1},a_{2},\ldots,a_{n}\\}$ of Equal
Cardinality Partition is such that $n=2m$ and
$\sum_{i=1}^{m}a_{\alpha_{i}}=\sum_{i=1}^{m}a_{\beta_{i}}$, where
$\\{\alpha_{i},\beta_{i}:1\leq i\leq m\\}=\\{1,2,\ldots,n\\}$. We need to
build a valid schedule $\sigma$ for $(G,D,A^{0})$ with at most 16
bankruptcies. Let $1\leq i\leq n$ and suppose that $i=\alpha_{j}$, where
$1\leq j\leq m$. The node $s$ pays its $i$th debt to $m_{1}$ (that is, the
debt $a_{i}@[10i,10i+5]$) at time $10i$ and this payment is percolated all the
way down to $m_{7}^{A}$ at time $10i$. The debt $1@10i$ from $m_{7}^{A}$ to
$m_{8}^{A}$ is paid at time $10i$ with this €1 being replaced from
$m_{12}^{A}$ at time $10i+1$ (see Case (_a_._i_) from the proof of Claim 3
above). We also have a payment cycle involving $m_{8}^{A}$, $m_{9}^{A}$,
$m_{10}^{A}$ and $m_{11}^{A}$ at time $10i+1$. The external assets of $a_{i}$
at $m_{7}^{A}$ are percolated down to $m_{16}^{A}$ at time $10i+2$. At time
$10i+5$, we have suitable payment cycles involving: $m_{1}$, $m_{2}$ and
$m_{3}$; $m_{4}$, $m_{5}$ and $m_{6}$; and $m_{13}^{A}$, $m_{14}^{A}$ and
$m_{15}^{A}$. We also have a payment cycle involving $m_{7}^{A}$, $m_{8}^{A}$,
$m_{9}^{A}$, $m_{10}^{A}$, $m_{11}^{A}$ and $m_{12}^{A}$ (see (4) from the
proof of Claim 3 above). An analogous course of action is taken if
$i=\beta_{j}$, for some $1\leq j\leq m$. The resulting schedule is valid and
the 16 nodes $m_{1}$, $m_{3}$, $m_{4}^{A}$, $m_{6}^{A}$, $m_{7}^{A}$,
$m_{8}^{A}$, $m_{11}^{A}$, $m_{13}^{A}$, $m_{15}^{A}$, $m_{4}^{B}$,
$m_{6}^{B}$, $m_{7}^{B}$, $m_{8}^{B}$, $m_{11}^{B}$, $m_{13}^{B}$ and
$m_{15}^{B}$ are bankrupt. The claim follows.

So, our main result holds for the PP variant of Bankruptcy Minimization. Note
that everything above holds for the AoN variant too, though Theorem 6 is a
strictly stronger result for that setting.

Let us consider now the FP variant. As it happens, an argument similar to that
above works within the FP variant although there are more complicated nuances.
Rather than repeat the whole nuanced argument in detail, and given the above
complete proof for the PP variant, we only sketch the proof for the FP
variant. Henceforth, we assume that we are working within the FP variant.

Consider the proof of the corresponding version of Claim 3. The reasoning that
establishes that we must have that either $m_{7}^{A}$ or $m_{12}^{A}$ is
bankrupt and that either $m_{7}^{B}$ or $m_{12}^{B}$ is bankrupt holds for the
FP variant. Consider payments made from $m_{6}^{A}$ to $m_{7}^{A}$ at time 10.

Case (_a_): An amount of €$x>0$ is paid from $m_{6}^{A}$ to $m_{7}^{A}$ at
time 10.

There are two essential sub-cases at time 10:

  * (_i_)

$m_{7}^{A}$ services its debt to $m_{8}^{A}$, which pays €1 to the sink, with
perhaps €$y\geq 0$ paid from $m_{7}^{A}$ to $m_{13}^{A}$ and from there to the
sink, so that €$x-y-1\geq 0$ resides at $m_{7}^{A}$ in external assets at time
10

  * (_ii_)

$m_{7}^{A}$ does not fully service its debt to $m_{8}^{A}$ but pays €$w$,
where $0\leq w<1$, to $m_{8}^{A}$, which immediately goes to the sink, and
€$x-w$ to $m_{13}^{A}$, which immediately goes to the sink, so that €0 resides
at $m_{7}^{A}$ in external assets at time 10; hence, $m_{7}^{A}$ is bankrupt.

Consider what happens at time 11. In Case (_a_._i_), there must be a payment
cycle involving $m_{8}^{A}$, $m_{9}^{A}$, $m_{10}^{A}$ and $m_{11}^{A}$ and
$m_{12}^{A}$ services its debt to $m_{7}^{A}$. The €1 from $m_{12}^{A}$ does
not supplement the resource emanating from $s$ but just ‘replaces’ €1 which
was ‘lost’ to the sink at time 10.

Suppose that we are in Case (_a_._ii_). There are two scenarios:

  * (1)

$m_{12}^{A}$ pays €1 to $m_{7}^{A}$ which pays €$1-w$ to $m_{8}^{A}$ of which
€$w^{\prime}$ goes immediately to the sink and €$1-w-w^{\prime}$ is paid to
$m_{9}^{A}$; $m_{7}^{A}$ has external assets of at most €$w$ as it may be the
case that $m_{7}^{A}$ also makes a payment to $m_{13}^{A}$ which goes straight
to the sink, or

  * (2)

$m_{12}^{A}$ pays €1 to $m_{7}^{A}$ which pays €$y$ to $m_{8}^{A}$, where
$0\leq y<1-w$, of which €$y^{\prime}$ goes immediately to the sink and
€$y-y^{\prime}$ is paid to $m_{9}^{A}$; also, €$1-y$ is paid to $m_{13}^{A}$
which goes straight to the sink.

In (1), it must be the case that $m_{8}^{A}$ receives at least $w+w^{\prime}$
from $m_{11}^{A}$ (so as to fully service its debt to $m_{9}^{A}$); hence,
$m_{11}^{A}$ pays at most €$1-w-w^{\prime}$ to $m_{12}^{A}$. In any case, €$x$
have been lost to the sink with $m_{7}^{A}$ gaining €$w$ from $m_{12}^{A}$
(with $x\geq w$). In (2), it must be the case that $m_{8}^{A}$ receives at
least €$1-(y-y^{\prime})$ from $m_{11}^{A}$ (so as to fully service its debt
to $m_{9}^{A}$); hence, $m_{11}^{A}$ pays at most €$y-y^{\prime}$ to
$m_{12}^{A}$. In any case, €$x$ have been lost to the sink with $m_{7}^{A}$
gaining nothing from $m_{12}^{A}$.

Case (_b_): No payment is made from $m_{6}^{A}$ to $m_{7}^{A}$ at time 10.

At time 11, it must be the case that $m_{12}^{A}$ services its debt to
$m_{7}^{A}$ and then we are essentially in Case (_a_._ii_) above.

The outcome is that the resources emanating from $m_{12}^{A}$ cannot
supplement the resources emanating form $s$ at any time $t<15$. An identical
argument can be applied to time 15 so as to yield a similar conclusion as
regards the resources emanating from $m_{12}^{B}$ at any time $t<20$. The rest
of the proof of Claim 3 holds for the FP variant and we have that Claim 3
holds for the FP variant.

The schedule $\sigma$ described in the proof of Claim 4 is a valid schedule in
the FP variant and so Claim 4 also holds for the FP variant. This complete our
proof of the main theorem.

The proof of Theorem 2 clearly demonstrates the intricacies of reasoning in
our financial networks. By Theorem 2, it follows that each of the AoN, PP and
FP variants of Bankruptcy Minimization are _para-NP-hard_ when parameterized
by any parameter that is upper-bounded by the number of vertices, such as,
e.g., the number of bankruptcies $k$ or the treewidth of the footprint. Note
that Theorem 2 concerns weak completeness results (in particular, the integers
in an instance of Equal Cardinality Matching appear explicitly as monetary
debts in the corresponding instance of Bankruptcy Minimization).

###  3.2 Hardness results for Perfect Scheduling

We now turn to Perfect Scheduling. Note that both Theorem 1 and Theorem 2
yield hardness results for Perfect Scheduling as corollaries; however, the
following results directed specifically at Perfect Scheduling are all stronger
statements.

######  Theorem 3.

The problem Perfect Scheduling is NP-complete for the AoN and PP variants even
when we restrict to IDM instances $(G,D,A^{0})$ for which: $T\leq 3$; $G$ is a
directed acyclic graph with out-degree at most 3 and in-degree at most 3; the
monetary amount of any debt is at most €2; and any initial external assets of
a node is at most €3 per bank.

###### Proof.

Let us work within the PP variant until further notice. We introduce the
_multiplier gadget_ shown in Fig. 7 and use this gadget in our main reduction
(the gadget sits within the blue dotted line). We claim the following.

$m_{0}$$2$$m_{1}$$m_{2}$$m_{3}$$s$$2$inout$2@[1,3]$$2@3$$1@[2,3]$$1@[1,3]$$1@[1,2]$$1@1$$1@[1,3]$$*2$
Figure 7: The multiplier gadget. Intuitively, the gadget “amplifies” payments
into it at time 1 by a factor 2.

######  Claim 5.

Assume that the node $in$ of the multiplier gadget has initial external assets
of €1.

  * (_a_)

In any perfect schedule for the multiplier gadget, if no payment is made by
$in$ to $m_{1}$ at either time 1 or time 2 then no payment is made by $m_{0}$
to $out$ at time 1.

  * (_b_)

There is a perfect schedule $\sigma_{0}$ for the multiplier gadget so that a
payment is made by $in$ at time 3.

  * (_c_)

There is a perfect schedule $\sigma_{1}$ for the multiplier gadget so that a
payment is made by $in$ to $m_{1}$ at time 1 and a payment of €2 is made from
$m_{0}$ to $out$ at time 1.

###### Proof.

Suppose that no payment is made by $in$ to $m_{1}$ at times 1 and 2; so
$m_{1}$ receives no payment at time 1 and makes no payment at time 1. As there
is a payment of €1 from $m_{2}$ to $m_{3}$ at time 1, there must be a payment
of €1 from $m_{0}$ to $m_{2}$ at time 1. Suppose that a payment of €1 is made
from $m_{0}$ to $out$ at time 1. If so then $m_{0}$ can make no payment to
$m_{1}$ at time 2 and $m_{1}$ is bankrupt which yields a contradiction. Hence,
there is no payment from $m_{0}$ to $out$ at time 1. The statement (_a_)
follows.

Consider the schedule whereby:

  * •

at time 1: $m_{0}$ pays €1 to $m_{2}$; $m_{2}$ pays €1 to $m_{3}$

  * •

at time 2: $m_{0}$ pays €1 to $m_{1}$; $m_{1}$ pays €1 to $m_{2}$

  * •

at time 3: $S$ pays €2 to $m_{0}$; $m_{0}$ pays €2 to $out$; $in$ pays €1 to
$m_{1}$.

This yields a perfect schedule and statement (_b_) follows.

Suppose that there is a payment of €1 made from $in$ to $m_{1}$ at time 1; so,
we can also make payments of €1 from $m_{1}$ to $m_{2}$ and from $m_{2}$ to
$m_{3}$ at time 1. Additionally, we can make a payment of €2 from $m_{0}$ to
$out$ at time 1. At time 2, no payments are made. At time 3, we can make
payments of: €2 from $S$ to $m_{0}$; €1 from $m_{0}$ to $m_{2}$; and €1 from
$m_{0}$ to $m_{1}$. This yields a perfect schedule and statement (_c_)
follows.

Our reduction is from 3-Sat-3 (again) to Perfect Scheduling. As before, we
assume that all 3-Sat-3 instances are such that every literal appears at least
once and at most twice and that no clause contains both a literal and its
negation. Given a 3-Sat-3 instance $\phi$ involving $n$ Boolean variables and
$m$ clauses, we construct an IDM instance $(G,D,A^{0})$ as portrayed in Fig. 8
(we omit the formal description of $(G,D,A^{0})$ as it can be immediately
derived from Fig. 8; moreover, we proceed similarly with other IDM instances
that we construct later on). The types of nodes (source, literal, clause and
sink) are as in the proof of Theorem 1, although we have additional so-called
$a$-type nodes, and we abbreviate our multiplier gadget as a square box with
$*2$ inside (note that we have $2n$ distinct copies of our multiplier gadget
where the node $in$ is taken as $a_{i}$ and the node $out$ as the literal node
$x_{i}$ or the literal node $\neg x_{i}$, for $1\leq i\leq n$; of course, we
have $m$ clause nodes, $n$ source nodes, $n$ $a$-type nodes and one sink
node).

$s_{i}$$1$$a_{i}$$1$$x_{i}$$\lnot
x_{i}$$q_{j}$$d$$*2$$*2$$1@3$$1@[1,3]$$1@[1,3]$$2@[1,3]$$2@[1,3]$$1@[1,3]$ if
$v_{i}\in c_{j}$$1@[1,3]$ if $\lnot v_{i}\in c_{j}$$1@1$ Figure 8:
Illustration of the reduction from 3-SAT 3 to Perfect Scheduling restricted to
Directed Acyclic Graphs (DAGs).

######  Claim 6.

If $(G,D,A^{0})$ is a yes-instance of Perfect Scheduling then $\phi$ is a yes-
instance of 3-Sat-3.

###### Proof.

Define the truth assignment $X$ via: if, within $\sigma$, $x_{i}$ receives a
payment of at least €1 at time 1 then $X(v_{i})=True$; otherwise
$X(v_{i})=False$.

Fix $1\leq j\leq m$. We must have that $q_{j}$ pays €1 to $d$ at time 1 and so
$q_{j}$ must receive €1 from some node $x_{i}$ at time 1 or €1 from some node
$\neg x_{i}$ at time 1.

Suppose that $q_{j}$ receives €1 from $x_{\tau_{j}}$ at time 1; in particular,
$v_{\tau_{j}}\in c_{j}$. Hence, $x_{\tau_{j}}$ receives at least €1 from its
corresponding multiplier gadget at time 1 and so, by definition,
$X(v_{\tau_{j}})=True$ with the clause $c_{j}$ satisfied by $X$.

Alternatively, suppose that $q_{j}$ receives €1 from $\neg x_{\tau_{j}}$ at
time 1; in particular, $\neg v_{\tau_{j}}\in c_{j}$. Hence, $\neg
x_{\tau_{j}}$ receives at least €1 from its corresponding multiplier gadget at
time 1. By Claim 5._a_ , there must be a payment of €1 made from
$a_{\tau_{j}}$ to this multiplier gadget at either time 1 or time 2.
Consequently, no payment is made by $a_{\tau_{j}}$ to the complementary
multiplier gadget (that is, the one with a debt to $x_{\tau_{j}}$) at either
time 1 or time 2. By Claim 5._a_ , no payment is received by $x_{i}$ at time 1
and so, by definition, $X(v_{\tau_{j}})=False$ with the clause $c_{j}$
satisfied by $X$. The claim follows.

######  Claim 7.

If $\phi$ is a yes-instance of 3-Sat-3 then $(G,D,A^{0})$ is a yes-instance of
Perfect Scheduling.

###### Proof.

Let $X$ be a satisfying truth assignment for $\phi$. For each clause $c_{j}$,
let $v_{\tau_{j}}$ be a Boolean variable whose occurrence in $c_{j}$, either
via the literal $v_{\tau_{j}}$ or the literal $\neg v_{\tau_{j}}$, leads to
$c_{j}$ being satisfiable. So, we get a list
$L=v_{\tau_{1}},v_{\tau_{2}},\ldots,v_{\tau_{m}}$ of ‘satisfying’ Boolean
variables, possibly with repetitions although no variable appears in the list
more than twice and if a Boolean variable $v$ does appear twice then the
corresponding literals in the two corresponding clauses are both positive or
both negative (of course, this stems from the format of $\phi$ as an instance
of 3-Sat-3): if the occurrences are positive then we say that $v$ has
_positive polarity_ , with _negative polarity_ defined analogously. Note that
any debt from a literal node to a clause node in our IDM instance exists
solely because of the occurrence of the corresponding literal in the
corresponding clause; in particular, we can never have debts from both literal
nodes corresponding to some variable to the same clause node.

Consider the following schedule $\sigma$. At time 1, for each $1\leq j\leq m$:

  * •

$q_{j}$ pays €1 to $d$

  * •

if $v_{\tau_{j}}$ appears in $L$ with positive (resp. negative) polarity then
$x_{\tau_{j}}$ (resp. $\neg x_{\tau_{j}}$) pays €1 to $q_{j}$

  * •

if $v_{\tau_{j}}$ appears in $L$ with positive (resp. negative) polarity then
$a_{\tau_{j}}$ pays €1 to the multiplier gadget which has a debt to
$x_{\tau_{j}}$ (resp. $\neg x_{\tau_{j}}$).

In addition, for each $1\leq j\leq m$, if $v_{\tau_{j}}$ appears in $L$ with
positive (resp. negative) polarity then:

  * •

within the multiplier gadget that has a debt to $x_{\tau_{j}}$ (resp. $\neg
x_{\tau_{j}}$), we include the schedule $\sigma_{1}$ from Claim 5._c_

  * •

within the multiplier gadget that has a debt to $\neg x_{\tau_{j}}$ (resp.
$x_{\tau_{j}}$), we include the schedule $\sigma_{0}$ from Claim 5._b_.

At time 3, for each $1\leq j\leq m$:

  * •

$s_{\tau_{j}}$ pays €1 to $a_{\tau_{j}}$

  * •

if $v_{\tau_{j}}$ appears in $L$ with positive (resp. negative) polarity then
$a_{\tau_{j}}$ pays €1 to the multiplier gadget which has a debt to $\neg
x_{\tau_{j}}$ (resp. $x_{\tau_{j}}$).

Finally, having done the above, add any Boolean variable $v$ not appearing in
$L$ to $L$ and proceed as above with these Boolean variables and assuming that
they have positive polarity (note that the restriction of $X$ to these Boolean
variables has no effect on whether $X$ satisfies $\phi$). What results is a
perfect schedule.

Given that our IDM instance $(G,D,A^{0})$ of Perfect Scheduling can be built
from the instance $\phi$ of 3-Sat-3 in polynomial time, we obtain our result
for the PP variant.

Consider now the AoN variant. As it happens, all of the above schedules are
perfect schedules within the AoN variant and all associated reasoning still
holds. Hence, we have our result for the AoN variant too.

######  Theorem 4.

The problem Perfect Scheduling is NP-complete for the PP and AoN variants even
when we restrict to IDM instances $(G,D,A^{0})$ for which: $G$ is a
multiditree with diameter 6; all debts have monetary amount $\textup{€}1$; and
there is a maximum of 6 debts between any pair of nodes.

###### Proof.

We show that, given an instance $\phi$ of 3-Sat-3, involving $n$ Boolean
variables and $m$ clauses, we can construct in polynomial-time an IDM instance
$(G,D,A^{0})$ where $G$ satisfies the criteria stated in the theorem so that
$(G,D,A^{0})$ admits a perfect schedule iff $\phi$ has a satisfying truth
assignment. As usual, we restrict ourselves to those instances of 3-Sat-3 in
which every literal appears at least once and at most twice and where no
clause contains both a literal and its negation. In particular, we can label
any appearance of any literal in $\phi$ as the first appearance or the second
appearance.

Our reduction is portrayed in Fig. 9. There is a distinct _variable gadget_
for each Boolean variable $v_{i}$, with $1\leq i\leq n$, and a distinct
_clause gadget_ , for each clause $c_{j}$, with $1\leq j\leq m$. There is one
node $r$. The debts in any variable gadget or involving the node $r$ are self-
evident whereas the debts in a clause gadget are more involved.

  * •

If the literal $v_{i}$ is in the clause $c_{j}$ and this appearance is the
first (resp. second) appearance of $v_{i}$ in $\phi$ then there are:

    * –

debts $1@10(i-1)+1$ (resp. $1@10(i-1)+3$) from $b_{j}$ to $a_{j}$ and from
$e_{j}$ to $d_{j}$

    * –

debts $1@10(i-1)+2$ (resp. $1@10(i-1)+4$) from $a_{j}$ to $b_{j}$ and from
$d_{j}$ to $e_{j}$.

  * •

If the literal $\neg v_{i}$ is in the clause $c_{j}$ and this appearance is
the first (resp. second) appearance of $\lnot v_{i}$ in $\phi$ then there are:

    * –

debts $1@10(i-1)+6$ (resp. $1@10(i-1)+8$) from $b_{j}$ to $a_{j}$ and from
$e_{j}$ to $d_{j}$

    * –

debts $1@10(i-1)+7$ (resp. $1@10(i-1)+9$) from $a_{j}$ to $b_{j}$ and from
$d_{j}$ to $e_{j}$.

  * •

If the clause $c_{j}$ has 3 literals (resp. 2 literals) then there are:

    * –

two separate111By having only unit debts in the instance we have that every PP
schedule is also an AoN schedule, and vice versa; for the PP variant we could
instead have a single debt $2@[1,T]$. debts $1@[1,T]$ (resp. a single debt
$1@[1,T]$) from $a_{j}$ to $e_{j}$ and from $e_{j}$ to $a_{j}$.

The legend in Fig. 9 shows the time intervals corresponding to each literal,
which we call the _active windows_ of the literals, and the occurrence of
$x_{1}$ (resp. $\neg x_{2}$, $x_{6}$) in $c_{j}$ in Fig. 9 is the first (resp.
second, first) occurrence.

$r$0$u_{i}$1$y_{i}$0$w_{i}$0$1@10i+1$$1@10i+6$$1@10i+4$$1@10i+9$$1@[10i+1,10i+9]$$1@[10i+1,10i+9]$variable gadget for $v_{i}$$a_{j}$0$b_{j}$1$e_{j}$0$d_{j}$01@1 1@18 1@511@2 1@19 1@52$1@[1,T]$$1@[1,T]$$1@[1,T]$$1@[1,T]$1@1 1@18 1@511@2 1@19 1@52clause gadget for $c_{j}=(x_{1},\lnot x_{2},x_{6})$1@[1,T]1@[1,T]$1@[10i+1,$$10i+9]$$1@[10i+1,$$10i+9$] literal |  active window
---|---
$x_{1}$ |  [1,4]
$\lnot x_{1}$ |  [6,9]
$x_{2}$ |  [11,14]
$\lnot x_{2}$ |  [16,19]
… |  …
$x_{i+1}$ |  $[10i+1,10i+4]$
$\lnot x_{i+1}$ |  $[10i+6,10i+9]$
… |  …
Figure 9: A reduction from 3-Sat-3 to Perfect Scheduling restricted to
multiditrees.

######  Claim 8.

If $(G,D,A^{0})$ is a yes-instance of Perfect Scheduling then $\phi$ is a yes-
instance of 3-Sat-3.

###### Proof.

Suppose that there is a perfect schedule $\sigma$ for $(G,D,A^{0})$. Consider
a clause gadget, corresponding to the clause $c_{j}$. There are 4 debts due
within each active window corresponding to a literal in the clause. Suppose
that the active windows are $[\alpha_{1},\beta_{1}]$, $[\alpha_{2},\beta_{2}]$
and $[\alpha_{3},\beta_{3}]$, with $\beta_{1}<\alpha_{2}$ and
$\beta_{2}<\alpha_{3}$ (we are assuming that our clause has 3 literals but the
arguments for clauses with only 2 literals run analogously). If no payment has
been received by $e_{j}$ from $r$ by time $\beta_{1}+1$ then: the €1 at
$b_{j}$ within the clause gadget must have been used in $\sigma$:

  * •

to pay the debts of $b_{j}$ to $a_{j}$, $a_{j}$ to $e_{j}$ and $e_{j}$ to
$d_{j}$ at time $\alpha_{1}$

  * •

to pay the debts of $d_{j}$ to $e_{j}$, $e_{j}$ to $a_{j}$ and $a_{j}$ to
$b_{j}$ at time $\alpha_{1}+1$,

if the appearance of the corresponding literal is the first; or

  * •

to pay the debts of $b_{j}$ to $a_{j}$, $a_{j}$ to $e_{j}$ and $e_{j}$ to
$d_{j}$ at time $\alpha_{1}+2$

  * •

to pay the debts of $d_{j}$ to $e_{j}$, $e_{j}$ to $a_{j}$ and $a_{j}$ to
$b_{j}$ at time $\alpha_{1}+3=\beta_{1}$,

if the appearance of the corresponding literal is the second (note that the
payments made towards the debts of $a_{j}$ to $e_{j}$ and $e_{j}$ to $a_{j}$
are only partial payments). We have an analogous situation as regards the
interval $[\alpha_{2},\beta_{2}]$ when no payment has been received by $e_{j}$
from $r$ by time $\beta_{2}+1$. However, if no payment has been received by
$e_{j}$ from $r$ by time $\beta_{3}+1$ then we obtain a contradiction as the
debts from $a_{j}$ to $e_{j}$ and from $e_{j}$ to $a_{j}$ will have been fully
paid and consequently $e_{j}$ will be bankrupt at time $\beta_{3}$. Hence,
within $\sigma$, there must be a payment of €1 received by $e_{j}$ from $r$
and this is the only payment made from $r$ to $e_{j}$. Furthermore, there can
be no payment from $e_{j}$ to $r$ strictly before the time at which a payment
is made from $r$ to $e_{j}$ and if a payment is made from $e_{j}$ to $r$ at
the same time that a payment is made from $r$ to $e_{j}$ then this can be
interpreted as no resource leaving or entering the clause gadget, with the
external resource satisfying both debts involving $r$ and $e_{j}$, which
cannot be the case.

Consider now a variable gadget, corresponding to the variable $v_{i}$. At
times $t\in[0,10i]\cup[10i+4,10i+5]\cup[10i+9,T]$ there must be external
assets of (at least) €1 at node $u_{i}$. So, outside the active windows of the
literals associated with the variable $v_{i}$, there must be at least €1 of
external assets at the node $u_{i}$. Also, note that the €1 originating at
node $u_{i}$ can only leave and return to the variable gadget at some times in
$[10i+1,10i+5]$ or in $[10i+6,10i+9]$ but not both. Consequently, at any time,
there is at most €1 of resource that originated within a variable gadget
outside that particular variable gadget.

Consider the time interval $[1,9]$. Within this time interval, the €1
originating at $u_{1}$ is the only euro that might be possibly ‘outside’ the
variable gadget corresponding to $v_{1}$. Call this euro $E$. Suppose $E$
leaves its variable gadget at some time in $[1,4]$. It needs to be back at
$y_{1}$ by time 4 (and will never leave the variable gadget again). Suppose
that $E$ is paid from $r$ to $e_{j}$, for some $j$, within the time interval
$[1,4]$. If the literal $x_{1}$ is not in $c_{j}$ then all debts involving
only $a_{j}$ and $b_{j}$ and all debts involving only $d_{j}$ and $e_{j}$ will
be due at some time outside $[1,4]$ and so $E$ is of no use to the clause
gadget for $c_{j}$. If $E$ is paid from $r$ to $e_{j}$ at time 1 (resp. by
time 3) and the literal $x_{1}$ is in clause $c_{j}$ as the first (resp.
second) appearance then $E$ can be used to pay the debts from $e_{j}$ to
$d_{j}$ at time 1 (resp. time 3) and from $d_{j}$ to $e_{j}$ at time 2 (resp.
time 4). Note that $E$ cannot be used to pay the debt from $a_{j}$ to $b_{j}$
at time 2 or time 4 as it would not get back to its variable gadget by time 4.
Given that $E$ leaves the clause gadget by time 4, no more resource either
enters or leaves the clause gadget. Alternatively, suppose that $E$ leaves the
variable gadget corresponding to $v_{1}$ at some time in $[6,9]$. Exactly the
same argument can be made as that above except with respect to the literal
$\neg x_{1}$ appearing in some clause or other.

Let us continue with the time interval $[11,19]$ and the €1 originating at
$u_{2}$. An analogous argument to that above holds. Note that all clause
gadgets that were previously ‘visited’ by $E$, above, are now ‘closed’ in that
they accept or eject no further resource. Indeed, an analogous argument to
that above holds for every euro originating at some node $u_{i}$. As $\sigma$
is a perfect schedule, every clause gadget must be visited by some euro
originating in some variable gadget and the particular literal corresponding
to the active window during which the euro left its variable gadget must
appear in the clause. Define the truth assignment $X$ via: $X(v_{i})=True$
(resp. $False$) if the euro from the variable gadget corresponding to $v_{i}$
leaves its variable gadget during the active window $[10i+1,10i+4]$ (resp.
$[10i+6,10i+9]$) and visits a clause gadget, with any Boolean variables
$v_{i}$ for which $X(v_{i})$ has not been defined such that $X(v_{i})$ is
defined arbitrarily. Given the above discussion, it should be clear that $X$
satisfies $\phi$.

######  Claim 9.

If $\phi$ is a yes-instance of 3-Sat-3 then $(G,D,A^{0})$ is a yes-instance of
Perfect Scheduling.

###### Proof.

Suppose that $X$ is a satisfying truth assignment for $\phi$. Define the
schedule $\sigma$ as follows.

If $X(v_{i})=True$ then at time $10(i-1)+1$, the euro originating at $u_{i}$
is paid from $u_{i}$ to $y_{i}$ to $w_{i}$ to $r$.

  * •

If the clause $c_{j}$ containing the first appearance of the literal $x_{i}$
exists and has not been visited by some euro originating within a variable
gadget then at time $10i+1$, the euro is paid from $r$ to $e_{j}$ and on to
$d_{j}$. At time $10i+2$, the same euro is paid from $d_{j}$ to $b_{j}$ and on
to $r$.

  * •

If there is no clause containing the literal $x_{i}$ or if the clause gadget
corresponding to the first appearance of $x_{i}$ has already been visited in
the schedule $\sigma$ by some euro originating within a variable gadget, then
do nothing.

  * •

If the clause $c_{j}$ containing the second appearance of the literal $x_{i}$
exists and has not been visited by some euro originating within a variable
gadget then at time $10i+3$, the euro is paid from $r$ to $e_{j}$ and on to
$d_{j}$. At time $10i+4$, the same euro is paid from $d_{j}$ to $b_{j}$ and on
to $r$.

  * •

If there is no clause containing the literal $x_{i}$ or if there is no second
appearance of the literal $x_{i}$ or if the clause gadget corresponding to the
second appearance of $x_{i}$ has already been visited in the schedule $\sigma$
by some euro originating within a variable gadget, then do nothing.

  * •

Our euro at $r$ is paid at time $10i+4$ from $r$ to $w_{i}$ to $y_{i}$ to
$u_{i}$.

If $X(v_{i})=False$ then at time $10i+6$, the euro originating at $u_{i}$ is
paid from $u_{i}$ to $y_{i}$ to $w_{i}$ to $r$.

  * •

If the clause $c_{j}$ containing the first appearance of the literal $\neg
x_{i}$ exists and has not been visited by some euro originating within a
variable gadget then at time $10i+6$, the euro is paid from $r$ to $e_{j}$ and
on to $d_{j}$. At time $10i+7$, the same euro is paid from $d_{j}$ to $e_{j}$
and on to $r$.

  * •

If there is no clause containing the literal $\neg x_{i}$ or if the clause
gadget corresponding to the first appearance of $\neg x_{i}$ has already been
visited in the schedule $\sigma$ by some euro originating within a variable
gadget, then do nothing.

  * •

If the clause $c_{j}$ containing the second appearance of the literal $\neg
x_{i}$ exists and has not been visited by some euro originating within a
variable gadget then at time $10i+8$, the euro is paid from $r$ to $e_{j}$ and
on to $d_{j}$. At time $10i+9$, the same euro is paid from $d_{j}$ to $e_{j}$
and on to $r$.

  * •

If there is no clause containing the literal $\neg x_{i}$ or if there is no
second appearance of the literal $\neg x_{i}$ or if the clause gadget
corresponding to the second appearance of $\neg x_{i}$ has already been
visited in the schedule $\sigma$ by some euro originating within a variable
gadget, then do nothing.

  * •

Our euro at $r$ is paid at time $10i+9$ from $r$ to $w_{i}$ to $y_{i}$ to
$u_{i}$.

Within any clause gadget corresponding to $c_{j}$, the euro originating at
$b_{j}$ is used to pay the debts corresponding to the literal not addressed by
the euro from a variable gadget. It can easily be seen that $\sigma$ is valid
and a perfect schedule.

The result follows, given that the construction of $(G,D,A^{0})$ can clearly
be undertaken in polynomial-time.

In all the above results, the input IDM instance is allowed to have unlimited
(i.e., unbounded) total initial assets which might be unrealistic in
practically relevant financial systems. We now show that even in the highly
restricted case where there is just €1 in initial external assets in total,
Perfect Scheduling still remains NP-complete in the AoN and PP variants.

######  Theorem 5.

The problem Perfect Scheduling is NP-complete in the AoN and PP variants even
when the total value of all initial external assets in any instance is €1.

###### Proof.

The following proof applies to both the AoN and PP variants. Our reduction is
a reduction from the problem Sourced Hamiltonian Path defined as follows.

Sourced Hamiltonian Path

Instance: a digraph $H$ and a vertex $x$

Yes-instance: there exists a Hamiltonian path in $H$ with source $x$.

This problem can be trivially shown to be NP-complete by reducing from the
standard problem of deciding whether a digraph has a Hamiltonian path [20].

Let $H$ be some digraph on the $n$ vertices $\\{x_{i}:1\leq i\leq n\\}$ and
w.l.o.g. let $x=x_{1}$. In order to describe our reduction, we first describe
a gadget, namely the _at-least-once_ gadget. We have one of these gadgets for
each vertex of $H$ and we refer to the gadget corresponding to the vertex
$x_{i}$ of $H$ as at-least-once$(i)$. Our at-least-once gadget can be defined
as in Fig. 10 where the value $T$ is defined as $2n+1$. Note that the gadget
is exactly the nodes and debts within the blue dotted box and so contains its
own copies of nodes $v_{L}$, $v_{C}$ and $v_{R}$ and the $4n-1$ debts
involving them. The nodes $v^{\prime}_{R}$ and $v^{\prime\prime}_{L}$ are not
part of the gadget but are nodes in other gadgets as we now explain.

$v_{L}$$v_{C}$$v_{R}$$v^{\prime}_{R}$$v^{\prime\prime}_{L}$$1@[1,T]$$1@[1,T]$$1@T$$1@T$$1@1~{}1@3~{}\ldots~{}1@T-2$$1@[1,T-1]$$\ldots$$1@[1,T-1]$($n-1$
times)$1@2~{}1@4~{}\ldots~{}1@T-1$$1@[1,T-1]$$\ldots$$1@[1,T-1]$($n-1$
times)$1@T$at-least-once($i$)

Figure 10: An at-least-once gadget. Note that as $T=2n+1$ there are, $n$ €1
debts owed by $v_{L}$ to $v_{C}$ and by $v_{C}$ to $v_{R}$.

Set $T=2n+1$. Our IDM instance $(G,D,A^{0})$ can be defined as follows:

  * •

there is the at-least-once$(i)$ gadget, for $1\leq i\leq n$

  * •

for every edge $(x_{i},x_{j})$ of $H$, there is a debt of €1 from $v_{R}$ of
at-least-once$(i)$ to $v_{L}$ of at-least-once$(j)$ to be paid in the interval
$[1,T]$ and a debt of €1 from $v_{L}$ of at-least-once$(j)$ to $v_{R}$ of at-
least-once$(i)$ to be paid at time $T$

  * •

all nodes have initial external assets of 0 except for node $v_{L}$ of at-
least-once$(1)$ which has initial external assets of 1.

We refer to the single euro of initial external assets as the _initial euro_.
The IDM instance $(G,D,A^{0})$ can clearly be constructed in time polynomial
in $n$.

######  Claim 10.

If $(G,D,A^{0})$ is a yes-instance of Perfect Scheduling then $(H,x)$ is a
yes-instance of Sourced Hamiltonian Path.

###### Proof.

Note that strictly prior to time $T$, the only payment-cycles that can exist
within $G$ involve the two nodes $v_{L}$ and $v_{C}$ of some at-least-once
gadget or the two nodes $v_{C}$ and $v_{R}$ of some at-least-once gadget. Note
also that within some gadget there are $n$ debts of €1 from $v_{L}$ to $v_{C}$
needing to be satisfied and $n-1$ debts of €1 from $v_{C}$ to $v_{L}$. An
analogous statement can be made as regards $v_{C}$ and $v_{R}$. Consequently,
in order to satisfy all debts involving $v_{L}$ and $v_{C}$ within some
gadget, at some odd time in $[1,T-1]$, the initial euro must be within that
gadget so as to satisfy some debt from $v_{L}$ to $v_{C}$ (by moving from
$v_{L}$ to $v_{C}$). Similarly, at some even time in $[1,T-1]$, the initial
euro must be within the gadget so as to satisfy some debt from $v_{C}$ to
$v_{L}$ (by moving from $v_{C}$ to $v_{R}$). Moreover, at any time in
$[1,T-1]$, the initial euro can only satisfy at most one of the debts
mentioned above. Hence, given that $T=2n+1$, at any time in $[1,T-1]$, the
initial euro must be satisfying exactly one of the above debts.

Suppose that the initial euro satisfies some debt from $v_{L}$ to $v_{C}$ in
some at-least-once gadget at time $t$. As the initial euro needs to satisfy
one of the above debts at time $t+1$, we need that at time $t+1$ the initial
euro satisfies a debt from $v_{C}$ to $v_{R}$ in the same gadget. Also, it
cannot be the case that a debt from $v_{C}$ to $v_{R}$ in some gadget is
satisfied by the initial euro before the euro satisfies some debt from $v_{L}$
to $v_{R}$ in the same gadget. As the initial euro starts at $v_{L}$ in at-
least-once$(1)$, our schedule must be such that the initial euro ‘moves’
through the at-least-once gadgets corresponding to every node, entering at the
node $v_{L}$ and exiting at the node $v_{R}$. Consequently, its path within
$G$ corresponds to a path $x=x_{1},x_{2},\ldots,x_{n}$ in $H$ where every node
on this path is distinct and where there is a directed edge from node $x_{i}$
to $x_{i+1}$, for $1\leq i\leq n-1$; that is, a Hamiltonian path in $H$ with
source $x$.

######  Claim 11.

If $(H,x)$ is a yes-instance of Sourced Hamiltonian Path then $(G,D,A^{0})$ is
a yes-instance of Perfect Scheduling.

###### Proof.

Let $x=x_{1},x_{2},\ldots,x_{n}$ be a Hamiltonian path $P$ in the digraph $H$.
Consider the following schedule $\sigma$:

  * •

the initial euro is used so as to pay the following debts:

    * –

€1 at time $2i-1$ from $v_{L}$ to $v_{C}$ in at-least-once$(x_{i})$ and €1 at
time $2i$ from $v_{C}$ to $v_{R}$ in at-least-once$(x_{i})$, for $1\leq i\leq
n$

    * –

€1 at time $2i$ from $v_{R}$ in at-least-once$(x_{i})$ to $v_{L}$ in at-least-
once$(x_{i+1})$, for $1\leq i\leq n-1$

  * •

for any $v_{L}$ and $v_{C}$ within some at-least-once gadget and at any odd
time $t<T$ when a debt is not being paid from $v_{L}$ to $v_{C}$ using the
initial euro, there is a payment-cycle consisting of payments of €1 from
$v_{L}$ to $v_{C}$ and of €1 from $v_{C}$ to $v_{L}$

  * •

for any $v_{C}$ and $v_{R}$ within some at-least-once gadget and at any even
time $t<T$ when a debt is not being paid from $v_{C}$ to $v_{R}$ using the
initial euro, there is a payment-cycle consisting of payments of €1 from
$v_{C}$ to $v_{R}$ and of €1 from $v_{R}$ to $v_{C}$

  * •

for any edge $(x_{i},x_{j})$ of $H$ that does not feature in the Hamiltonian
path $P$, there is a payment-cycle consisting of payments at time $T$ of €1
from $v_{R}$ in at-least-once$(x_{i})$ to $v_{L}$ in at-least-once$(x_{j})$
and of €1 from $v_{L}$ in at-least-once$(x_{j})$ to $v_{R}$ in at-least-
once$(x_{i})$

  * •

the initial euro is used so as to pay the following debts:

    * –

€1 at time $T$ from $v_{R}$ to $v_{L}$ in at-least-once$(x_{i})$, for $1\leq
i\leq n$

    * –

€1 at time $T$ from $v_{L}$ in at-least-once$(x_{i})$ to $v_{R}$ in at-least-
once$(x_{i-1})$, for $2\leq i\leq n$.

The ‘path’ taken by the initial euro within $(G,D,A^{0})$ can be visualized as
in Fig. 11 where the debt arrows are tagged with the time of payment. It is
clear that $\sigma$ is valid and a perfect schedule.

Our main result follows.

$v_{L}$$v_{C}$$v_{R}$$v_{L}$$v_{C}$$v_{R}$$v_{L}$$v_{C}$$v_{R}$$v_{L}$$v_{C}$$v_{R}$$v_{L}$$v_{C}$$v_{R}$$\cdots$$v_{L}$$v_{C}$$v_{R}$at-
least-once($1$)at-least-once($2$)at-least-once($3$)at-least-once($4$)at-least-
once($5$)at-least-
once($n$)$2$$3$$4$$4$$5$$6$$6$$7$$8$$8$$9$$10$$10$$2n-2$$2n-1$$2n$$1$$2$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$$2n+1$

Figure 11: The path taken by the initial euro straightforwardly corresponds to
a sourced Hamiltonian path in the original graph.

Of course, one can obtain additional restrictions on the structure of the IDM
instances for Perfect Scheduling in Theorem 5 by looking at NP-completeness
results relating to Sourced Hamiltonian Path on restricted digraphs; however,
we have refrained from doing so (as nothing of any significance emerges).

We can constraint the digraph $G$ of an instance $(G,D,A^{0})$ of Perfect
Scheduling even further in the AoN variant; indeed, so that it is always a
directed path of length 3. The price we pay is that the initial external
assets are potentially large.

######  Theorem 6.

Consider the problem Perfect Scheduling restricted so that every instance
$(G,D,A^{0})$ is such that $G$ is a directed path of bounded length.

  * (_a_)

If, further, $T$ is restricted to be 2 then the resulting problem is weakly
NP-complete in the AoN variant.

  * (_b_)

If there are no restrictions on $T$ then the resulting problem is strongly NP-
complete in the AoN variant.

###### Proof.

Consider (_a_). We reduce from the problem Partition defined as follows (and
proven in [20] to be weakly NP-complete).

Partition

Instance: a multi-set of integers $S=\\{a_{1},a_{2},\ldots,a_{n}\\}$ with
$sum(S)=2k$

Yes-instance: there exists a partition of $S$ into two subsets $S_{1}$ and
$S_{2}$ such that $sum(S_{1})=sum(S_{2})=k$.

In general, an instance $S=\\{a_{1},a_{2},\ldots,a_{n}\\}$ has size $nb$ where
$b$ is the least number of bits required to express any of the integers of $S$
in binary.

Let $S$ be an instance of Partition of size $nb$. Consider the IDM instance
$(G,D,A^{0})$ in Fig. 12. Note that the time taken to construct $(G,D,A^{0})$
from $S$ is polynomial in $nb$.

$s$$2k$$v$$w$$x$$a_{1}@[1,2]$$a_{2}@[1,2]$…$a_{n}@[1,2]$$k@1$$k@2$$k@1$$k@2$
Figure 12: An IDM instance encoding an instance $\\{a_{1},\ldots,a_{n}\\}$ of
Partition with sum $2k$.

######  Claim 12.

If $(G,D,A^{0})$ is a yes-instance of Perfect Scheduling then $S$ is a yes-
instance of Partition.

###### Proof.

Suppose that there is a valid schedule $\sigma$ for $(G,D,A^{0})$ that is a
perfect schedule. It must be the case that the total amount paid by $s$ at
time 1 is €$k$ and that this payment is immediately paid by $v$ to $w$ and
from $w$ to $x$ at time 1. As we are in the AoN variant, it must be the case
that the sum of a subset of integers of $S$ amounts to $k$. An analogous
argument applies to the payments made at time 2 and the remainder of the
integers in $S$. the claim follows.

######  Claim 13.

If $S$ is a yes-instance of Partition then $(G,D,A^{0})$ is a yes-instance of
Perfect Scheduling.

###### Proof.

Suppose that $S_{1}$ and $S_{2}$ is a partition of $S$ such that
$sum(S_{1})=sum(S_{2})$$=k$. Define the schedule $\sigma$ so that:

  * •

at time 1: $s$ pays €$k$ to $v$; if $a_{i}\in S_{1}$, for $1\leq i\leq n$,
then $v$ pays €$a_{i}$ to $w$; and $w$ pays €$k$ to $x$

  * •

at time 2: $s$ pays €$k$ to $v$; if $a_{i}\in S_{2}$, for $1\leq i\leq n$,
then $v$ pays €$a_{i}$ to $w$; and $w$ pays €$k$ to $x$.

The schedule $\sigma$ is a valid perfect schedule.

The proof of (_a_) follows.

Consider (_b_). We reduce from the strongly NP-complete problem 3-Partit-ion
defined as follows (see [21]).

3-Partition

Instance: a multi-set of integers $S=\\{a_{1},a_{2},\ldots,a_{3m}\\}$, for
some $m\geq 1$, with $sum(S)=mk$

Yes-instance: there exists a partition of $S$ into $m$ triplets
$S_{1},S_{2},\ldots S_{m}$ such that $sum(S_{i})=k$, for each $1\leq i\leq m$.

In general, an instance $S=\\{a_{1},a_{2},\ldots,a_{3m}\\}$ has size $mb$
where $b$ is the least number of bits required to express any of the integers
of $S$ in binary.

Let $S$ be an instance of 3-Partition of size $mb$. By multiplying all
integers by 4 if necessary, we may assume that every integer of $S$ is
divisible by 4 as is $k$. Consider the IDM instance $(G,D,A^{0})$ in Fig. 12.
Note that the time taken to construct $(G,D,A^{0})$ from $S$ is polynomial in
$nb$.

$s$$m(k+3)$$v$$w$$x$$a_{1}+1@[1,m]$$a_{2}+1@[1,m]$$\ldots$$a_{3m}+1@[1,m]$$k+3@1$$k+3@2$$\ldots$$k+3@m$$k+3@1$$k+3@2$$\ldots$$k+3@m$
Figure 13: An IDM instance showing the reduction from 3-Partition to AoN
Perfect Scheduling.

######  Claim 14.

If $(G,D,A^{0})$ is a yes-instance of Perfect Scheduling then $S$ is a yes-
instance of 3-Partition.

###### Proof.

Suppose that there is a valid schedule $\sigma$ for $(G,D,A^{0})$ that is a
perfect schedule. It must be the case that the total amount paid by $s$ at
time $i$, for every $1\leq i\leq m$, is €$k+3$ and that this payment is
immediately paid by $v$ to $w$ and by $w$ to $x$. Suppose that the payment at
time $i$ by $v$ to $w$ pays at least 4 of the debts due. So, there exists
another time $j$, say, where the payments made by $v$ to $w$ pay at most 2
debts. So, we have that either $a_{\alpha}+a_{\beta}+2=k+3$ or
$a_{\alpha}+1=k+3$, for some $1\leq\alpha\neq\beta\leq 3m$. This yields a
contradiction as the right-hand sides of these equations are equivalent to 3
modulo 4 whereas the left-hand sides are not. So, at any time $i$, for $1\leq
i\leq m$, exactly three debts are paid by $v$ to $w$ at time $i$. If
$1\leq\alpha,\beta,\gamma\leq 3m$ are distinct so that debts of monetary
amounts $a_{\alpha}+1$, $a_{\beta}+1$ and $a_{\gamma}+1$ are paid by $v$ to
$w$ at some time then $a_{\alpha}+1+a_{\beta}+1+a_{\gamma}+1=k+3$; that is,
$a_{\alpha}+a_{\beta}+a_{\gamma}=k$. So, we have a yes-instance of
3-Partition. The claim follows.

######  Claim 15.

If $S$ is a yes-instance of 3-Partition then $(G,D,A^{0})$ is a yes-instance
of Perfect Scheduling.

###### Proof.

Suppose that $S$ can be partitioned into triplets so that the sum of the
integers in each triplet is $k$; so, suppose that
$a_{\alpha_{i}}+a_{\beta_{i}}+a_{\gamma_{i}}=k$, for each $1\leq i\leq m$,
where $S=\\{a_{\alpha_{i}},a_{\beta_{i}},a_{\gamma_{i}}:1\leq i\leq m\\}$.
Define the following schedule $\sigma$: at time $i$, for each $1\leq i\leq m$,
$s$ pays €$k+3$ to $v$; $v$ pays
€$a_{\alpha_{i}}+a_{\beta_{i}}+a_{\gamma_{i}}+3=k+3$ to $w$; and $w$ pays
€$k+3$ to $x$. The schedule $\sigma$ is valid and a perfect schedule. The
claim follows.

The main result follows.

###  3.3 Hardness results for Bankruptcy Maximization

We now turn to Bankruptcy Maximization.

######  Theorem 7.

The problem Bankruptcy Maximization is NP-complete in the AoN, PP and FP
variants even when for an instance $(G,D,A^{0})$: $T=2$; $G$ is a directed
acyclic graph with out-degree at most $2$, in-degree at most 3; all monetary
debts are at most €2 per edge; and initial external assets are at most €3 per
bank.

###### Proof.

We build a polynomial-time reduction from the problem 3-Sat-3, with the usual
restrictions on instances (see the proof of Theorem 1). Suppose that we have
some instance $\phi$ of 3-Sat-3 where there are $n$ Boolean variables and $m$
clauses. We start with the _chain gadget_ chain$(l)$, where $l\geq 1$, as
portrayed in Fig. 14 (note that the gadget is the path of $l$ nodes within the
blue dotted box). The key point about any chain gadget is that in some
schedule: if at time 1, node $u$ does not make a payment to node $m_{1}$ then
$u$ and all the nodes of the chain gadget are bankrupt; and if at time 1, $u$
pays its debt to $m_{1}$ then none of the nodes of the chain gadget is
bankrupt. As in our proof of Theorem 2, we first work in the PP variant unless
otherwise stated, though the reasoning will apply to the AoN and FP variants
as well.

$u$$m_{1}$$m_{2}$$m_{3}$$m_{l}$$1@1$$1@1$$1@1$$1@1$$1@1$…chain($l$) Figure 14:
The chain gadget. In any valid schedule, either $p_{u,m_{1}}^{1}<1$ and all
vertices $m_{i}$ are bankrupt, or $p_{u,m_{1}}^{1}=1$ and no vertices $m_{i}$
are bankrupt.

We now define variable nodes $\\{s_{i}:1\leq i\leq n\\}$, literal nodes
$\\{x_{i},\neg x_{i}:1\leq i\leq n\\}$, clause nodes $\\{q_{j}:1\leq j\leq
m\\}$ and a sink node $d$ analogously to as in the proof of Theorem 1 and
include the debts as depicted in Fig. 15 so as to obtain our IDM instance
$(G,D,A^{0})$. Note that the chain gadgets corresponding to the different
literal nodes are all distinct and $|c_{j}|$ denotes the number if literals in
the clause $c_{j}$ of $\phi$.

$s_{i}$$3$$x_{i}$$\lnot
x_{i}$$q_{j}$$d$chain($m+1$)chain($m+1$)$3@1$$3@1$$1@2$ if $\lnot v_{i}\in
c_{j}$$1@2$ if $v_{i}\in c_{j}$$|c_{j}|@2$$1@1$$1@1$ Figure 15: An IDM
instance illustrating the reduction from 3-SAT 3 to Bankruptcy Maximization,
using chain gadgets.

Note that because all debts of $(G,D,A^{0})$ are due at an exact time, rather
than over an interval, reasoning in the AoN variant is identical to reasoning
in the PP variant.

######  Claim 16.

In any valid schedule $\sigma$ for $(G,D,A^{0})$ in which $c\geq 0$ variable
nodes $s_{i}$ either pay €3 to $x_{i}$ or €3 to $\neg x_{i}$:

  * •

all $n$ variable nodes are bankrupt

  * •

exactly $n$ literal nodes are bankrupt

  * •

exactly $c(m+1)$ chain nodes are bankrupt.

Consequently, this amounts to exactly $2n+c(m+1)$ bankrupt nodes with any
other bankrupt nodes necessarily being clause nodes.

###### Proof.

Suppose that in the valid schedule $\sigma$, $s_{i}$, for some $1\leq i\leq
n$, pays €1 to a node from $\\{x_{i},\neg x_{i}\\}$ at time 1 and €2 to the
other node from $\\{x_{i},\neg x_{i}\\}$ at time 1. Since both $x_{i}$ and
$\neg x_{i}$ have €1 at time 1, both must pay €1 to their corresponding chain
gadget; so, none of the nodes of either of these chain gadgets is bankrupt. As
any variable and its negation both appear at least once in some clause of
$\phi$, exactly one of the nodes $x_{i}$ and $\neg x_{i}$ is bankrupt at time
2.

Alternatively, suppose that $s_{j}$, for $1\leq j\leq n$, pays €3 to either
$x_{j}$ or $\neg x_{j}$ at time 1. So, the literal node to which $s_{j}$ makes
no payment is bankrupt at time 1 as are all the nodes of its corresponding
chain gadget. As any variable and its negation both appear at least once in
some clause of $\phi$, exactly one of the nodes $x_{j}$ and $\neg x_{j}$ is
bankrupt at time 2.

In any case, we have: $n$ variable nodes that are bankrupt; $n$ literal nodes
that are bankrupt; and $c(m+1)$ chain nodes that are bankrupt. This results in
$2n+c(m+1)$ bankrupt nodes. As the sink node $d$ cannot be bankrupt, the claim
follows.

######  Claim 17.

If $((G,D,A^{0}),2n+n(m+1)+m)$ is a yes-instance of Bankruptcy Maximization
then $\phi$ is a yes-instance of 3-Sat-3.

###### Proof.

Suppose that there exists a valid schedule $\sigma$ that results in at least
$2n+n(m+1)+m$ bankruptcies. So, by Claim 16, every variable node $s_{i}$ pays
€3 to either $x_{i}$ or $\neg x_{i}$ and also every clause node $q_{j}$ is
bankrupt in $\sigma$. The reason a clause node $q_{j}$ is bankrupt is because
there is some literal $v_{i}$ or $\neg v_{i}$ in clause $c_{j}$ but where
$\neg x_{i}$ or $x_{i}$, respectively, receives no payment from $s_{i}$.
Define the truth assignment $X$ on the variables of $\phi$ so that
$X(v_{i})=True$ iff $x_{i}$ receives a payment of €3 from $s_{i}$, for $1\leq
i\leq n$. This truth assignment satisfies every clause of $\phi$.

######  Claim 18.

If $\phi$ is a yes-instance of 3-Sat-3 then $((G,D,A^{0}),2n+n(m+1)+m)$ is a
yes-instance of Bankruptcy Maximization.

###### Proof.

Suppose that there is a satisfying truth assignment $X$ for $\phi$. Consider
the following schedule $\sigma$:

  * •

at time 1, every $s_{i}$ pays: €3 to $x_{i}$ if $X(v_{i})=True$; and €3 to
$\neg x_{i}$ if $X(v_{i})=False$

  * •

if $x_{i}$ (resp. $\neg x_{i}$) received €3 from $s_{i}$ at time 1 then:

    * –

at time 1, it pays €1 to its corresponding chain gadget so as to satisfy all
debts in the gadget

    * –

at time 2, it pays €1 to each clause node $q_{j}$ for which the literal $\neg
v_{i}\in c_{j}$ (resp. $v_{i}\in c_{j}$)

  * •

if $x_{i}$ (resp. $\neg x_{i}$) received no payment from $s_{i}$ at time 1
then at times 1 and 2 then it can make no payments

  * •

each $q_{j}$ makes a payment of however many euros it has to $d$ at time $2$
(note that it never received more than €$|c_{j}|$).

The schedule $\sigma$ is clearly valid. By Claim 16, we have at least
$2n+n(m+1)$ bankrupt nodes with any additional bankrupt nodes necessarily
clause nodes. Consider some clause node $q_{j}$ containing some literal
$v_{i}$ so that $X(v_{i})=True$. By definition, $\neg x_{i}$ receives no
payment from $s_{i}$ at time 1 and so the debt of €1 at time 2 from $\neg
x_{i}$ to $q_{j}$ is not paid. Consequently, $q_{j}$ is bankrupt. Hence, we
have exactly $2n+n(m+1)+m$ bankrupt nodes and the claim follows.

Note that the above reasoning clearly holds in the AoN variant (since in the
schedules we consider all debts are paid either in full or not at all) as well
as in the FP variant (since in order for $s_{i}$ to bankrupt one of the chains
attached to $x_{i}$ and $\lnot x_{i}$ it must pay _strictly_ less than £1 to
the bankrupt node and hence _at least_ £2 to the “surviving” node). As the
construction of $((G,D,A^{0}),2n+n(m+1)+m)$ can be completed in time
polynomial in $n$, the result follows.

Just as we did with Perfect Scheduling in Theorem 6, we can restrict
Bankruptcy Maximization in the AoN variant so that any IDM $(G,D,A^{0})$ in
any instance is such that $G$ is a directed path of bounded length (here 2).

######  Theorem 8.

Consider the problem Bankruptcy Maximization restricted so that every instance
$((G,D,A^{0}),k)$ is such that $G$ is a directed path of length 3. If,
further, $T$ is restricted to be 2 then the resulting problem is weakly NP-
complete in the AoN variant.

###### Proof.

We reduce from the weakly NP-complete problem Subset Sum defined as follows
(see [21]).

Subset Sum

Instance: a multi-set of integers $S=\\{a_{1},a_{2},\ldots,a_{n}\\}$ and an
integer $k$

Yes-instance: there exists a subset $S_{1}$ of $S$ so that the sum of the
numbers in $S_{1}$ is $k$.

In general, an instance $S=\\{a_{1},a_{2},\ldots,a_{n}\\}$ has size $nb$ where
$b$ is the least number of bits required to express any of the integers of $S$
in binary. We may clearly assume that every integer $a_{i}$ is at least 2 (by
doubling every integer $a_{i}$ and $k$ if necessary).

Let $S$ be an instance of Subset Sum of size $nb$. By doubling all integers if
necessary, we may assume that every integer of $S$ is at least 2. Consider the
IDM instance $(G,D,A^{0})$ in Fig. 16 (for which $T=2$). The value $A$ in Fig.
16 is the sum of all integers in $S$. Note that the time taken to construct
$(G,D,A^{0})$ from $S$ is polynomial in $nb$.

$u$$A$$v$$k$$w$$a_{1}@[1,2]$…$a_{n}@[1,2]$$1@1$$A@2$ Figure 16: An IDM
instance corresponding to an instance of Subset Sum.

######  Claim 19.

If $((G,D,A^{0}),1)$ is a yes-instance of Bankruptcy Maximization then $S$ is
a yes-instance of Subset Sum.

###### Proof.

Suppose that $\sigma$ is a valid schedule within which there is at least 1
bankruptcy in the IDM instance $(G,D,A^{0})$. The nodes $u$ and $w$ are never
bankrupt; so, $v$ must be bankrupt within $\sigma$. At time 2, the node $v$
necessarily pays off all of the unpaid debts to $w$ of monetary amount greater
than €1, as it receives sufficient funds from $u$ at time 2 to do this. Hence,
$v$ must be bankrupt at time 1; that is, $v$ does not pay its debt to $w$ of
monetary amount €1 at time 1. As $\sigma$ is valid, $v$ is not withholding at
time 1 and the only way for this to happen is for $v$ to pay debts to $w$
amounting to €$k$. That is, we have a subset of integers of $S$ whose total
sum is $k$; that is, $S$ is a yes-instance of Subset Sum. The claim follows.

######  Claim 20.

If $S$ is a yes-instance of Subset Sum then $((G,D,A^{0}),1)$ is a yes-
instance of Bankruptcy Maximization.

###### Proof.

Suppose that the subset $S_{1}$ of $S$ is such that $sum(S_{1})=k$. W.l.o.g.
let $S_{1}=\\{a_{1},a_{2},\ldots,a_{r}\\}$. Define the schedule $\sigma$ as:
at time 1, $v$ pays the debts $a_{1}@[1,2],\ldots,a_{r}@[1,2]$; and at time
$2$, $u$ pays its debt to $v$ and $v$ pays the debts
$a_{r+1}@[1,2],\ldots,a_{n}@[1,2]$. Note that this is a valid schedule, as no
node is withholding at any time, within which $v$ is bankrupt. The claim
follows.

The main result follows.

###  3.4 Polynomial-time algorithms

In this section we show that Bailout Minimization in the FP variant is
solvable in polynomial-time and also that Bailout Minimization in the PP
variant is solvable in polynomial-time when our IDM instances are restricted
to out-trees. We begin with the FP variant result.

######  Theorem 9.

The problem Bailout Minimization in the FP variant is solvable in polynomial-
time.

###### Proof sketch.

We show that, in the FP variant, an instance of Bailout Minimization
$((G,D,A^{0}),b)$ can be encoded as a linear program. The following
constraints can all be expressed as linear expressions:

  * •

$\text{sum}(B)\leq b$

  * •

the definitions of $I_{v}^{t}$, $O_{v}^{t}$ and $e_{v}^{t}$ are all linear
combinations of the payment variables $p_{e}^{t}$ as defined as in Section 2.3

  * •

we set $e_{v}^{0}:=A^{0}[v]+B[v]$; that is, the starting assets of $v$ are its
initial external assets combined with the bailout at $v$ according to the
bailout vector $B$

  * •

the constraints on valid schedules in Definition 1 are all expressed as linear
combinations

  * •

we additionally impose that no banks are bankrupt under a schedule, or,
equivalently, that no debt is ever overdue; that is, for every edge $e$ and
debt $D(e)=(a,t_{1},t_{2})$, we have that
$\sum_{t\in[t_{1},t_{2}]}p_{e}^{t}=a$.

Any assignment to $B$ and to the payment variables satisfying the above is
necessarily a perfect valid schedule for $((G,D,A^{0}),b)$. As linear programs
can be solved in polynomial-time, our result follows.

Note the limitations of the use of linear programming for other problems. For
Bailout Minimization in the PP variant, proceeding as in the proof of Theorem
9 results is an integer linear program, the solution of which is NP-complete
in general. Moreover, we have already proven Perfect Scheduling, the special
case of Bailout Minimization with $b$ fixed to $0$, to be NP-complete in the
PP variant through the proofs in Theorems 3, 4 and 5. As regards trying to use
linear programming for Bankruptcy Minimization in the FP variant, it is not
possible to express a constraint on the number of bankruptcies through a
linear combination of the payment variables; indeed, we have already proven
Bankruptcy Minimization in the FP variant to be NP-complete in Theorems 1 and
2.

We can obtain tractability results for the problem Bailout Minimization if we
restrict the IDM instances.

######  Theorem 10.

The problem Bailout Minimization in the PP variant is solvable in polynomial-
time when our IDM instances are restricted to out-trees.

###### Proof.

Let $((G,D,A^{0}),b)$ be an instance of Bailout Minimization so that $G$ is an
out-tree. Suppose that $G$ has node set $\\{u_{i}:1\leq i\leq n\\}$. We need
to decide whether we can increase the initial external assets of each node
$u_{i}$ by $b_{i}$ so that $\sum_{i}b_{i}\leq b$ and $(G,D,A^{0}+B)$ has a
perfect schedule, where $B=(b_{1},b_{2},\ldots,b_{n})$; that is, whether
$(G,D,A^{0})$ is ‘$b$-bailoutable’ via a _$b$ -bailout vector_ $B$. Our
intention is to repeatedly amend $(G,D,A^{0})$ so that $(G,D,A^{0})$ is
‘$b$-bailoutable’ iff the resulting IDM instance is
‘$b^{\prime}$-bailoutable’, for some amended $b^{\prime}$; in such a case, we
say that the two problem instances are _equivalent_. We will then work with
the (simplified) amended instance.

We proceed as follows. First, identify nodes $v$ for which, at any time $t$,
the sum of all debts $v$ must pay by time $t$ minus the sum of all debts which
could be paid to $v$ by time $t$ exceeds $v$’s initial external assets
$e_{v}^{0}$. We call these nodes _prefix-insolvent_. Note that if a node $v$
is prefix-insolvent then under any perfect schedule $\sigma$, we would have
$I_{v}^{[t]}+e_{v}^{0}<O_{v}^{[t]}$, violating a validity constraint, and
hence there is no such perfect schedule. Also note that every insolvent node
is prefix-insolvent (namely by taking $t=T$). For any node that is prefix-
insolvent, increase the initial external assets by the minimal amount that
causes the node to cease to be prefix-insolvent and simultaneously decrease
the bailout amount by this value. Our new instance is clearly equivalent with
our initial instance. If, in doing this, the bailout amount becomes less than
0 then we answer ‘no’ and we are done. So, we may assume that none of our
nodes is prefix-insolvent.

Before we start, we make a simple amendment to the debts $D$: we replace any
debt from node $u$ to node $v$ of the form $a@[t_{1},t_{2}]$, where $a>1$,
with $a$ distinct debts $1@[t_{1},t_{2}]$. Our resulting instance, with
bailout $b$, is equivalent to our initial instance, with bailout $b$, as we
are working within the PP variant. This amendment simplifies some of the
reasoning coming up. Note that it may be necessary to simulate this operation
rather than actually performing it (since if $a$ is exponential in the
instance size then the operation takes exponential time), but that the
reasoning which follows can easily be “scaled up” to deal with non-unit
amounts.

Consider a leaf node $v$ and its parent $u$ in the out-tree $G$. Replace every
debt of the form $1@[t_{1},t_{2}]$ from $u$ to $v$ by the debt $1@t_{2}$ and
denote the revised instance by $(G,D^{\prime},A^{0})$. Let $\sigma$ be a
perfect valid schedule for $(G,D,A^{0}+B)$ (here, and throughout, we write $B$
to denote some $b$-bailout vector; that is, some assignment of resource to the
nodes of $G$ so that the total bailout amount does not exceed the total
available $b$). Define the schedule $\sigma^{\prime}$ for
$(G,D^{\prime},A^{0}+B)$ by amending any payment from $u$ to $v$ of some debt
$1@[t_{1},t_{2}]$ so that the payment is made at time $t_{2}$. The schedule
$\sigma^{\prime}$ is clearly a perfect valid schedule for
$(G,D^{\prime},A^{0}+B)$. Furthermore, any perfect valid schedule for
$(G,D^{\prime},A^{0}+B)$ is a perfect valid schedule for $(G,D,A^{0}+B)$.
Hence, we can replace $((G,D,A^{0}),b)$ by $((G,D^{\prime},A^{0}),b)$, as
these instances are equivalent. We can proceed as above for every leaf node
and its parent and so assume that all debts from a parent to a leaf are due at
some specific time only; that is, have a singular time-stamp and are of the
form $1@t$. Note also that no node of $G$ is insolvent.

Suppose that we have two leaf nodes $v$ and $w$ with the same parent $u$. We
can replace $v$ and $w$ with a ‘merged’ node $vw$ so that all debts from $u$
to $v$ or from $u$ to $w$ are now from $u$ to $vw$. Our initial problem
instance is clearly equivalent to our amended problem instance (note that we
never assign bailout resource to either $v$ or $w$ as this is pointless). We
can proceed likewise for all such triples $(u,v,w)$. Hence, we may assume that
our digraph $G$ is such that: no two leaves have a common parent; all debts to
a leaf node have monetary amount €1 and have a singular time-stamp; and no
node in $G$ is prefix-insolvent.

Suppose that we have a leaf node $w$ that is the only child of its parent node
$v$ whose parent is $u$ (such a node $w$ exists: take a leaf of the tree that
is furthest away from the root). We may assume that $v$ has no initial
external assets as we would simply use these assets to pay as many debts to
$w$ as possible (in increasing order of time-stamp); that is, we could remove
all these debts from $D$ along with the corresponding amount from the initial
external assets of $v$. If the result of doing this is that there are no debts
from $v$ to $w$ then we remove $w$ from $G$ and any remaining initial external
assets from $v$. We would then repeat all of the above amendments until it is
the case that our nodes $u$, $v$ and $w$ are such that $v$ has no external
assets.

By the above, every debt from $v$ to $w$ is of the form $1@t$. Let
$t^{\prime}$ be the minimum time-stamp for all debts from $v$ to $w$ and let
$d_{v}$ be a debt from $v$ to $w$ of the form $1@t^{\prime}$. Consider the
debts from $u$ to $v$: these have the form $1@[t_{1},t_{2}]$. There are
various cases:

  * (_a_)

there is a debt $d_{u}$ from $u$ to $v$ of the form $1@[t_{1},t_{2}]$ where
$t_{2}\leq t^{\prime}$

  * (_b_)

there is no debt from $u$ to $v$ of the form $1@[t_{1},t_{2}]$ where
$t_{2}\leq t^{\prime}$ but there is a debt from $u$ to $v$ of the form
$1@[t_{1},t_{2}]$ where $t_{1}\leq t^{\prime}\leq t_{2}$

  * (_c_)

there is no debt from $u$ to $v$ of the form $1@[t_{1},t_{2}]$ where
$t_{1}\leq t^{\prime}$.

The nodes $u$, $v$ and $w$ can be visualized as in Fig. 17(d) and the three
cases above in Fig. 17(a)–(c).

$t_{1}[$$]t_{2}$$t_{3}[$$]t_{4}$$t_{5}[$$]t_{6}$$t_{7}[$$]t_{8}$$t^{\prime}$
(a)

$t_{1}[$$]t_{2}$$t_{3}[$$]t_{4}$$t_{5}[$$]t_{6}$$t_{7}[$$]t_{8}$$t^{\prime}$
(b)

$t_{1}[$$]t_{2}$$t_{3}[$$]t_{4}$$t_{5}[$$]t_{6}$$t_{7}[$$]t_{8}$$t^{\prime}$
(c)

$w$$v$$u$$1@[t_{1},t_{2}]$$1@[t_{3},t_{4}]$$\ldots$$1@t^{\prime}$$1@t^{\prime\prime}$$\ldots$
(d)

$w$$v$$u$$v^{\prime}$$1@[t_{1},t_{2}]$$1@[t_{3},t_{4}]$$\ldots$$1@t^{\prime}$$1@t^{\prime\prime}$$\ldots$$1@t^{\prime}$
(e)

Figure 17: Cases when a leaf has a parent with one child in our algorithm for
PP Bailout Minimization on out-trees.

Case (_a_): We amend $G$ by: introducing a new node $v^{\prime}$ whose parent
is $u$ and a new debt $d^{\prime}$ from $u$ to $v^{\prime}$ of the form
$1@[t_{1},t_{2}]$; removing the debt $d_{u}$ from $u$ to $v$; and removing the
debt $d_{v}$ from $v$ to $w$. Denote this revised IDM instance by
$(G^{\prime},D^{\prime},A^{0})$. Suppose that there exists a perfect valid
schedule $\sigma$ for $(G,D,A^{0}+B)$. Define the schedule $\sigma^{\prime}$
for $(G^{\prime},D^{\prime},A^{0}+B)$ from $\sigma$ by: changing the payment
from $u$ to $v$, at time $t$ where $t_{1}\leq t\leq t_{2}\leq t^{\prime}$ and
covering the debt $d_{u}$, so that the payment is made from $u$ to
$v^{\prime}$ at time $t$ (so as to cover the new debt $d^{\prime}$); and
dropping the payment, at time $t^{\prime}$, that covers the debt $d_{v}$. The
resulting schedule $\sigma^{\prime}$ is clearly valid and perfect. Conversely,
suppose that we have a perfect valid schedule $\sigma^{\prime}$ for
$(G^{\prime},D^{\prime},A^{0}+B)$. Define the schedule $\sigma$ for
$(G,D,A^{0}+B)$ from $\sigma^{\prime}$ by: changing the payment from $u$ to
$v^{\prime}$ at time $t$ where $t_{1}\leq t\leq t_{2}\leq t^{\prime}$ and
covering the debt $d^{\prime}$, so that the payment is made from $u$ to $v$ at
time $t$, so as to cover the debt $d_{u}$; and using the €1 received by $v$ so
as to cover the debt $d_{v}$ from $v$ to $w$. The resulting schedule $\sigma$
is clearly a perfect valid schedule for $(G,D,A^{0}+B)$. Consequently,
$((G,D,A^{0}),b)$ and $((G^{\prime},D^{\prime},A^{0}),b)$ are equivalent and
we can work with $((G^{\prime},D^{\prime},A^{0}),b)$.

Case (_b_): Let $D_{u}$ be the set of debts from $u$ to $v$ and let $D_{v}$ be
the set of debts from $v$ to $w$. Order the $k$ debts of $D_{v}$ in increasing
order of time-stamp as $d_{v}=d_{1},d_{2},\ldots,d_{k}$ where the
corresponding time-stamps are
$t^{\prime}=\bar{t}_{1},\bar{t}_{2},\ldots,\bar{t}_{k}$ (there may be
repetitions). Suppose that for some $1\leq i\leq k$, the number of debts in
$D_{u}$ of the form $1@[t_{1},t_{2}]$ with $t_{1}\leq\bar{t}_{i}$ is strictly
less than $i$. Consequently, at time $\bar{t}_{i}$, the debt $d_{i}$ cannot be
paid and we necessarily need to give $v$ some bailout amount, €$c>1$ say, to
cover the $c$ debts that cannot be paid by $v$ at time $\bar{t}_{i}$. We do
this and reduce the overall bailout amount by €$c$. We then delete debts
$d_{1},d_{2},\ldots,d_{c}$ from $G$ and remove the bailout amount of €$c$ from
$v$. If doing this results in there being no remaining debts from $v$ to $w$
then we delete $w$ from $G$. Irrespective of this, the resulting instance
$((G^{\prime},D^{\prime},A^{0}),b^{\prime})$, where $b^{\prime}=b-c$, is
equivalent to $((G,D,A^{0}),b)$. We would then repeat all of the amendments
above and so w.l.o.g. we may assume that we are in Case (_b_) and for every
$1\leq i\leq k$, the number of debts in $D_{u}$ of the form $1@[t_{1},t_{2}]$
with $t_{1}\leq\bar{t}_{i}$ is at least $i$. In particular, there are at least
$k$ debts in $N_{u}$.

Suppose that $\sigma$ is a valid perfect schedule for $(G,D,A^{0}+B)$, for
some $B$ where $v$ receives a bailout amount of €$c>0$. Suppose further that
there is no $B^{\prime}$ where there is a valid perfect schedule for
$(G,D,A^{0}+B^{\prime})$ with $v$ receiving a bailout of less than €$c$. The
reason that $v$ receives the bailout amount of €$c$ is that in the schedule
$\sigma$, if we ignore the payments by $v$ that use the bailout amount at $v$
then there are $c$ debts from $d_{1},d_{2},\ldots,d_{k}$ that are not paid on
time; let us call these debts the ‘bad’ debts. Note that for each bad debt,
there is a debt from $u$ to $v$ that _might_ have been paid at a time early
enough to cover the debt but wasn’t. Let $e_{1},e_{2},\ldots,e_{c}$ be
distinct debts from $D_{u}$ that might have been paid earlier so as to enable
the payment of the bad debts. Amend the bailout $B$ so that the €$c$ formerly
given as bailout to $v$ is now given to $u$ and denote this revised bailout by
$B^{\prime}$. Revise the schedule $\sigma$ so that for each $1\leq i\leq c$,
€1 of bailout at $u$ is used to pay the debt $e_{i}$ at the earliest time
possible. Doing so results in us being able to pay all bad debts on time;
hence, we have a perfect schedule for $(G,D,A^{0}+B^{\prime})$ where $v$
receives no bailout. This yields a contradiction and so if there is a bailout
$B$ and a valid perfect schedule for $(G,D,A^{0}+B)$ then there is a bailout
$B^{\prime}$ and a valid perfect schedule for $(G,D,A^{0}+B^{\prime})$ where
$v$ receives no bailout funds. We shall return to this comment in a moment.

From the debts of $D_{u}$, we choose a debt $d_{u}=1@[t_{1},t_{2}]$, where
$t_{1}\leq t^{\prime}\leq t_{2}$, so that from amongst all of the debts of
$D_{u}$ of the form $1@[t_{3},t_{4}]$, where $t_{3}\leq t^{\prime}\leq t_{4}$,
we have that $t_{2}\leq t_{4}$; that is, from all of the debts of $D_{u}$ that
‘straddle’ $t^{\prime}$, $d_{u}$ is a debt whose right-most time-stamp is
smallest. We amend $G$ by: introducing a new node $v^{\prime}$ and a new debt
$d^{\prime}$ from $u$ to $v^{\prime}$ of the form $1@t^{\prime}$; removing the
debt $d_{u}$ from $u$ to $v$; and removing the debt $d_{v}$ from $v$ to $w$.
Denote this revised IDM instance by $(G^{\prime},D^{\prime},A^{0})$; it can be
visualized as in Fig. 17(e).

Suppose that $\sigma$ is a valid perfect schedule for $(G,D,A^{0}+B)$, for
some $B$. From above, we may assume that there is no bailout to node $v$ in
$B$. Consider the payment by $v$ to $w$ of the debt $d_{v}$. If the actual €1
that pays this debt came from the payment of a debt from
$D_{u}\setminus\\{d_{u}\\}$ of the form $1@[t_{3},t_{4}]$ (where $t_{3}\leq
t^{\prime}\leq t_{4}$), then we can amend $\sigma$ so that we use this €1 to
pay the debt $d_{u}$ at the time $t^{\prime}$ and use the €1 that paid the
debt $d_{u}$ to pay the debt $1@[t_{3},t_{4}]$ (at whatever time $d_{u}$ was
paid); that is, we swap the times of the payment of the debts $d_{u}$ and
$1@[t_{3},t_{4}]$ in $\sigma$ except that we now pay $d_{u}$ at time
$t^{\prime}$. If the actual €1 that pays $d_{v}$ came from the payment of
$d_{u}$ then we can amend the payment time of $d_{u}$ to $t^{\prime}$ (if
necessary).

Build a schedule $\sigma^{\prime}$ in $(G^{\prime},D^{\prime},A^{0}+B)$ from
$\sigma$ by: instead of paying $d_{u}$ (at time $t^{\prime}$), we pay the new
debt $d^{\prime}$ from $u$ to $v^{\prime}$; and we remove the payment of the
debt $d_{v}$. The schedule $\sigma^{\prime}$ is clearly a valid perfect
schedule of $(G^{\prime},D^{\prime},A^{0}+B)$. Conversely, if
$\sigma^{\prime}$ is a valid perfect schedule of
$(G^{\prime},D^{\prime},A^{0}+B)$, we can build a schedule $\sigma$ for
$(G,D,A^{0}+B)$ from $\sigma^{\prime}$ by: instead of paying the debt
$d^{\prime}$ (at time $t^{\prime}$), we pay the debt $d_{u}$ at time
$t^{\prime}$; and we use this €1 to pay immediately the debt $d_{u}$. The
schedule $\sigma$ is clearly a valid perfect schedule of $(G,D,A^{0}+B)$.
Hence, $((G,D,A^{0}),b)$ and $((G^{\prime},D^{\prime},A^{0}),b)$ are
equivalent and we can work with $((G^{\prime},D^{\prime},A^{0}),b)$.

Case (_c_): Suppose that there is no debt from $u$ to $v$ of the form
$1@[t_{1},t_{2}]$ where $t_{1}\leq t^{\prime}$. This case cannot happen as we
have ensured that no node of $G$ is insolvent.

By iteratively applying all of the amendments to the instance
$((G,D,A^{0}),b)$, as laid out above, we reduce $((G,D,A^{0}),b)$ to an
equivalent instance $((G^{\prime},D^{\prime},$$(A^{\prime})^{0}),b^{\prime})$
where $G$ consists of a solitary directed edge and all debts have a singular
time-stamp. The process of reduction can clearly by undertaken in time
polynomial in the size of the initial instance $((G,D,A^{0}),b)$ and the
resulting instance $((G^{\prime},D^{\prime},(A^{\prime})^{0}),b^{\prime})$ can
clearly be solved in time polynomial in the size of the initial instance
$((G,D,A^{0}),b)$. Hence, Bailout Minimization is solvable in polynomial-time.

Our polynomial-time algorithm for Bailout Minimization, and so Perfect
Scheduling, in the PP variant in Theorem 10 when we restrict to out-trees
contrasts with the NP-completeness of Perfect Scheduling when we restrict to
directed acyclic graphs or multiditrees, as proven in Theorem 3 and Theorem 4,
respectively.

##  4 Conclusion and open problems

This paper introduces the _Interval Debt Model (IDM)_ , a new model seeking to
capture the temporal aspects of debts in financial networks. We investigate
the computational complexity of various problems involving debt scheduling,
bankruptcy and bailout with different payment options (All-or-nothing (AoN),
Partial (PP), Fractional (FP)) in this setting. We prove that many variants
are hard even on very restricted inputs but certain special cases are
tractable. For example, we present a polynomial time algorithm for PP Bailout
Minimization where the IDM graph is an out-tree. However, for a number of
other classes (DAGs, multitrees, total assets are $\textup{€}1$), we show that
the problem remains NP-hard. This leaves open the intriguing question of the
complexity status of problems which are combinations of two or more of these
constraints, most naturally on multitrees which are also DAGs, an immediate
superclass of our known tractable case.

We prove that FP Bailout Minimization is polynomial-time solvable by
expressing it as a Linear Program. Can a similar argument be applied to some
restricted version of FP Bankruptcy Minimization (which is NP-Complete, in
general)? A natural generalization is simultaneous Bailout and Bankruptcy
minimization i.e. can we allocate $\textup{€}b$ in bailouts such that a
schedule with at most $k$ bankruptcies becomes possible. Variations of this
would be of practical interest. For example, if regulatory authorities can
allocate bailouts as they see fit, but not impose specific payment times, it
would be useful to consider the problem of allocation of $\textup{€}b$ in
bailouts such that the maximum number of bankruptcies in any valid schedule is
at most $k$. Conversely, where financial authorities can impose specific
payment times, the combination of the problems Bankruptcy Minimization and
Bailout Minimization would be more applicable.

Finally, can we make our models even more realistic and practical? How well do
our approaches perform on real-world financial networks? Can we identify
topological and other properties of financial networks that may be leveraged
in designing improved algorithms?

## References

  *   * Eisenberg and Noe [2001] Eisenberg, L., Noe, T.H.: Systemic risk in financial systems. Management Science 47(2), 236–249 (2001)
  * Rogers and Veraart [2013] Rogers, L.C., Veraart, L.A.: Failure and rescue in an interbank network. Management Science 59(4), 882–898 (2013)
  * Schuldenzucker et al. [2017] Schuldenzucker, S., Seuken, S., Battiston, S.: Finding clearing payments in financial networks with credit default swaps is PPAD-complete. In: 8th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 67 (2017)
  * Papp and Wattenhofer [2021] Papp, P.A., Wattenhofer, R.: Sequential defaulting in financial networks. In: 12th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 185 (2021)