1: Input:

a: an adverse graph \(G_{adverse}\) of order \(k\) with traveling cost of 1 on bridge edges and traveling cost of 0 on other edges

b: an arbitrary deterministic online algorithm \(ALG\) applied to \(G_{adverse}\)

2: Output:

a: an instance of the \(m\)-\(k\)-\(CTP\) on \(G_{adverse}\) with \(k\) blocked edges against \(ALG\)

3: Initiation:

a: define \(i\) and \(j\) as counter variables and set \(i=0\) and \(j=2\)

4: if there exists at least one node at level \(j\) of left tree with \(x^i_{wj}>0\) which belongs to at least one \(O-D\) path which is not found to be blocked yet:

a: determine \(w^{*} \in \{1,2,...,2^{j-1}\}\) such that \(x^{i}_{w^{*}j} = max_{w \in \{1,2,...,2^{j-1}\}}\{x^i_{wj}\}\)

▷ choose \(w^*\) randomly in case of tie

b: block the edge which emanates from \(v^{right}_{w^{*}j}\) and enters a node on the \((j-1)\)th level of the right tree

c: set \(j=j+1\)

d: if \(j>k+1,\), stop

e: else: go to 4

5. else: set \(i=i+1\) and go to 4