# Attacking Shortest Paths by Cutting Edges

Benjamin A. Miller<EMAIL_ADDRESS>0000-0002-1649-1401
Northeastern UniversityBostonMAUSA02115 ,  Zohair Shafi
<EMAIL_ADDRESS>0000-0001-6154-1466 Northeastern
UniversityBostonMAUSA02115 ,  Wheeler Ruml  University of New
HampshireDurhamNHUSA03824<EMAIL_ADDRESS>0000-0002-1308-2311 ,  Yevgeniy
Vorobeychik  Washington University in St. LouisSt. LouisMOUSA63130
<EMAIL_ADDRESS>0000-0003-2471-5345 ,  Tina Eliassi-Rad  Northeastern
UniversityBostonMAUSA02115<EMAIL_ADDRESS>0000-0002-1892-1188
and  Scott Alfeld  Amherst CollegeAmherstMAUSA01002<EMAIL_ADDRESS>0000-0001-8446-4993

###### Abstract.

Identifying shortest paths between nodes in a network is a common graph
analysis problem that is important for many applications involving routing of
resources. An adversary that can manipulate the graph structure could alter
traffic patterns to gain some benefit (e.g., make more money by directing
traffic to a toll road). This paper presents the _Force Path Cut_ problem, in
which an adversary removes edges from a graph to make a particular path the
shortest between its terminal nodes. We prove that this problem is APX-hard,
but introduce PATHATTACK, a polynomial-time approximation algorithm that
guarantees a solution within a logarithmic factor of the optimal value. In
addition, we introduce the _Force Edge Cut_ and _Force Node Cut_ problems, in
which the adversary targets a particular edge or node, respectively, rather
than an entire path. We derive a nonconvex optimization formulation for these
problems, and derive a heuristic algorithm that uses PATHATTACK as a
subroutine. We demonstrate all of these algorithms on a diverse set of real
and synthetic networks, illustrating the network types that benefit most from
the proposed algorithms.

adversarial graph analysis, APX-hardness, integer programming

††ccs: Theory of computation Shortest paths††ccs: Theory of computation
Stochastic approximation††ccs: Theory of computation Network
optimization††ccs: Security and privacy Information flow control

##  1\. Introduction

Finding shortest paths among interconnected entities is an important task in a
wide variety of applications. When routing resources—such as traffic on roads,
ships among ports, or packets among routers—identifying the shortest path
between two nodes is key to making efficient use of the network. Given that
traffic prefers to take the shortest route, a malicious adversary with the
ability to alter the graph topology could manipulate the paths to gain an
advantage, e.g., direct traffic between two popular locations across a toll
road the adversary owns. Countering such behavior is important, and
understanding vulnerability to such manipulation is a step toward more robust
graph mining.

In this paper, we present the _Force Path Cut_ problem in which an adversary
wants the shortest path between a source node and a target node in an edge-
weighted network to follow a preferred path. The adversary achieves this goal
by cutting edges, each of which has a known cost for removal. We show that
this problem is APX-hard via a reduction from the 3-Terminal Cut problem
(Dahlhaus et al., 1994). To solve Force Path Cut, we recast it as a Weighed
Set Cover problem, which allows us to use well-established approximation
algorithms to minimize the total edge removal cost. We propose the PATHATTACK
algorithm, which combines these algorithms with a constraint generation method
to efficiently identify paths to target for removal. While these algorithms
only guarantee an approximately optimal solution in general, PATHATTACK yields
the lowest-cost solution in a large majority of our experiments.

We also introduce the _Force Edge Cut_ and _Force Node Cut_ problems, where a
specific edge (or node) is targeted rather than an entire path. These problems
are also APX-hard, and we use PATHATTACK as part of a heuristic search
algorithm to solve them. The three problems are defined formally in the
following section.

###  1.1. Problem Statement

We consider a graph $G=(V,E)$, where the vertex set $V$ contains $N$ entities
and $E$ consists of $M$ edges, which may be directed or undirected. Each edge
has a weight $w:E\rightarrow\mathbb{R}_{\geq 0}$ denoting the expense of
traversal (e.g., distance or time). In addition, each edge has a removal cost
$c:E\rightarrow\mathbb{R}_{\geq 0}$. We are also given a source node $s\in V$,
a target node $t\in V$, and a budget $b>0$ for edge removal. Within this
context, there are three problems we address:

  * •

Force Edge Cut: Given an edge $e^{*}\in E$, find $E^{\prime}\subset E$ where
$\sum_{e\in E^{\prime}}{c(e)}\leq b$ and all shortest paths from $s$ to $t$ in
$G^{\prime}=(V,E\setminus E^{\prime})$ use $e^{*}$.

  * •

Force Node Cut: Given a node $v^{*}\in V$, find $E^{\prime}\subset E$ where
$\sum_{e\in E^{\prime}}{c(e)}\leq b$ and all shortest paths from $s$ to $t$ in
$G^{\prime}=(V,E\setminus E^{\prime})$ use $v^{*}$.

  * •

Force Path Cut: Given a path $p^{*}$ from $s$ to $t$ in $G$, find
$E^{\prime}\subset E$ where $\sum_{e\in E^{\prime}}{c(e)}\leq b$ and $p^{*}$
is the shortest path from $s$ to $t$ in $G^{\prime}=(V,E\setminus
E^{\prime})$.

Each variation of the problem addresses a different adversarial objective:
there is a particular edge (e.g., a toll road), a particular node (e.g., a
router in a network), or an entire path (e.g., a sequence of surveillance
points) where increased traffic would benefit the adversary. The attack vector
in all cases is removal of edges, and the adversary has access to the entire
graph.

###  1.2. Contributions

The main contributions of this paper as as follows:

  * •

We define the Force Edge Cut, Force Node Cut, and Force Path Cut problems and
prove that they are APX-hard.

  * •

We introduce the PATHATTACK algorithm, which provides a logarithmic
approximation for Force Path Cut with high probability in polynomial time.

  * •

We provide a non-convex optimization formulation for Force Edge Cut and Force
Node Cut, as well as polynomial-time heuristic algorithms.

  * •

We present the results of over 16,000 experiments on a variety of synthetic
and real networks, demonstrating where these algorithms perform best with
respect to baseline methods.

###  1.3. Paper Organization

The remainder of this paper is organized as follows. In Section 2, we briefly
summarize related work on inverse optimization and adversarial graph analysis.
In Section 3, we provide a sketch of the proof that all three problems are
APX-hard. Section 4 introduces the PATHATTACK algorithm, which guarantees a
logarithmic approximation of the optimal solution to Force Path Cut. In
Section 5, we show how PATHATTACK can be used as a heuristic to solve Force
Edge Cut and Force Node Cut. Section 6 documents the results of experiments on
diverse real and synthetic networks, demonstrating where PATHATTACK provides a
benefit over baseline methods. In Section 7, we conclude with a summary and
discussion of open problems.

##  2\. Related Work

Early work on attacking networks focused on disconnecting them (Albert et al.,
2000). This work demonstrated that targeted removal of high-degree nodes was
highly effective against networks with power law degree distributions (e.g.,
Barabási–Albert networks), but far less so against random networks. This is
due to the prevalence of hubs in networks with such degree distributions.
Other work has focused on disrupting shortest paths via edge removal, but in a
narrower context than ours. Work on the most vital edge problem (e.g.,
(Nardelli et al., 2003)) attempts to efficiently find the single edge whose
removal most increases the distance between two nodes. Our present work, in
contrast, considers a devious adversary that wishes a certain path to be
shortest.

There are several other adversarial contexts in which path-finding is highly
relevant. Some work is focused on traversing hostile territory, such as
surreptitiously planning the path of an unmanned aerial vehicle (Jun and
D’Andrea, 2003). The complement of this is network interdiction, where the
goal is to intercept an adversary who is attempting to traverse the graph
while remaining hidden. Bertsimas et al. formulate an optimization problem
similar to Force Path Cut, where the goal is overall disruption of flows
rather than targeting a specific shortest path (Bertsimas et al., 2016).
Network interdiction has been studied in a game theoretic context for many
years (Washburn and Wood, 1995), and has expanded into work on disrupting
attacks, with the graph representing an attack plan (Letchford and
Vorobeychik, 2013). In this work, as in ours, oracles can be used to avoid
enumerating an exponentially large number of possible strategies (Jain et al.,
2011).

As with many graph problems, finding a shortest path can be formulated as an
optimization problem: over all paths from $s$ to $t$, find the one that
minimizes the sum of edge weights. Finding the weights for two nodes to have a
particular shortest path is an example of inverse optimization (Ahuja and
Orlin, 2001). From this perspective, the shortest path is a function mapping
edge weights to a path, and the inverse shortest path problem is to find the
inverse function: input a path and output a set of weights. This typically
involves finding a new set of weights given a baseline that should change as
little as possible, with respect to some distance metric (though it is shown
in (Xu and Zhang, 1995) that solving the problem without baseline weights
solves the minimum cut problem). To solve inverse shortest path while
minimizing the $L_{1}$ norm between the weights, Zhang et al. propose a column
generation algorithm (Zhang et al., 1995), similar to the constraint
generation method we describe in Section 4.3. Such a constraint generation
procedure is also used in the context of navigation meshes in (Brandão et al.,
2021). The instance of inverse shortest path that is closest to Force Path Cut
uses the weighted Hamming distance between the weight vectors, where changing
the weight of an edge has a fixed cost, regardless of the size of the
change.111Edge removal can be simulated by significantly increasing weights.
Inverse shortest path using weighted Hamming distance also allows for reducing
edge weights, which is not allowed in Force Path Cut. This case was previously
shown to be NP-hard (Zhang and Wang, 2008). In this paper, we show that Force
Path Cut, which is less flexible, is also not just NP-hard, but APX-hard.

In addition to inverse shortest path, authors have considered the inverse
shortest path length problem (sometimes called reverse shortest path) (Tayyebi
and Massoud, 2016), where only the length of the shortest path is specified.
This problem has been shown to be NP-hard except when only considering a
single source and destination (Zhang and Lin, 2003; Cui and Hochbaum, 2010).
There is also the notion of inverse shortest path routing, in which edge
weights are manipulated so that edges from one specified subset are used for
shortest paths, while edges from a second, disjoint subset are never used
(Call and Holmberg, 2011). Other graph-based optimization problems, such as
maximum flow and minimum cut, have also been topics in the inverse
optimization literature (see, e.g., (Liu and Zhang, 2006; Jiang et al., 2010;
Deaconu and Ciupala, 2020)).

There has recently been a great deal of work on attacking machine learning
methods where graphs are part of the input. Finding shortest paths is another
common graph problem that attackers could exploit. Attacks against vertex
classification (Dai et al., 2018; Zügner et al., 2018; Chen et al., 2018; Wu
et al., 2019; Xu et al., 2019) and node embeddings (Bojchevski and Günnemann,
2019; Chang et al., 2020) consider attackers that can manipulate edges, node
attributes, or both in order to affect the outcome of the learning method. In
addition, attacks against community detection have been proposed where a node
can create new edges to alter its group assignment from a community detection
algorithm (Kegelmeyer et al., 2018; Chen et al., 2020; Jiang et al., 2020), or
to reduce the efficacy of community detection overall (Nagaraja, 2010; Waniek
et al., 2018; Fionda and Pirro, 2017; Li et al., 2020; Chen et al., 2019). Our
work complements these efforts, expanding the space of adversarial graph
analysis into another important graph mining task.

##  3\. Computational Complexity

We first consider the complexity of Force Path Cut. Like inverse shortest path
under Hamming distance (Zhang and Wang, 2008), this problem is NP-hard, as
shown in our prior work (Miller et al., 2021). A novel result of our present
work is that Force Path Cut is not merely NP-hard; there is no possible
polynomial time approximation scheme, i.e., no polynomial-time algorithm can
find a solution within a factor of $(1+\epsilon)$ of the optimal (minimal)
budget unless P=NP. Using a linear reduction from another APX-hard problem, we
prove the following theorem.

###### Theorem 3.1.

Force Path Cut is APX-hard, including the case where all weights and all costs
are equal.

###  3.1. Proof Sketch

The following is a sketch of the proof of Theorem 3.1, with a detailed proof
provided in Appendix A. First, consider the case for undirected graphs, where
all edges weights are equal to their removal costs. We prove this is APX-hard
via reduction from 3-Terminal Cut (Dahlhaus et al., 1994). In 3-Terminal Cut,
we are given a graph $G=(V,E)$, three terminal nodes $s_{1},s_{2},s_{3}\in V$,
and a budget $b\geq 0$. For the purpose of this proof, we only consider the
case where all edge weights are equal. The goal is to determine whether there
exists $E^{\prime}\subset E$, with $|E^{\prime}|\leq b$, where $s_{1}$,
$s_{2}$, and $s_{3}$ are disconnected in $G^{\prime}=(V,E\setminus
E^{\prime})$, i.e., after the edges is $E^{\prime}$ are removed, no path
exists between any of the terminal nodes.

We reduce 3-Terminal Cut to Force Path Cut as follows. Create $M+1$ new
disjoint paths, each $N$ hops long, from $s_{1}$ to $s_{2}$. This introduces
$(M+1)(N-1)$ new nodes and $(M+1)N$ new edges. Do the same for $s_{2}$ and
$s_{3}$ (another $(M+1)(N-1)$ nodes and $(M+1)N$ edges). Create a new
$(2N-1)$-hop path from $s_{1}$ to $s_{3}$ ($2N-2$ new nodes, $2N-2$ new
edges). Make the new path from $s_{1}$ to $s_{3}$ the target path $p^{*}$,
with $s=s_{1}$ and $t=s_{3}$. Call the resulting graph $\hat{G}$. Solve Force
Path Cut on $\hat{G}$, obtaining a set of edges $E^{\prime}$ to be removed.
This process is illustrated in Fig. 1.

If $E^{\prime}$ is a solution to Force Path Cut, it is also a solution to
3-Terminal Cut. If any of the terminal nodes could be reached from another
using edges in the original graph, $p^{*}$ would not be the shortest path. If
a path from $s_{2}$ to $s_{3}$ from the original graph remained, for example,
this path would be at most $N-1$ hops long. There would exist a path from
$s_{1}$ to $s_{3}$ using one of the new $(N+1)$-hop paths from $s_{1}$ to
$s_{2}$, followed by the remaining path from $s_{2}$ to $s_{3}$. This path
would be less than $2N+1$ hops, so $p^{*}$ would not be the shortest path.

Figure 1. Reduction from 3-Terminal Cut to Force Path Cut. The initial graph
(left) includes 3 terminal nodes $s_{1}$, $s_{2}$, and $s_{3}$, which are
connected to the rest of the graph by edge sets $E_{1}$, $E_{2}$, and $E_{3}$,
respectively. The dashed lines indicate the possibility of edges between
terminals. The input to Force Path Cut, $\hat{G}$ (center), includes the
original graph plus many long parallel paths between terminals. A single path
from $s_{1}$ to $s_{2}$ comprising $p^{*}$ is indicated in red. The result of
solving Force Path Cut and removing the returned edges (right) is that any
existing paths between the terminals have been removed, thus disconnecting
them in the original graph and solving 3-Terminal Cut.

In the optimization version of the problem, the goal is to find the
$E^{\prime}$ that solves 3-Terminal Cut with the smallest budget. Let
$E^{\prime}_{\mathrm{OPT}}$ be this edge set. Since this set disconnects the
terminals, it also solves Force Path Cut. In the full proof, we show that
there is no way to solve Force Path Cut on $\hat{G}$ with fewer edges. Thus,
the optimal solution for Force Path Cut is the same as the optimal solution to
3-Terminal Cut. In addition, if we consider _any_ solution $\hat{E}^{\prime}$
to Force Path Cut on $\hat{G}$, we show that there is a solution to 3-Terminal
Cut that is no larger than $\hat{E}^{\prime}$. As we discuss in the appendix,
this means that the reduction is linear, and thus preserves approximation.
Since 3-Terminal Cut is APX-hard, a linear reduction implies that Force Path
Cut is also APX-hard.

To prove that Force Path Cut is APX-hard for directed graphs as well, we
reduce Force Path Cut for undirected graphs to the same problem for directed
graphs. Given an undirected graph $G=(V,E)$ and the path $p^{*}$ from source
node $s$ to destination node $t$, create a new graph $\hat{G}=(V,\hat{E})$ on
the same vertex set, with two directed edges for each undirected edge from
$G$, i.e., $\hat{E}$ contains the directed edge $(u,v)$ if and only if $E$
contains either $\\{u,v\\}$. We again consider the case where all weights and
all costs are equal. Solve Force Path Cut on $\hat{G}$, obtaining the optimal
solution $\hat{E}^{\prime}$. For each directed edge in
$(u,v)\in\hat{E}^{\prime}$, remove the undirected edge $\\{u,v\\}$ from $G$.
In the resulting graph, $p^{*}$ will be the shortest path from $s$ to $t$. As
we show in Appendix A.2, if the optimal solution includes $(u,v)$, it cannot
also include $(v,u)$, i.e., if $(u,v)\in\hat{E}^{\prime}$, then
$(v,u)\notin\hat{E}^{\prime}$. This implies that the optimal solution size for
Force Path Cut in directed graphs is equal to the optimal solution size for
Force Path Cut in undirected graphs. By the same argument that we used for
undirected graphs, Force Path Cut is therefore APX-hard for directed graphs.

###  3.2. Extension to Force Edge Cut and Force Node Cut

The same reduction used to prove that Force Path Cut is APX-hard can show the
same for Force Edge Cut. The difference is that, rather than letting $p^{*}$
be the new path from $s_{1}$ to $s_{3}$, we let $e^{*}$ be one of the edges
along this new path. This will still force the new path from $s_{1}$ to
$s_{3}$ to be the shortest, so the optimal will be exactly the same. Like
Force Path Cut, the directed and undirected cases have the same solution,
resulting in the following corollary.

###### Corollary 3.2.

Force Edge Cut is APX-hard, including the case where all weights and all costs
are equal.

By selecting a node along the new path from $s_{1}$ to $s_{3}$ to act as
$v^{*}$, we can make the same argument for Force Node Cut.

###### Corollary 3.3.

Force Node Cut is APX-hard, including the case when all weights and all costs
are equal.

##  4\. PATHATTACK

While Force Path Cut is APX-hard, the optimal solution can be approximated
within a logarithmic factor in polynomial time. This section describes an
algorithm to achieve this.

###  4.1. Cutting Paths Via Set Cover

We first note that Force Path Cut can be recast as an instance of Weighted Set
Cover. In weighted set cover, there is a discrete universe $U$ of elements and
a set $\mathcal{S}$ of subsets of $U$, where each subset $S\in\mathcal{S}$ has
an associated cost $c(S)\geq 0$. The objective is to find the subset of
$\mathcal{S}$ with the lowest total cost where the union of the elements
comprises $U$, i.e., to find

(1) $\displaystyle\hat{\mathcal{S}}=$
$\displaystyle\operatorname*{arg\,min}_{\mathcal{S}^{\prime}\subseteq\mathcal{S}}{\sum_{S\in\mathcal{S}^{\prime}}c(S)}$
(2) s.t. $\displaystyle~{}\bigcup_{S\in\mathcal{S}^{\prime}}{S}=U.$

When we solve Force Path Cut, the goal is to cut all paths from $s$ to $t$
that are not longer than $p^{*}$, and to do so by selecting edges for removal.
This is a set cover problem. The universe $U$ is the set of all paths
competing to be shortest. This set must be “covered” by removing all such
paths from the graph. If any of these paths remains, $p^{*}$ will not be the
shortest path. The subsets in $\mathcal{S}$ are edges: Each edge is the set of
paths that use that edge. Cutting the edge is selecting that set for inclusion
in the union, i.e., removing all paths that include the edge. Figure 2
illustrates the connection between the two problems.

Figure 2. The Force Path Cut problem is an example of the Weighted Set Cover
problem. In the bipartite graph on the right, the square nodes represent paths
and the circle nodes represent edges. Note that edges along $p^{*}$ are not
included. When the red-colored circle (i.e., edge $(v_{7},t)$) is removed,
then the red-colored squares (i.e., paths $p_{1}$, $p_{2}$, $p_{3}$, and
$p_{4}$) are removed.

Weighted Set Cover is not only APX-hard, but cannot be approximated within
less than a logarithmic factor (Raz and Safra, 1997). There are, however, well
known approximation algorithms that enable us to efficiently reach this
asymptotic lower bound. The challenge for Force Path Cut is that the universe
of competing paths may be extremely large. We address this challenge in the
remainder of this section.

###  4.2. Approximation Algorithms for Fixed Path Sets

We consider two approximation algorithms for Weighted Set Cover, both of which
achieve a logarithmic factor approximation for the optimal solution (Vazirani,
2003a). The first is a greedy method, which iteratively selects the most cost
effective set and includes it in the solution, i.e., it selects the set where
the number of uncovered elements divided by the cost is the lowest. We
likewise iteratively remove the edge that cuts the most uncut paths in $P$ for
the lowest cost. We refer to this procedure as GreedyPathCover, and we provide
its pseudocode in Algorithm 1. We have a fixed set of paths $P\subset
P_{p^{*}}$. Note that this algorithm only uses costs, not weights: the paths
of interest have already been determined and we only need to determine the
cost of breaking them. GreedyPathCover performs a constant amount of work at
each edge in each path in the initialization loop and the edge and path
removal. We use lazy initialization to avoid initializing entries in the
tables associated with edges that do not appear in any paths. Thus, populating
the tables and removing paths takes time that is linear in the sum of the
number of edges over all paths, which in the worst case is $O(|P|N)$. Finding
the most cost-effective edge takes $O(M)$ time with a naïve implementation,
and this portion is run at most once per path, leading to an overall running
time of $O(|P|(N+M))$. Using a more sophisticated data structure, like a
Fibonacci heap, to hold the number of paths for each edge would enable finding
the most cost effective edge in constant time, but updating the counts when
edges are removed would take $O(\log{M})$ time, for an overall running time of
$O(|P|N\log{M})$. The worst-case approximation factor is the harmonic function
of the size of the universe (Vazirani, 2003a), i.e.,
$H_{|\mathcal{U}|}=\sum_{n=1}^{|\mathcal{U}|}{1/n}$, which implies that the
GreedyPathCover algorithm has a worst-case approximation factor of $H_{|P|}$.

Input: Graph $G=(V,E)$, costs $c$, target path $p^{*}$, path set $P$, edges
$E_{\mathrm{keep}}$

Output: Set $E^{\prime}$ of edges to cut

$T_{P}\leftarrow$ empty hash table; // set of paths for each edge

$T_{E}\leftarrow$ empty hash table; // set of edges for each path

$N_{P}\leftarrow$ empty hash table; // path count for each edge

foreach  _$e\in E$_ do

$T_{P}[e]\leftarrow\emptyset$;

$N_{P}[e]\leftarrow 0$;

end foreach

foreach  _$p\in P$_ do

$T_{E}[p]\leftarrow\emptyset$;

foreach  _$e\in E_{p}\setminus E_{\mathrm{keep}}$_ do

$T_{P}[e]\leftarrow T_{P}[e]\cup\\{p\\}$;

$T_{E}[p]\leftarrow T_{E}[p]\cup\\{e\\}$;

$N_{P}[e]\leftarrow N_{P}[e]+1$;

end foreach

end foreach

$E^{\prime}\leftarrow\emptyset$;

while  _$\max_{e\in E}{N_{P}[e]} >0$_ do

$e^{\prime}\leftarrow\arg\max_{e\in E}{N_{P}[e]/c(e)}$; // find most cost-
effective edge

$E^{\prime}\leftarrow E^{\prime}\cup\\{e^{\prime}\\}$;

foreach  _$p\in T_{P}[e^{\prime}]$_ do

foreach  _$e_{1}\in T_{E}[p]$_ do

$N_{P}[e_{1}]\leftarrow N_{P}[e_{1}]-1$; // decrement path count

$T_{P}[e_{1}]\leftarrow T_{P}[e_{1}]\setminus\\{p\\}$; // remove path

end foreach

$T_{E}[p]\leftarrow\emptyset$; // clear edges

end foreach

end while

return $E^{\prime}$

Algorithm 1 GreedyPathCover

For the second approximation algorithm, we introduce the integer program
formulation of Force Path Cut, modeled after the formulation for Weighted Set
Cover. The objective is to minimize the cost of the edges that are cut. Let
$\mathbf{c}\in\mathbb{R}_{\geq 0}^{M}$ be a vector of edge removal costs,
where each entry corresponds to an edge. The binary vector
$\Delta\in\\{0,1\\}^{M}$ indicates the edges to be removed. In the integer
program formulation of Weighted Set Cover, each dimension corresponds to a
set, and each constraint corresponds to an element. Each element forms a
linear constraint, forcing at least one of the sets containing that element to
be selected. To solve Force Path Cut, let $P_{p^{*}}$ be the set of paths that
must be cut. For each path $p\in P_{p^{*}}$, let
$\mathbf{x}_{p}\in\\{0,1\\}^{M}$ be the indicator vector for $E_{p}$, the set
of edges along $p$. We solve Force Path Cut via the integer program

(3) $\displaystyle\hat{\Delta}=$
$\displaystyle\operatorname*{arg\,min}_{\Delta}\mathbf{c}^{\top}\Delta$ (4)
s.t. $\displaystyle~{}\Delta\in\\{0,1\\}^{M}$ (5)
$\displaystyle~{}\mathbf{x}_{p}^{\top}\Delta\geq 1~{}~{}\forall p\in
P_{p^{*}}$ (6) $\displaystyle~{}\mathbf{x}_{\textrm{keep}}^{\top}\Delta=0.$

The constraint (6) prevents any edges in the set $E_{\mathrm{keep}}$ from
being cut.222This could also be achieved by removing these variables from the
optimization. With target paths, we set $E_{\mathrm{keep}}=E_{p^{*}}$, but we
allow greater flexibility for the methods outlined in Section 5, which target
nodes or edges.

The second algorithm is a randomized algorithm that uses this formulation. As
with the greedy approach, we focus on a subset of paths $P\subset P_{p^{*}}$.
This algorithm relaxes the integer program (3)–(6) by replacing the binary
constraint $\Delta\in\\{0,1\\}^{M}$ with a continuous constraint
$\Delta\in[0,1]^{M}$. When we find the optimal solution $\hat{\Delta}$ to the
relaxed problem, we perform the following randomized rounding procedure for
each edge $e$:

  1. (1)

Treat the corresponding entry $\hat{\Delta}_{e}$ as a probability.

  2. (2)

Draw $\lceil\ln{(4|P|)}\rceil$ i.i.d. Bernoulli random variables with
probability $\hat{\Delta}_{e}$.

  3. (3)

Cut $e$ only if at least one random variable from step 2 is 1.

The resulting graph must satisfy two criteria. First, the constraints must all
be satisfied, i.e., all paths in $P$ must be cut. In addition, the cost of
cutting the edges must not exceed $\ln{(4|P|)}$ times the fractional optimum,
i.e., the optimal objective of the relaxed linear program (LP). If one of
these criteria is not satisfied, the randomized rounding procedure is run
again. Each criterion has less than $1/4$ probability of not being satisfied
(Vazirani, 2003b). Thus, the expected number of randomized rounding trials to
achieve a satisfactory solution is less than 2. We present pseudocode for this
procedure, which we call RandPathCover, in Algorithm 2.

Input: Graph $G=(V,E)$, costs $\mathbf{c}$, path $p^{*}$, path set $P$, edges
$E_{\mathrm{keep}}$

Output: Set $E^{\prime}$ of edges to cut

$\hat{\Delta}\leftarrow$ relaxed cut solution to (3)–(6) with paths $P$;

$\Delta\leftarrow\mathbf{0}$;

$E^{\prime}\leftarrow\emptyset$;

not_cut$\leftarrow\mathbf{True}$;

while  _$\mathbf{c}^{\top}\Delta >\mathbf{c}^{\top}\hat{\Delta}(4\ln{(4|P|)})$
$\mathbf{or}$ $\mathrm{not\\_cut}$_ do

$E^{\prime}\leftarrow\emptyset$;

for  _$i\leftarrow 1$ to $\lceil\ln{(4|P|)}\rceil$_ do

// randomly select edges based on $\hat{\Delta}$

$E_{1}\leftarrow\\{e\in E\textrm{ with probability }\hat{\Delta}_{e}\\}$;

$E^{\prime}\leftarrow E^{\prime}\cup E_{1}$;

end for

$\Delta\leftarrow$ indicator vector for $E^{\prime}$;

not_cut$\leftarrow(\exists p\in P$ where $E_{p}\cap E^{\prime}\neq\emptyset$);

end while

return $E^{\prime}$

Algorithm 2 RandPathCover

###  4.3. Constraint Generation

Algorithms 1 and 2 work with a fixed set of paths $P$, but to solve Force Path
Cut, enumeration of the full set of relevant paths may be intractable.
Consider, for example, the case where $G$ is a clique (i.e., a complete graph)
and all edges have weight 1 except the edge joining $s$ and $t$, which has
weight $N$. Among all simple paths from $s$ to $t$, the longest path is the
direct path $(s,t)$ that only uses one edge; all other simple paths are
shorter, including $(N-2)!$ paths of length $N-1$. Setting $p^{*}=(s,t)$ makes
the full set of constraints (i.e., one for each path that need to be cut)
extremely large. However, if $P$ were to include only those paths of length
$2$ and $3$, we would obtain the optimal solution with only $(N-2)^{2}+(N-2)$
constraints. In general, we can solve linear programming problems—even those
with infinitely many constraints—as long as we have a polynomial-time method
to identify a constraint that a candidate solution violates.

In our case, the oracle that provides a violated constraint, if one exists, is
the shortest path algorithm. After applying a candidate solution, we see if
$p^{*}$ is the shortest path from $s$ to $t$ in the resulting graph. If so,
the procedure terminates. If not, the shortest path is added as a new
constraint. This procedure works in an iterative process with the
approximation algorithms to expand $P$ as new constraints are discovered. We
refer to the resulting algorithm as PATHATTACK, and provide pseudocode in
Algorithm 3. Depending on whether we use GreedyPathCover or RandPathCover, we
refer to the algorithm as PATHATTACK-Greedy or PATHATTACK-Rand, respectively.

Input: Graph $G=(V,E)$, costs $c$, weights $w$, target path $p^{*}$, edges
$E_{\textrm{keep}}$, cover alg. Cvr

Output: Set $E^{\prime}$ of edges to cut

$E^{\prime}\leftarrow\emptyset$;

$P\leftarrow\emptyset$;

$\mathbf{c}\leftarrow$ vector from costs $c(e)$ for $e\in E$;

$G^{\prime}\leftarrow(V,E\setminus E^{\prime})$;

$s,t\leftarrow$ source and destination nodes of $p^{*}$;

$p\leftarrow$ shortest path from $s$ to $t$ in $G^{\prime}$ (not including
$p^{*}$);

while  _$p$ is not longer than $p^{*}$_ do

$P\leftarrow P\cup\\{p\\}$;

$E^{\prime}\leftarrow$Cvr$(G,\mathbf{c},p^{*},P)$;

$G^{\prime}\leftarrow(V,E\setminus E^{\prime})$;

$p\leftarrow$ shortest path from $s$ to $t$ in $G^{\prime}$ (not including
$p^{*}$) using weights $w$;

end while

return $E^{\prime}$

Algorithm 3 PATHATTACK

###  4.4. PATHATTACK Convergence and Approximation Guarantees

While the approximation factor for Set Cover is a function of the size of the
universe (all paths that need to be cut), this is not the fundamental factor
in the approximation in our case. The approximation factor for PATHATTACK-
Greedy is based only on the paths we consider explicitly. Using only a subset
of constraints, the worst-case approximation factor is determined by the size
of that subset. By the final iteration of PATHATTACK, however, we have a
solution to Force Path Cut that is within $H_{|P|}$ of the optimum of the less
constrained problem, using $|P|$ from the final iteration. This yields the
following proposition:

###### Proposition 4.1.

The approximation factor of PATHATTACK-Greedy is at most $H_{|P|}$ times the
optimal solution to Force Path Cut.

A similar argument holds for PATHATTACK-Rand, applying the results of
(Vazirani, 2003a):

###### Proposition 4.2.

PATHATTACK-Rand yields a worst-case $O(\log|P|)$ approximation to Force Path
Cut with high probability.

There is also a variation of PATHATTACK-Rand can guarantee polynomial time
convergence. While the number of implicit constraints may be extremely large,
each one is a standard linear inequality constraint, which implies that the
feasible region is convex. Given a polynomial-time oracle that returns a
constraint violated by a proposed solution $\hat{\Delta}\in[0,1]^{M}$ to the
relaxed LP, we could use Khachiyan’s ellipsoid algorithm (see (Gács and
Lovász, 1981)), which can solve a linear program with an arbitrary (or
infinite) number of linear constraints in a polynomial number of iterations
(Grötschel et al., 1981). We use the randomized rounding procedure from
Algorithm 2 to achieve such an oracle. In Appendix B, we prove that this
oracle terminates in polynomial time with high probability. This results in
the following theorem.

###### Theorem 4.3.

PATHATTACK using the ellipsoid algorithm converges in polynomial time with
high probability.

While this guarantees polynomial time convergence, we do not use the ellipsoid
algorithm in our experiments in Section 6, as other methods converge much
faster in practice.

###  4.5. PATHATTACK for Node Removal

This paper is focused on the case where edges are removed from a graph, but
there are applications in which removing nodes is more appropriate. In a
computer network, for example, it may be more likely for a node to be taken
offline (e.g., via a denial of service attack) rather than to have particular
connections disallowed. Force Path Cut via node removal is a more complicated
problem; for a given $p^{*}$, there is not always a solution. Consider, for
example, a triangle of nodes $u$, $v$, and $w$, where all weights are equal,
and $p^{*}=(u,v,w)$: none of the three nodes can be removed because it would
destroy $p^{*}$, so $p^{*}$ cannot be made the shortest path due to the
existence of the edge connecting $u$ to $w$.

In cases where it is possible, however, we can still use PATHATTACK. The
mapping to Weighted Set Cover is analogous: a path is an element and a node
are sets that include all paths. Given a graph and $p^{*}$, we can check if it
is possible to make $p^{*}$ the shortest path from $s$ to $t$ via node
removal: if $p^{*}$ is the shortest path from $s$ to $t$ in the induced
subgraph of the nodes on $p^{*}$, then there is a solution. If not, there is
none; the method to check has demonstrated that, even if all other nodes are
removed, $p^{*}$ is not the shortest path. If there is a possible solution, we
can run PATHATTACK for node removal and achieve the same convergence and
approximation guarantees as we have for edge removal. As this is ancillary to
the main focus of the paper, we relegate further discussion of node removal to
Appendix C.

##  5\. Heuristics for Force Edge Cut and Force Node Cut

Solving Force Edge Cut or Force Node Cut requires an additional layer of
optimization. Since these problems do not consider a fixed path, there is the
possibility that a candidate solution could be improved by cutting the current
shortest path through the target.

Take, for example, the graph in Figure 3. The shortest path from $s$ to $t$
via $e^{*}$ is 4 hops and uses the sole low-cost edge. If we solve Force Path
Cut with this path as $p^{*}$, all of the $k$ paths along the top of the
figure have to be cut. If we remove the low-cost edge, all these paths would
be cut and the shortest path from $s$ to $t$ will go through $e^{*}$. Since
that edge is being preserved as part of $p^{*}$, however, each of the $k$
parallel 2-hop paths has to be cut individually and incur a cost of
$c_{\textrm{max}}$. For large $k$, we see that this cost is within a constant
factor of removing all edges in the graph, when a low-cost solution was
available. The existence of this scenario proves the following theorem.

###### Theorem 5.1.

Solving Force Path Cut targeting the shortest path through $e^{*}$ (or
$v^{*}$) may yield a cost $\Omega(Mc_{\textrm{max}}/c_{\textrm{min}})$ times
greater than solving Force Edge Cut (or Force Node Cut), where
$c_{\textrm{max}}$ and $c_{\textrm{min}}$ are, respectively, the maximum and
minimum edge removal costs.

Figure 3. A scenario where preserving the initial shortest path through
$e^{*}$ results in a bad solution. Here, all edges have the same weight and
the labels are removal costs. The shortest path through $e^{*}$ also uses the
edge with cost $c_{\min}$. However, if we solve Force Path Cut with this path
as $p^{*}$, the $k$ parallel paths on the top of the figure need to be cut,
resulting in a cost of $kc_{\max}$. If, on the other hand, the edge with cost
$c_{\min}$ were removed, then the shortest path from $s$ to $t$ would go
through $e^{*}$, at a factor of $k\frac{c_{\max}}{c_{\min}}$ lower cost. If
$k$ is $\Omega(M)$, then solution is within a constant factor of removing all
edges, when a solution with the lowest possible cost was available.

To both minimize cost and allow the flexibility to alter the target path, we
formulate a nonconvex optimization problem. We start with a formulation of a
linear program to obtain the shortest path through $e^{*}$ (or $v^{*}$).
Recall the linear program formulation of the shortest path problem (see, e.g.,
(Aneja and Nair, 1978)). Using a graph’s incidence matrix, finding the
shortest path can be formulated as a linear program. In the incidence matrix,
denoted by $\mathbf{C}$, each row corresponds to a node and each column
corresponds to an edge. The column representing the edge from node $u$ to node
$v$ contains $-1$ in the row for $u$, $1$ in the row for $v$, and zeros
elsewhere. If the graph is undirected, the edge orientation is arbitrary. To
identify the shortest path from $s$ to $t$, define the vector
$\mathbf{d}\in\\{-1,0,1\\}^{N}$, which is $-1$ in the row corresponding to
$s$, $1$ in the row for $t$, and zeros elsewhere. The shortest path is the
solution to the integer linear program

(7) $\displaystyle\hat{\mathbf{x}}=$
$\displaystyle\operatorname*{arg\,min}_{\mathbf{x}}\mathbf{x}^{\top}\mathbf{w}$
(8) s.t. $\displaystyle~{}\mathbf{x}\in\\{0,1\\}^{M}$ (9)
$\displaystyle~{}\mathbf{C}\mathbf{x}=\mathbf{d}.$

The resulting vector $\hat{\mathbf{x}}$ is an indicator for the edges in the
shortest path.333In the undirected case, to denote traversal of an edge in the
opposite direction of its arbitrary orientation, we consider
$\mathbf{x}_{\textrm{pos}}$ and $\mathbf{x}_{\textrm{neg}}$, with constraint
(9) replaced with
$\mathbf{C}(\mathbf{x}_{\textrm{pos}}-\mathbf{x}_{\textrm{neg}})=\mathbf{d}$
and the objective replaced with
$(\mathbf{x}_{\textrm{pos}}+\mathbf{x}_{\textrm{neg}})^{\top}\mathbf{w}$. To
restrict traversing an edge in both directions, we add the constraint
$\mathbf{x}_{\textrm{pos}}+\mathbf{x}_{\textrm{neg}}\leq\mathbf{1}$ Constraint
(9) ensures that $\hat{\mathbf{x}}$ is a path, and the objective guarantees
the result has minimum weight. Due to the structure of the incidence matrix,
we can relax the constraint (8) into the continuous interval
$\mathbf{x}\in[0,1]^{M}$. If the shortest path from $s$ to $t$ is unique,
$\hat{\mathbf{x}}$ will be an indicator vector for the shortest path despite
this relaxation. If there are multiple shortest paths, $\hat{\mathbf{x}}$ will
be a convex combination of the vectors for these paths.

To obtain the shortest path through $e^{*}$, we perform a similar optimization
over two paths: the path from $s$ to $e^{*}$ and the path from $e^{*}$ to
$t$.444For brevity, we focus on the solution to Force Edge Cut. The solution
to Force Node Cut is similar. Let $e^{*}=(u,v)$ be the target edge. (In the
undirected setting, we consider both $(u,v)$ and $(v,u)$ independently and
choose the lower-cost solution.) Since we consider two paths, we have two
vectors $\mathbf{d}_{1}$ and $\mathbf{d}_{2}$, analogous to $\mathbf{d}$ in
(9). Assuming that $s\neq u$ and $t\neq v$, $\mathbf{d}_{1}$ is $-1$ in the
row of $s$ and $1$ in the row of $u$, with zeros elsewhere, and
$\mathbf{d}_{2}$ similarly has $-1$ in the row for $v$ and $1$ in the row for
$t$. (If $s=u$, $\mathbf{d}_{1}$ is all zeros, as is $\mathbf{d}_{2}$ if
$t=v$.) Since we are optimizing two paths, we use two path vectors,
$\mathbf{x}_{1}\in[0,1]^{M}$ and $\mathbf{x}_{2}\in[0,1]^{M}$.

It is not, however, sufficient to obtain a path from $s$ to $u$ and one from
$v$ to $t$: The concatenation must also be a simple (acyclic) path. To ensure
the resulting path has no cycles, we add a constraint to ensure any node is
visited at most once. Since the path vectors are optimized over edges, we
ensure any node occurs at most twice in the set of edges, aside from the
terminal nodes, which occur at most once. To obtain this constraint, we use
the matrix $\mathbf{C}_{\textrm{abs}}$, which contains the absolute values of
the incidence matrix, i.e., the $i$th row and $j$th column of
$\mathbf{C}_{\textrm{abs}}$ contains $|\mathbf{C}_{ij}|$. We also define
$\mathbf{d}_{\textrm{abs}}\in\\{1,2\\}^{N}$ to be $1$ in the rows associated
with $s$, $t$, $u$, and $v$, and $2$ elsewhere. This yields the linear program

(10) $\displaystyle\hat{\mathbf{x}}_{1},\hat{\mathbf{x}}_{2}=$
$\displaystyle\operatorname*{arg\,min}_{\mathbf{x}_{1},\mathbf{x}_{2}}(\mathbf{x}_{1}+\mathbf{x}_{2})^{\top}\mathbf{w}$
(11) s.t. $\displaystyle~{}\mathbf{x}_{1},\mathbf{x}_{2}\in[0,1]^{M}$ (12)
$\displaystyle~{}\mathbf{C}\mathbf{x}_{1}=\mathbf{d}_{1}$ (13)
$\displaystyle~{}\mathbf{C}\mathbf{x}_{2}=\mathbf{d}_{2}$ (14)
$\displaystyle~{}\mathbf{C}_{\textrm{abs}}(\mathbf{x}_{1}+\mathbf{x}_{2})\leq\mathbf{d}_{\textrm{abs}}.$

To solve Force Edge Cut, we use the same constraint generation technique as in
PATHATTACK, plus a nonlinear constraint to ensure the returned path does not
contain any removed edges. As in PATHATTACK, we use a vector $\Delta\in[0,1]$.
In addition to constraining $\Delta$ to not cut $e^{*}$, we add the nonconvex
bilinear constraint that $\Delta$ is $0$ anywhere $\mathbf{x}_{1}$ or
$\mathbf{x}_{2}$ is nonzero. Finally, we again consider a subset of paths $P$
we want to ensure are cut. The resulting nonconvex program

(15) $\displaystyle\hat{\mathbf{x}}_{1},\hat{\mathbf{x}}_{2},\hat{\Delta}=$
$\displaystyle\operatorname*{arg\,min}_{\mathbf{x}_{1},\mathbf{x}_{2},\Delta}(\mathbf{x}_{1}+\mathbf{x}_{2})^{\top}\mathbf{w}$
(16) s.t. $\displaystyle~{}\mathbf{x}_{1},\mathbf{x}_{2},\Delta\in[0,1]^{M}$
(17)
$\displaystyle~{}\mathbf{C}\mathbf{x}_{i}=\mathbf{d}_{i},~{}i\in\\{1,2\\}$
(18)
$\displaystyle~{}\mathbf{C}_{\textrm{abs}}(\mathbf{x}_{1}+\mathbf{x}_{2})\leq\mathbf{d}_{\textrm{abs}}$
(19) $\displaystyle~{}\mathbf{x}_{i}^{\top}\Delta=0,~{}i\in\\{1,2\\}$ (20)
$\displaystyle~{}\Delta_{e^{*}}=0$ (21)
$\displaystyle~{}\Delta^{\top}\mathbf{c}\leq b$ (22)
$\displaystyle~{}\Delta^{\top}\mathbf{x}_{p}\geq 1~{}\forall p\in P$

provides a partial solution.

The constraint generation mechanism differs slightly from the Force Path Cut
case. When solving Force Path Cut, there is a specific target path whose
length does not change. For Force Edge Cut, when a new path is added to the
constraint set $P$, it may change the shortest uncut path through $e^{*}$, and
thus change the length threshold for inclusion. Thus, we want $P$ to include
all paths that not longer than the shortest path in the solution, which is not
available until the problem has been solved. As in PATHATTACK, each time we
solve the optimization problem, we find the shortest path after removing the
edges indicated by $\hat{\Delta}$ as well as $e^{*}$. If this path is not
longer than the shortest uncut path through $e^{*}$—the path indicated by
$\hat{\mathbf{x}}_{1}$, $\hat{\mathbf{x}}_{2}$, and $e^{*}$—then this
alternative path must also be cut, and we add a constraint to achieve this.
Algorithm 4 provides psuedocode for this modified constraint generation
procedure.

Input: Graph $G=(V,E)$, weights $w$, costs $c$, source $s$, destination $t$,
target edge $e^{*}$, budget $b$

Output: Set $E^{\prime}$ of edges to cut

$\mathbf{C}\leftarrow$ unweighted incidence matrix of $G$;

$\mathbf{w}\leftarrow$ weight vector from $w$; $\mathbf{c}\leftarrow$ cost
vector from $c$;

$\mathbf{d}_{1}\leftarrow$ $s$ to $e^{*}$ vector; $\mathbf{d}_{2}\leftarrow$
$e^{*}$ to $t$ vector;

$\mathbf{C}_{\textrm{abs}}\leftarrow|\mathbf{C}|$;
$\mathbf{d}_{\textrm{abs}}\leftarrow$ “no cycle” vector;

$P\leftarrow\emptyset$;

$\mathrm{done}\leftarrow\mathbf{False}$;

while  _$\mathbf{not}$ $\mathrm{done}$_ do

$\hat{\mathbf{x}}_{1},\hat{\mathbf{x}}_{2},\hat{\Delta}\leftarrow$ solution to
(15);

$\hat{\Delta}\leftarrow$ extract single path indicator from $\hat{\Delta}$ if
not binary;

$p_{1}\leftarrow$ path from $\hat{\mathbf{x}}_{1}$, $e^{*}$, and
$\hat{\mathbf{x}}_{2}$;

$E^{\prime}\leftarrow$ edges with nonzeros in $\hat{\Delta}$;

$G^{\prime}\leftarrow(V,E\setminus(E^{\prime}\cup\\{e^{*}\\}))$;

$p_{2}\leftarrow$ shortest path from $s$ to $t$ in $G^{\prime}$ (using weights
$w$);

if  _$p_{2}$ is not longer than $p_{1}$_ then

$P\leftarrow P\cup\\{p_{2}\\}$;

else

$\mathrm{done}\leftarrow\mathbf{True}$;

end if

end while

return $E^{\prime}$;

Algorithm 4 Constraint generation procedure for Force Edge Cut.

To minimize the cost of the attack, we perform a binary search with respect to
the budget $b$. We obtain upper and lower bounds for the budget by running
PATHATTACK targeting the shortest path through $e^{*}$. We run the standard
PATHATTACK to get the upper bound, and remove the constraint that the target
path is uncut for the lower bound, instead only constraining that $e^{*}$ is
not cut. If, during the search, a new upper bound is discovered (i.e., a path
through $e^{*}$ is discovered that requires a budget smaller than the one
under consideration), we create new upper and lower bounds based on the new
satisfactory path. Algorithm 5 outlines this procedure.

Input: Graph $G=(V,E)$, weights $w$, costs $c$, source $s$, destination $t$,
target edge $e^{*}$, tol. $\epsilon$

Output: Set $E^{\prime}$ of edges to cut

$p\leftarrow$ shortest path from $s$ to $t$ via $e^{*}$;

$E_{p}\leftarrow$ edges in $p$;

$E_{\mathrm{upper}}\leftarrow$PATHATTACK$(G,c,w,p,E_{p},\texttt{RandPathCover})$;

$b_{\mathrm{upper}}\leftarrow\sum_{e\in E_{\mathrm{upper}}}{c(e)}$;

$E_{\mathrm{lower}}\leftarrow$PATHATTACK$(G,c,w,p,\\{e^{*}\\},\texttt{RandPathCover})$;

$b_{\mathrm{lower}}\leftarrow\sum_{e\in E_{\mathrm{lower}}}{c(e)}$;

while  _$b_{\mathrm{upper}}-b_{\mathrm{lower}} >\epsilon$_ do

$b_{\mathrm{mid}}\leftarrow(b_{\mathrm{upper}}+b_{\mathrm{lower}})/2$;

$E_{\mathrm{mid}}\leftarrow$Algorithm 4$(G,w,c,s,t,b_{\mathrm{mid}})$;

if  _Algorithm 4 could not be solved_ then

$b_{\mathrm{lower}}\leftarrow b_{\mathrm{mid}}$; // budget is too small

remove constraints accrued since last iteration

else

// budget is sufficient

$G^{\prime}\leftarrow(V,E\setminus E_{\mathrm{mid}})$;

$p\leftarrow$ shortest path from $s$ to $t$ in $G^{\prime}$; // this path will
include $e^{*}$

$E_{\mathrm{temp}}\leftarrow$PATHATTACK$(G,c,w,p,E_{p},\texttt{RandPathCover})$;

$b_{\mathrm{temp}}\leftarrow\sum_{e\in E_{\mathrm{temp}}}{c(e)}$;

if  _$b_{\mathrm{temp}} <b_{\mathrm{mid}}$_ then

$b_{\mathrm{upper}}\leftarrow b_{\mathrm{temp}}$;

$E_{\mathrm{upper}}\leftarrow E_{\mathrm{temp}}$;

else

$b_{\mathrm{upper}}\leftarrow b_{\mathrm{mid}}$;

$E_{\mathrm{upper}}\leftarrow E_{\mathrm{mid}}$;

end if

$E_{\mathrm{temp}}\leftarrow$PATHATTACK$(G,c,w,p,\\{e^{*}\\},\texttt{RandPathCover})$;

$b_{\mathrm{temp}}\leftarrow\sum_{e\in E_{\mathrm{temp}}}{c(e)}$;

if  _$b_{\mathrm{temp}} >b_{\mathrm{lower}}$_ then

$b_{\mathrm{lower}}\leftarrow b_{\mathrm{temp}}$;

$E_{\mathrm{lower}}\leftarrow E_{\mathrm{temp}}$;

end if

end if

end while

return $E_{\mathrm{upper}}$; // return the best valid solution found

Algorithm 5 Combinatorial Search

While Algorithm 5 will converge to within $\epsilon$ of an optimal solution in
a logarithmic number of iterations, each iteration uses Algorithm 4, which
involves solving a nonconvex optimization problem. It could, therefore,
require exponential time to complete any given iteration, if finding an
optimal solution is required. Thus, in addition to the combinatorial
optimization method, we consider a heuristic algorithm that seeks to identify
the bottlenecks that prevent an optimal solution, as illustrated in Figure 3,
and that is guaranteed to run in polynomial time.

As in the combinatorial optimization, we leverage PATHATTACK with and without
constraints to avoid cutting the target path. In this case, after running
PATHATTACK while only preventing $e^{*}$ from being cut, we consider the edges
on the target path that are cut by PATHATTACK. For each of these edges, we
consider the possibility of either (1) removing the edge from the graph
entirely, or (2) marking it to never be removed. If removal of any of these
edges causes $t$ to become unreachable from $s$, we add that edge to a list of
uncuttable edges. Otherwise, we consider the case in which each of these edges
is removed, each time finding the shortest path through $e^{*}$. We run
PATHATTACK in each case, and find the edge whose removal results in the lowest
upper bound on the removal budget. This edge is added to a list of edges that
will always be removed. This procedure terminates when the upper and lower
bounds converge. A pseudocode description of this heuristic search is provided
in Algorithm 6.

Input: Graph $G=(V,E)$, weights $w$, costs $c$, source $s$, destination $t$,
target edge $e^{*}$, tol. $\epsilon$

Output: Set $E^{\prime}$ of edges to cut

$E_{\mathrm{always}}\leftarrow\emptyset$;

$E_{\mathrm{never}}\leftarrow\emptyset$;

$E_{\mathrm{best}}\leftarrow\emptyset$;

$c_{\mathrm{best}}\leftarrow\infty$;

repeat

$G^{\prime}\leftarrow(V,E\setminus E_{\mathrm{always}})$;

$p\leftarrow$ shortest path from $s$ to $t$ via $e^{*}$ in $G^{\prime}$;

$E_{p}\leftarrow$ edges in $p$;

$E_{\mathrm{upper}}\leftarrow$PATHATTACK$(G,c,w,p,E_{p},\texttt{RandPathCover})$;

$b_{\mathrm{upper}}\leftarrow\sum_{e\in E_{\mathrm{upper}}}{c(e)}$;

$E_{\mathrm{lower}}\leftarrow$PATHATTACK$(G^{\prime},c,w,p,\\{e^{*}\\}\cup
E_{\mathrm{never}},\texttt{RandPathCover})$;

$b_{\mathrm{lower}}\leftarrow\sum_{e\in E_{\mathrm{lower}}\cup
E_{\mathrm{always}}}{c(e)}$;

if  _$b_{\mathrm{upper}} <c_{\mathrm{best}}$_ then

$c_{\mathrm{best}}\leftarrow b_{\mathrm{upper}}$;

$E_{\mathrm{best}}\leftarrow E_{\mathrm{upper}}$;

end if

if  _$b_{\mathrm{lower}} <b_{\mathrm{upper}}$_ then

budget $\leftarrow$ empty hash table;

for  _$e\in E_{p}\cap E_{\mathrm{lower}}$_ do

remove $e$ from $G$;

$E_{1}\leftarrow$PATHATTACK$(G,c,w,p,E_{p},\texttt{RandPathCover})$;

budget[$e$]$\leftarrow c(e)+\sum_{e_{1}\in E_{1}}{c(e_{1})}$;

add $e$ to $G$;

end for

if  _$\exists e\in E_{p}\cap E_{\mathrm{lower}}$ where removing $e$
disconnects $s$ and $t$_ then

$E_{\mathrm{never}}\leftarrow E_{\mathrm{never}}\cup{\\{e\\}}$;

else

$e_{\mathrm{new}}\leftarrow\operatorname*{arg\,min}_{e\in E_{p}\cap
E_{\mathrm{lower}}}{\mathrm{budget}[e]}$;

$E_{\mathrm{always}}\leftarrow E_{\mathrm{always}}\cup\\{e\\}$;

end if

end if

until  _$c_{\mathrm{best}}\leq b_{\mathrm{lower}}+\epsilon$_ ;

return $E_{\mathrm{best}}$;

Algorithm 6 Heuristic Search

By Theorem 4.3, PATHATTACK converges in polynomial time. Each iteration of the
algorithm considers at most $N-1$ edges (the maximum number of edges in a
path) and runs PATHATTACK twice for each. At each iteration, at least one edge
is added to either (1) the set of edges to never cut or (2) the set of edges
to always cut. The total number of iterations is, therefore, bounded by the
number of edges. This means that PATHATTACK will be run $O(MN)$ times over the
course of Algorithm 6, which yields the following theorem.

###### Theorem 5.2.

Algorithm 6 completes in polynomial time.

##  6\. Experiments

This section presents baselines, datasets, experimental setup, and results.

###  6.1. Baseline Methods

We consider two simple greedy methods as baselines for assessing performance
of PATHATTACK. Each of these algorithms iteratively computes the shortest path
$p$ between $s$ and $t$; if $p$ is not longer than $p^{*}$, it uses some
criterion to cut an edge from $p$. When we cut the edge with minimum cost, we
refer to the algorithm as GreedyCost. We also consider a version where we cut
the edge in $p$ with the largest ratio of eigenscore555The eigenscore of an
edge is the product of the entries in the principal eigenvector of the
adjacency matrix corresponding to the edge’s vertices. to cost, since edges
with high eigenscores are known to be important in network flow (Tong et al.,
2012). This version of the algorithm is called GreedyEigenscore. In both
cases, edges from $p^{*}$ are not allowed to be cut. The baseline method to
solve Force Path Cut (or Force Node Cut) is to identify the shortest path
through $e^{*}$ (or $v^{*}$), use this path as $p^{*}$, and solve PATHATTACK.

###  6.2. Synthetic and Real Networks

We use both synthetic and real networks in our experiments. For the synthetic
networks, we run seven different graph models to generate 100 synthetic
networks of each model. We pick parameters to yield networks with similar
numbers of edges ($\approx 160$K). We use 16,000-node Erdős–Rényi graphs, both
undirected (ER) and directed (DER), with edge probability $0.00125$,
16,000-node Barabási–Albert (BA) graphs with average degree 20, 16,000-node
Watts–Strogatz (WS) graphs with average degree 20 and rewiring probability
$0.02$, $2^{14}$-node stochastic Kronecker graphs (KRON), $285\times 285$
lattices (LAT), and 565-node complete graphs (COMP).

We use seven weighted and unweighted networks. The unweighted networks are the
Wikispeedia graph (WIKI) (West et al., 2009), an Oregon autonomous system
network (AS) (Leskovec et al., 2005), and a Pennsylvania road network (PA-
ROAD) (Leskovec et al., 2009). The weighted networks are Central Chilean Power
Grid (GRID) (Kim et al., 2018), Lawrence Berkeley National Laboratory network
data (LBL), the Northeast US Road Network (NEUS), and the DBLP coauthorship
graph (DBLP) (Benson et al., 2018). All real networks are undirected except
for WIKI and LBL. The networks range from 444 edges on 347 nodes to over 8.3M
edges on over 1.8M nodes, with average degree ranging from 2.5 to 46.5 and
triangle count ranging from 40 to nearly 27M. Further details on the real and
synthetic networks—including URLs to the real data—are provided in Appendix D.

For the synthetic networks and unweighted real networks, we consider three
different edge-weight assignment schemes: Poisson, uniform random, or equal
weights. For Poisson weights, each edge $e$ has an independently random weight
$w_{e}=1+w_{e}^{\prime}$, where $w_{e}^{\prime}$ is drawn from a Poisson
distribution with rate parameter 20. For uniform weights, each weight is drawn
from a discrete uniform distribution of integers from 1 to 41. This yields the
same average weight as Poisson weights.

###  6.3. Experimental Setup

For each graph—considering graphs with different edge-weighting schemes as
distinct—we run 100 experiments. In each experiment, we select $s$ and $t$
uniformly at random among all nodes, with the exception of LAT, PA-ROAD, and
NEUS, where we select $s$ uniformly at random and select $t$ at random among
nodes 50 hops away from $s$.666This alternative method of selecting the
destination was used due to the computational expense of identifying
successive shortest paths in large grid-like networks. Given $s$ and $t$, we
identify the shortest simple paths and use the 100th, 200th, 400th, and 800th
shortest as $p^{*}$ in four experiments. For the large grid-like networks
(LAT, PA-ROAD, and NEUS), this procedure is run using only the 60-hop
neighborhood of $s$. We focus on the case where the edge removal cost is equal
to the weight (distance). For Force Edge Cut and Force Node Cut, we consider
consecutive shortest paths from $s$ to $t$ until we see 5 edges (or nodes) not
on the initial shortest path. The 5th edge (or node) we see that was not on
the original shortest path is used as $e^{*}$ (or $v^{*}$).

When running Algorithm 4, we let the nonconvex optimization (15) run no more
than 10 minutes. If a feasible point is not found in that time, we assume the
model is infeasible and increase the budget. We stop the procedure every 30
seconds to check the best candidate solution and see if it satisfies our
criteria. In addition, we stop the optimization if the objective matches the
length of our best incumbent solution. If we consider a budget for over 8
hours, we consider it infeasible and increase the lower bound. The entire
procedure is terminated, and the lowest upper bound returned, if it is still
running after 24 hours.

The experiments were run on Linux machines with 32 cores and 192 GB of memory.
The LP in PATHATTACK-Rand was implemented using Gurobi 9.1.1, and shortest
paths were computed using shortest_simple_paths in NetworkX.777Gurobi is at
https://www.gurobi.com. NetworkX is at https://networkx.org. Code from the
experiments is at https://github.com/bamille1/PATHATTACK. The combinatorial
search method is set to use 4 threads.

###  6.4. PATHATTACK Results

We treat the result of GreedyCost as our baseline cost and report the cost of
other algorithms’ solutions as a reduction from the baseline. With one
exception888GreedyEigenscore only outperforms GreedyCost in COMP with uniform
weights., GreedyCost outperforms GreedyEigenscore in both running time and
edge removal cost, so we omit the GreedyEigenscore results for clarity of
presentation. In all experiments, we edge removal costs equal to the weights.
Fig. 4 shows the results on both synthetic and real unweighted graphs, which
have had synthetic weights added to the edges. Fig. 5 shows the results on
real weighted networks. In these figures, the 800th shortest path is used as
$p^{*}$; other results were similar and omitted for brevity.

Figure 4. PATHATTACK results on synthetic and real unweighted graphs with
synthetic weights added, in terms of edge removal cost (left column) and
running time (right column). Lower is better for both metrics. Cost is plotted
as a proportion of the cost using the GreedyCost baseline. Bar heights are
means across 100 trials and error bars are standard errors. Results are shown
with equal weights on all edges (top row) and edge weights drawn from Poisson
(middle row) and Uniform (bottom row) distributions. PATHATTACK-Greedy
operated on lattices with equal weights for over one day without converging,
so results were not collected for this case. PATHATTACK yields a substantial
reduction in cost in ER, BA, KR, WIKI, and AS graphs, while the baseline is
often near-optimal for LAT and PA-ROAD. Figure 5. PATHATTACK results on real
weighted graphs in terms of edge removal cost (left) and running time (right).
Lower is better for both metrics. Cost is plotted as a proportion of the cost
using the GreedyCost baseline. Bar heights are means across 100 trials and
error bars are standard errors. Note the difference in scale on the vertical
axes from Fig. 4. PATHATTACK yields a substantial improvement in performance
for DBLP, while the baseline performs well on the other (less clustered)
networks.

Comparing the cost achieved by PATHATTACK to those obtained by the greedy
baseline, we observe some interesting phenomena. Lattices and road networks,
for example, have a similar tradeoff: PATHATTACK provides a mild improvement
in cost at the expense of an order of magnitude additional processing time.
Considering that PATHATTACK-Rand usually results in the optimal solution (over
86% of the time), this means that the baselines often achieve near-optimal
cost with a naïve algorithm. On the other hand, ER, BA, and KR graphs follow a
trend more similar to the AS and WIKI networks, particularly in the randomly
weighted cases: The cost is cut by a substantial fraction—enabling the attack
with a smaller budget—for a similar or smaller time increase. This suggests
that the time/cost tradeoff is much less favorable for less clustered, grid-
like networks (note the clustering coefficients in Appendix D).

Cliques (COMP) are particularly interesting in this case, showing a phase
transition as the entropy of the weights increases. When edge weights are
equal, cliques behave like an extreme version of the road networks: an order
of magnitude increase in run time with no decrease in cost. With Poisson
weights, PATHATTACK yields a slight improvement in cost, whereas when uniform
random weights are used, the clique behaves much more like an ER or BA graph.
In the unweighted case, $p^{*}$ is a three-hop path, so all other two- and
three-hop paths from $s$ to $t$ must be cut, which the baseline does
efficiently. Adding Poisson weights creates some randomness, but most edges
have a weight that is about average, so it is still similar to the unweighted
scenario. With uniform random weights, we get the potential for much different
behavior (e.g., short paths with many edges) for which the greedy baseline’s
performance suffers.

There is an opposite, but milder, phenomenon with PA-ROAD and LAT: using
higher-entropy weights _narrows_ the cost difference between the baseline and
PATHATTACK. This may be due to the source and destination being many hops
away. With the terminal nodes many hops apart, many shortest paths between
them could go through a few low-weight (thus low-cost) edges. A very low
weight edge between two nodes would be very likely to occur on many of the
shortest paths, and would be found in an early iteration of the greedy
algorithm and removed, while considering more shortest paths at once would
yield a similar result. We also note that, in the weighted graph data, LBL and
GRID behave similarly to road networks. Among our real datasets, these have a
low clustering coefficient (see Appendix D). This lack of overlap in nodes’
neighborhoods may lead to better relative performance with the baseline, since
there may not be a great deal of overlap between candidate paths.

###  6.5. Results Targeting a Node

In this section, we present results for the case where the adversary targets a
node $v^{*}$. The baseline in these experiments is to run PATHATTACK using the
shortest path from $s$ to $t$ through $v^{*}$ as $p^{*}$. We call this method
PATHATTACK-$v^{*}$. We present results using this method along with results
for the heuristic search method (Algorithm 6) and combinatorial optimization.

In most cases, all three methods yield a solution of the same cost. To clarify
the performance differences, we separate these cases from those where the
costs differ between methods. For the case where all methods result in the
same cost, we show running time results on unweighted graphs in Fig. 6. As
when targeting paths, lattices and road networks are similar: they are the
only graphs where the heuristic methods do not match the result of the
combinatorial optimization a majority of the time, largely due to the equal-
weight case. Watts–Strogtaz graphs, which have a lattice-like component, also
frequently have different results across methods. Fig. 7 illustrates cases
where not all algorithms yield the same cost. Again, lattices and roads are
distinct: here they see a much more substantial improvement from the
combinatorial optimization than heuristics, with Watts–Strogatz graphs also
sometimes being similar. There are many cases where the heuristic search
yields the same result as the PATHATTACK-$v^{*}$ baseline. Upon inspection,
many of these cases result from multiple shortest paths using $v^{*}$: The
heuristic overlooks one solution because it does not cut the current $p^{*}$,
which results in no edges to consider in the inner loop of Algorithm 6.

Figure 6. Running time results on unweighted networks when targeting a
specific node in cases where all three algorithms yield the same cost. Lower
time is better. Annotations are the proportion of 100 trials where all costs
are the same. Bar heights are means across these trials and error bars are
standard errors. Results are shown with equal weights on all edges (top) and
edge weights drawn from Poisson (middle) and Uniform (bottom) distributions.
With the exception of LAT and PA-ROAD, the baseline method matches the
combinatorial optimization in a majority of cases and has a substantially
smaller time requirement. Figure 7. Results on unweighted networks when
targeting a specific node in cases where not all node-targeting algorithms
yield the same cost, in terms of edge removal cost (left column) and running
time (right column). Lower is better for both metrics. Bar heights are means
across these trials and error bars are standard errors. Results are shown with
equal weights on all edges (top row) and edge weights drawn from Poisson
(middle row) and Uniform (bottom row) distributions. Note that COMP with equal
and Poisson weights and ER with Poisson weights are not included, as the
methods matched in all trials. The greatest cost reductions from using
combinatorial search often coincide with large running time increases.

For weighted networks, running time in cases where all methods yield the same
cost is plotted in Fig. 8. In all cases, the three algorithms usually find
equal-cost solutions, though the combinatorial method frequently times out.
The power grid network has a particularly large increase in running time when
using the combinatorial method. In cases where not all methods yield the same
cost, shown in Fig. 9, the heuristic search achieves the same cost as the
combinatorial search more often than in the unweighted graphs. In fact, on
DBLP, the combinatorial search typically times out and the heuristic search
outperforms it.

Figure 8. Running time results on weighted networks when targeting a specific
node in cases where all three algorithms yield the same cost. Lower time is
better. Annotations are the proportion of 100 trials where all costs are the
same. Bar heights are means across these trials and error bars are standard
errors. In contrast to the unweighted networks, the heuristic methods match
the combinatorial optimization in a large majority of cases, even in grid-like
networks. Figure 9. Results on weighted networks when targeting a specific
node in cases where not all node-targeting algorithms yield the same cost, in
terms of edge removal cost (left) and running time (right). Lower is better
for both metrics. Bar heights are means across these trials and error bars are
standard errors. Heuristic search in these cases is competitive with
combinatorial search, even outperforming it sometimes due to timeouts.

##  7\. conclusion

In this paper, we introduce the Force Path Cut, Force Edge Cut, and Force Node
Cut problems, in which edges are removed from a graph in order to make the
shortest path from one node to another, respectively, be a specific path, use
a specific edge, or use a specific node. We show that all three problems are
hard to approximate, but that a logarithmic approximation exists for Force
Path Cut via existing approximation algorithms for Set Cover. We leverage
these methods to develop a new algorithm called PATHATTACK and demonstrate its
efficacy in solving Force Path Cut using a thorough set of experiments on real
and synthetic networks. We also use PATHATTACK as part of a heuristic search
method to solve Force Edge Cut and Force Node Cut, which yields performance
similar to a more much more computationally intensive combinatorial search.

There is a gap between the approximation factor of PATHATTACK and the lower
bound implied by APX-hardness; it remains an open problem whether Force Path
Cut is APX-complete or if there is no constant-factor approximation. The best
possible polynomial-time approximation factor for 3-Terminal Cut is $12/11$
(Cunningham and Tang, 1999), and our results imply that the best such
approximation for Force Path Cut is between $12/11$ and logarithmic. Future
work will include defenses against PATHATTACK to make networks more robust
against adversarial manipulation.

###### Acknowledgements.

BAM was supported by the United States Air Force under Contract No.
FA8702-15-D-0001. TER was supported in part by the Combat Capabilities
Development Command Army Research Laboratory (under Cooperative Agreement No.
W911NF-13-2-0045) and by the Under Secretary of Defense for Research and
Engineering under Air Force Contract No. FA8702-15-D-0001. YV was supported by
grants from the Army Research Office (W911NF1810208, W911NF1910241) and
National Science Foundation (CAREER Award IIS-1905558). Any opinions,
findings, conclusions or recommendations expressed in this material are those
of the authors and should not be interpreted as representing the official
policies, either expressed or implied, of the funding agencies or the U.S.
Government. The U.S. Government is authorized to reproduce and distribute
reprints for Government purposes not withstanding any copyright notation here
on.

## References

  * (1)
  * Ahuja and Orlin (2001) Ravindra K Ahuja and James B Orlin. 2001.  Inverse Optimization.  _Operations Research_ 49, 5 (2001), 771–783.
  * Albert et al. (2000) Réka Albert, Hawoong Jeong, and Albert-László Barabási. 2000\.  Error and attack tolerance of complex networks.  _Nature_ 406, 6794 (2000), 378–382.
  * Aneja and Nair (1978) Yash P Aneja and Kunhiraman PK Nair. 1978.  The constrained shortest path problem.  _Naval Research Logistics Quarterly_ 25, 3 (1978), 549–555.
  * Benson et al. (2018) Austin R Benson, Rediet Abebe, Michael T Schaub, Ali Jadbabaie, and Jon Kleinberg. 2018.  Simplicial closure and higher-order link prediction.  _Proc. Nat. Acad. Sci._ 115, 48 (2018), E11221–E11230.
  * Bertsimas et al. (2016) Dimitris Bertsimas, Ebrahim Nasrabadi, and James B Orlin. 2016\.  On the power of randomization in network interdiction.  _Operations Research Letters_ 44, 1 (2016), 114–120.
  * Bojchevski and Günnemann (2019) Aleksandar Bojchevski and Stephan Günnemann. 2019.  Adversarial Attacks on Node Embeddings via Graph Poisoning. In _Proceedings of the 36th International Conference on Machine Learning_ (Long Beach, California, USA) _(Proceedings of Machine Learning Research, Vol. 97)_ , Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 695–704.  https://proceedings.mlr.press/v97/bojchevski19a.html
  * Brandão et al. (2021) Martim Brandão, Amanda Coles, and Daniele Magazzeni. 2021\.  Explaining Path Plan Optimality: Fast Explanation Methods for Navigation Meshes Using Full and Incremental Inverse Optimization. In _Proceedings of the International Conference on Automated Planning and Scheduling_ , Vol. 31. AAAI Press, Palo Alto, California USA, 56–64.
  * Call and Holmberg (2011) Mikael Call and Kaj Holmberg. 2011.  Complexity of Inverse Shortest Path Routing. In _International Conference on Network Optimization_. Springer, Berlin, Heidelberg, 339–353.
  * Chang et al. (2020) Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. 2020\.  A restricted black-box adversarial framework towards attacking graph embedding models. In _AAAI_. AAAI Press, Palo Alto, California USA, 3389–3396.
  * Chen et al. (2019) Jinyin Chen, Lihong Chen, Yixian Chen, Minghao Zhao, Shanqing Yu, Qi Xuan, and Xiaoniu Yang. 2019.  GA-based Q-attack on community detection.  _IEEE Transactions on Computational Social Systems_ 6, 3 (2019), 491–503.
  * Chen et al. (2020) Jinyin Chen, Yixian Chen, Lihong Chen, Minghao Zhao, and Qi Xuan. 2020.  Multiscale evolutionary perturbation attack on community detection.  _IEEE Transactions on Computational Social Systems_ 8, 1 (2020), 62–75.
  * Chen et al. (2018) Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. 2018\.  Fast Gradient Attack on Network Embedding.  https://doi.org/10.48550/ARXIV.1809.02797
  * Cui and Hochbaum (2010) Tingting Cui and Dorit S Hochbaum. 2010.  Complexity of some inverse shortest path lengths problems.  _Networks_ 56, 1 (2010), 20–29.
  * Cunningham and Tang (1999) William H Cunningham and Lawrence Tang. 1999.  Optimal 3-terminal cuts and linear programming. In _International Conference on Integer Programming and Combinatorial Optimization_. Springer, Springer, Berlin, Heidelberg, 114–125.
  * Dahlhaus et al. (1994) Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. 1994.  The complexity of multiterminal cuts.  _SIAM J. Comput._ 23, 4 (1994), 864–894.
  * Dai et al. (2018) Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. 2018.  Adversarial Attack on Graph Structured Data. In _ICML_. PMLR, 1115–1124.
  * Deaconu and Ciupala (2020) Adrian Deaconu and Laura Ciupala. 2020.  Inverse Minimum Cut Problem with Lower and Upper Bounds.  _Mathematics_ 8, 9 (2020), 10 pages.
  * Fionda and Pirro (2017) Valeria Fionda and Giuseppe Pirro. 2017.  Community deception or: How to stop fearing community detection algorithms.  _IEEE Transactions on Knowledge and Data Engineering_ 30, 4 (2017), 660–673.
  * Gács and Lovász (1981) Peter Gács and Laszlo Lovász. 1981.  Khachiyan’s algorithm for linear programming.  In _Mathematical Programming at Oberwolfach_. Springer, Berlin, Heidelberg, 61–68.
  * Grötschel et al. (1981) Martin Grötschel, László Lovász, and Alexander Schrijver. 1981.  The ellipsoid method and its consequences in combinatorial optimization.  _Combinatorica_ 1, 2 (1981), 169–197.
  * Jain et al. (2011) Manish Jain, Dmytro Korzhyk, Ondřej Vaněk, Vincent Conitzer, Michal Pěchouček, and Milind Tambe. 2011\.  A double oracle algorithm for zero-sum security games on graphs. In _AAMAS_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 327–334.
  * Jiang et al. (2010) Yiwei Jiang, Longcheng Liu, Biao Wu, and Enyu Yao. 2010\.  Inverse minimum cost flow problems under the weighted Hamming distance.  _European Journal of Operational Research_ 207, 1 (2010), 50–54.
  * Jiang et al. (2020) Zhongyuan Jiang, Jing Li, Jianfeng Ma, and Philip S. Yu. 2020\.  Similarity-based and sybil attack defended community detection for social networks.  _IEEE Transactions on Circuits and Systems II: Express Briefs_ 67, 12 (2020), 3487–3491.
  * Jun and D’Andrea (2003) Myungsoo Jun and Raffaello D’Andrea. 2003.  Path planning for unmanned aerial vehicles in uncertain and adversarial environments.  In _Cooperative Control: Models, Applications and Algorithms_. Springer US, Boston, MA, 95–110.
  * Kegelmeyer et al. (2018) W. Philip Kegelmeyer, Jeremy D Wendt, and Ali Pinar. 2018\.  _An Example of Counter-Adversarial Community Detection Analysis_.  Technical Report SAND2018-12068. Sandia National Laboratories.  https://doi.org/10.2172/1481570
  * Kim et al. (2018) Heetae Kim, David Olave-Rojas, Eduardo Álvarez-Miranda, and Seung-Woo Son. 2018.  In-depth data on the network structure and hourly activity of the Central Chilean power grid.  _Sci. Data_ 5, 1 (2018), 1–10.
  * Leskovec et al. (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005\.  Graphs over time: Densification laws, shrinking diameters and possible explanations. In _KDD_. Association for Computing Machinery, New York, NY, USA, 177–187.
  * Leskovec et al. (2009) Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. 2009.  Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters.  _Internet Mathematics_ 6, 1 (2009), 29–123.
  * Letchford and Vorobeychik (2013) Joshua Letchford and Yevgeniy Vorobeychik. 2013.  Optimal Interdiction of Attack Plans. In _AAMAS_. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 199–206.
  * Li et al. (2020) Jia Li, Honglei Zhang, Zhichao Han, Yu Rong, Hong Cheng, and Junzhou Huang. 2020\.  Adversarial attack on community detection by hiding individuals. In _WWW_. Association for Computing Machinery, New York, NY, USA, 917–927.
  * Liu and Zhang (2006) Longcheng Liu and Jianzhong Zhang. 2006.  Inverse maximum flow problems under the weighted Hamming distance.  _Journal of Combinatorial Optimization_ 12, 4 (2006), 395–408.
  * Miller et al. (2021) Benjamin A. Miller, Zohair Shafi, Wheeler Ruml, Yevgeniy Vorobeychik, Tina Eliassi-Rad, and Scott Alfeld. 2021.  PATHATTACK: Attacking Shortest Paths in Complex Networks. In _Machine Learning and Knowledge Discovery in Databases. Research Track_ , Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and Jose A. Lozano (Eds.). Springer International Publishing, Cham, 532–547.
  * Nagaraja (2010) Shishir Nagaraja. 2010\.  The impact of unlinkability on adversarial community detection: Effects and countermeasures. In _PETS_. Springer, Berlin, Heidelberg, 253–272.
  * Nardelli et al. (2003) Enrico Nardelli, Guido Proietti, and Peter Widmayer. 2003\.  Finding the most vital node of a shortest path.  _Theoretical Computer Science_ 296, 1 (2003), 167–177.
  * Raz and Safra (1997) Ran Raz and Shmuel Safra. 1997.  A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In _STOC_. Association for Computing Machinery, New York, NY, USA, 475–484.
  * Tayyebi and Massoud (2016) Javad Tayyebi and AMAN Massoud. 2016.  Efficient algorithms for the reverse shortest path problem on trees under the hamming distance.  _Yugoslav Journal of Operations Research_ 27, 1 (2016), 46–60.
  * Tong et al. (2012) Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2012\.  Gelling, and melting, large graphs by edge manipulation. In _CIKM_. Association for Computing Machinery, New York, NY, USA, 245–254.
  * Vazirani (2003a) Vijay V. Vazirani. 2003a.  _Approximation Algorithms_.  Springer, Berlin, Heidelberg.
  * Vazirani (2003b) Vijay V. Vazirani. 2003b.  Rounding Applied to Set Cover.  In _Approximation Algorithms_. Springer, Berlin, Heidelberg, Chapter 14, 118–123.
  * Waniek et al. (2018) Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. 2018.  Hiding individuals and communities in a social network.  _Nature Human Behaviour_ 2, 2 (2018), 139–147.
  * Washburn and Wood (1995) Alan Washburn and Kevin Wood. 1995.  Two-person zero-sum games for network interdiction.  _Operations Research_ 43, 2 (1995), 243–251.
  * West et al. (2009) Robert West, Joelle Pineau, and Doina Precup. 2009\.  Wikispeedia: An online game for inferring semantic distances between concepts. In _IJCAI_. AAAI Press, Palo Alto, California USA, 1598–1603.
  * Wu et al. (2019) Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. 2019\.  Adversarial examples for graph data: Deep insights into attack and defense. In _IJCAI_. IJCAI, 4816–4823.
  * Xu et al. (2019) Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. 2019.  Topology attack and defense for graph neural networks: an optimization perspective. In _IJCAI_. IJCAI, 3961–3967.
  * Xu and Zhang (1995) Shaoji Xu and Jianzhong Zhang. 1995.  An Inverse Problem of the Weighted Shortest Path Problem.  _Japan journal of industrial and applied mathematics_ 12, 1 (1995), 47–59.
  * Zhang and Wang (2008) Bin-wu Zhang and Qin Wang. 2008.  Inverse shortest path problems under Hamming distance.  _Journal of Hohai University (Natural Sciences)_ 36, 4 (July 2008), 04.
  * Zhang and Lin (2003) Jianzhong Zhang and Yixun Lin. 2003.  Computation of the reverse shortest-path problem.  _Journal of Global Optimization_ 25, 3 (2003), 243–261.
  * Zhang et al. (1995) Jianzhong Zhang, Zhongfan Ma, and Chao Yang. 1995.  A Column Generation Method for Inverse Shortest Path Problems.  _Zeitschrift für Operations Research_ 41, 3 (1995), 347–358.
  * Zügner et al. (2018) Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018\.  Adversarial Attacks on Neural Networks for Graph Data. In _KDD_. Association for Computing Machinery, New York, NY, USA, 2847–2856.

##  Appendix A Proof of Theorem 3.1

###  A.1. Proof for Undirected Graphs

As noted in Section 3.1, to prove Theorem 3.1, we first prove that Force Path
Cut is APX-hard for undirected graphs.

###### Lemma A.1.

Force Path Cut is APX-hard for undirected graphs, including the case where all
weights and all costs are equal.

To prove Lemma A.1, we reduce 3-Terminal Cut to Force Path Cut via a linear
reduction. Let $G=(V,E)$ be an undirected graph, where all weights are equal.
We also have three terminal nodes $s_{1}$, $s_{2}$, and $s_{3}\in V$. Since we
are proving the problem is APX-hard, we consider the optimization version of
3-Terminal Cut and Force Path Cut, where the goal is to minimize the budget.
Thus, the goal of 3-Terminal Cut is to find the smallest set $E^{\prime}$ such
that $s_{1}$, $s_{2}$, and $s_{3}$ are disconnected in
$G^{\prime}=(V,E\setminus E^{\prime})$. Dahlhaus et al. show in (Dahlhaus et
al., 1994) that 3-Terminal Cut is APX-hard, even when all weights are
equal.999More specifically, it is proved in (Dahlhaus et al., 1994) that the
problem is MAX SNP-hard, but this implies APX-hardness: if a problem is MAX
SNP-hard, it has no polynomial time approximation scheme unless P=NP.

We propose a linear reduction from 3-Terminal Cut to Force Path Cut. As
discussed in (Dahlhaus et al., 1994), a linear reduction from problem $A$ to
problem $B$ consists of two functions $f$ and $g$, where $f$ maps an instance
of $A$ to an instance of $B$, and $g$ maps a solution of $B$ to a solution of
$A$. To be a linear reduction, the following conditions must hold:

  1. (1)

The functions $f$ and $g$ can be computed in polynomial time.

  2. (2)

Given $\mathcal{A}$, an instance of problem $A$, the optimal solution to
$\mathcal{B}=f(\mathcal{A})$ must be at most $\alpha$ times the optimal
solution for $\mathcal{A}$, for a constant $\alpha>0$, i.e.,
$\mathrm{opt}(\mathcal{B})\leq\alpha\cdot\mathrm{opt}(\mathcal{A})$.

  3. (3)

Given a solution $y$ to $\mathcal{B}=f(\mathcal{A})$, $x=g(y)$ is a solution
to $\mathcal{A}$ such that

$|\mathrm{cost}(x)-\mathrm{opt}(\mathcal{A})|\leq\beta|\mathrm{cost}(y)-\mathrm{opt}(\mathcal{B})|$

for a constant $\beta>0$.

We start by defining $f$, the function from an instance of 3-Terminal Cut to
an instance of Force Path Cut. We are given an instance of 3-Terminal Cut as
described above. Let $N=|V|$ and $M=|E|$. As shown in Figure 1, we add $M+1$
new paths of length $N$ from $s_{1}$ to $s_{2}$, and the same from $s_{2}$ to
$s_{3}$. We add a single path of length $2N-1$ from $s_{1}$ to $s_{3}$.
Algorithm 7 provides pseudocode for this procedure.

Input: Graph $G=(V,E)$, terminals $s_{1},s_{2},s_{3}$

Output: Graph $\hat{G}$, target path $p^{*}$

$\hat{V}\leftarrow V$; $N\leftarrow|V|$;

$\hat{E}\leftarrow E$; $M\leftarrow|E|$;

// Create paths from $s_{1}$ to $s_{2}$

for  _$i\leftarrow 1$ to $M+1$_ do

$v_{\mathrm{prev}}\leftarrow s_{1}$;

for  _$j\leftarrow 1$ to $N-1$_ do

$v_{ij,1}\leftarrow$ new node;

$\hat{V}\leftarrow\hat{V}\cup\\{v_{ij,1}\\}$;

$\hat{E}\leftarrow\hat{E}\cup\\{\\{v_{\mathrm{prev}},v_{ij,1}\\}\\}$;

$v_{\mathrm{prev}}\leftarrow v_{ij,1}$;

end for

$\hat{E}\leftarrow\hat{E}\cup\\{\\{v_{\mathrm{prev}},s_{2}\\}\\}$;

end for

// Create paths from $s_{2}$ to $s_{3}$

for  _$i\leftarrow 1$ to $M+1$_ do

$v_{\mathrm{prev}}\leftarrow s_{2}$;

for  _$j\leftarrow 1$ to $N-1$_ do

$v_{ij,2}\leftarrow$ new node;

$\hat{V}\leftarrow\hat{V}\cup\\{v_{ij,2}\\}$;

$\hat{E}\leftarrow\hat{E}\cup\\{\\{v_{\mathrm{prev}},v_{ij,2}\\}\\}$;

$v_{\mathrm{prev}}\leftarrow v_{ij,2}$;

end for

$\hat{E}\leftarrow\hat{E}\cup\\{\\{v_{\mathrm{prev}},s_{3}\\}\\}$;

end for

// Create $p^{*}$ (a path from $s_{1}$ to $s_{3}$)

$v_{\mathrm{prev}}\leftarrow s_{1}$;

$p^{*}\leftarrow$ empty path;

for  _$j\leftarrow 1$ to $2N-2$_ do

$v_{ij,3}\leftarrow$ new node;

$\hat{V}\leftarrow\hat{V}\cup\\{v_{ij,3}\\}$;

$\hat{E}\leftarrow\hat{E}\cup\\{\\{v_{\mathrm{prev}},v_{ij,3}\\}\\}$;

append $\\{v_{\mathrm{prev}},v_{ij,3}\\}$ to the end of $p^{*}$;

$v_{\mathrm{prev}}\leftarrow v_{ij,3}$;

end for

$\hat{E}\leftarrow\hat{E}\cup\\{\\{v_{\mathrm{prev}},s_{3}\\}\\}$;

append $\\{v_{\mathrm{prev}},s_{3}\\}$ to the end of $p^{*}$;

return $\hat{G}=(\hat{V},\hat{E})$, $s_{1}$, $s_{3}$, $p^{*}$;

Algorithm 7 Mapping from 3-Terminal Cut to Force Path Cut.

Applying Algorithm 7 to an instance of 3-Terminal Cut $(G,s_{1},s_{2},s_{3})$,
we get $(G^{\prime},s_{1},s_{3},p^{*})$, an instance of Force Path Cut. Note
that, in these instances, all edge weights and removal costs are equal to 1.
From the instance of Force Path Cut, we get a solution $E^{\prime}$. We also
have a function that maps a solution to Force Path Cut to a solution to
3-Terminal Cut: include all edges in $E^{\prime}$ that existed in the original
graph, i.e.,

(23) $g(E^{\prime})=\begin{cases}E^{\prime}\cap E&\textrm{if
}|E^{\prime}|<M\\\ E&\textrm{otherwise}\end{cases}$

where $E^{\prime}$ is the solution to Force Path Cut and $E$ is the original
edge set from the 3-Terminal Cut instance. (The edge set $E$ is not a
parameter of $g$, as it is fixed within the context of the problem.)

We can see that both functions satisfy condition (1): The function $g$ simply
removes up to $M$ edges from a set, and the body of each loop takes constant
time in Algorithm 7, and there are two nested loops taking $O(MN)$ time and a
final loop taking $O(N)$ time. To show that this reduction satisfies condition
(2), we first prove the following Lemma.

###### Lemma A.2.

Let $\mathcal{A}$ be an instance of 3-Terminal Cut and $E^{\prime}$ be a
solution to $\mathcal{A}$. Then $E^{\prime}$ is also a solution to
$f(\mathcal{A})$.

###### Proof.

Since $E^{\prime}$ is a solution to $\mathcal{A}$, the graph
$G^{\prime}=(V,E\setminus E^{\prime})$ has at least three connected
components, where one contains $s_{1}$, one contains $s_{2}$, and one contains
$s_{3}$. The edges $E_{\mathrm{new}}$ added by Algorithm 7 create paths
between the connected components, but do not connect to any vertices in the
original graph other than $s_{1}$, $s_{2}$, and $s_{3}$. Thus, there are two
modes of traversing from $s_{1}$ to $s_{3}$ via a simple path: (1) traverse
the new path from $s_{1}$ to $s_{3}$ denoted as $p^{*}$ by Algorithm 7, or (2)
move from $s_{1}$ to $s_{2}$ via edges from $E_{\mathrm{new}}$, then from
$s_{2}$ to $s_{3}$ via edges from $E_{\mathrm{new}}$. By construction, the
path directly from $s_{1}$ to $s_{3}$ (the path added in the final loop of
Algorithm 7) passes through $2N-2$ intermediate nodes, having a length of
$2N-1$. Taking the indirect route first requires taking one of the $M+1$ paths
from $s_{1}$ to $s_{2}$, which has length $N$, then taking one of the $M+1$
paths from $s_{2}$ to $s_{3}$, which also has length $N$. Thus, the total
length of any path via $s_{2}$ is $2N$, which is longer than $p^{*}$. Thus,
$p^{*}$ is the shortest path from $s_{1}$ to $s_{3}$ in
$\hat{G}^{\prime}=(\hat{V},\hat{E}\setminus E^{\prime})$, so $E^{\prime}$ is a
solution to $f(a)$. ∎

An immediate consequence of Lemma A.2 is that condition (2) is satisfied, as
stated formally below.

###### Corollary A.3.

If $\mathcal{A}$ is an instance of 3-Terminal Cut, then
$\mathrm{opt}(f(\mathcal{A}))\leq\mathrm{opt}(\mathcal{A})$, satisfying
condition (2) with $\alpha=1$.

###### Proof.

Let $E^{\prime}$ be the optimal solution to $\mathcal{A}$, i.e.,
$|E^{\prime}|=\mathrm{opt}(\mathcal{A})$. By Lemma A.2, $E^{\prime}$ also
solves $f(\mathcal{A})$. Thus, the optimal solution to $f(\mathcal{A})$ can be
no larger than $|E^{\prime}|$, and therefore
$\mathrm{opt}(f(\mathcal{A}))\leq\mathrm{opt}(\mathcal{A})$. ∎

While the above corollary is sufficient to satisfy condition (2), we can make
a stronger statement that is useful to prove condition (3): the optimal
solutions of the two problems are the same.

###### Lemma A.4.

For an instance of 3-Terminal Cut $\mathcal{A}$,
$\mathrm{opt}(\mathcal{A})=\mathrm{opt}(f(\mathcal{A}))$. In particular, if
$E^{\prime}$ is an optimal solution for $\mathcal{A}$, then it is also an
optimal solution for $f(\mathcal{A})$.

###### Proof.

Let $G=(V,E)$ be the graph in $\mathcal{A}$, and $\hat{G}=(\hat{V},\hat{E})$
be the graph in problem $f(\mathcal{A})$. Let $\hat{E}^{\prime}$ be an optimal
solution to $f(\mathcal{A})$. Partition $\hat{E}^{\prime}$ into the edges that
occur in the original graph $E_{1}=\hat{E}^{\prime}\cap E$, and those that do
not, $E_{2}=\hat{E}^{\prime}\setminus E$. By Lemma A.2, if $E_{1}$ is a
solution to $\mathcal{A}$, it is also a solution to $f(\mathcal{A})$.
Therefore, if $E_{1}$ is a solution to $\mathcal{A}$, $E_{2}=\emptyset$
(otherwise we contradict the assumption that $\hat{E}^{\prime}$ is an optimal
solution to $f(\mathcal{A})$. Thus, we focus on the case where $E_{1}$ is not
a solution to $\mathcal{A}$. In this case, within the graph
$G_{1}=(V,E\setminus E_{1})$, not all terminals $s_{1}$, $s_{2}$, and $s_{3}$
are disconnected. If there is a path from $s_{1}$ to $s_{3}$, the length of
this path is at most $N-1$, which is shorter than $p^{*}$. This contradicts
the assumption that $\hat{E}^{\prime}$ is a solution to $f(\mathcal{A})$.
There are two other possibilities: $s_{1}$ and $s_{2}$ are connected in
$G_{1}$, or $s_{2}$ and $s_{3}$ are connected. If $s_{1}$ and $s_{2}$ are
connected, there is a path between the terminals of length at most $N-2$
(excluding $s_{3}$). Algorithm 7 inserts $M+1$ independent parallel paths from
$s_{2}$ to $s_{3}$. If any of these paths remains, there is a path in
$\hat{G}^{\prime}=(\hat{V},\hat{E}\setminus\hat{E}^{\prime})$ from $s_{2}$ to
$s_{3}$ of length $N$, which would create a path from $s_{1}$ to $s_{3}$ of
length at most $2N-2$, which is shorter than $p^{*}$. Thus, $\hat{E}^{\prime}$
would have to include at least one edge from all $M+1$ parallel paths from
$s_{2}$ to $s_{3}$ inserted by Algorithm 7. This means that $|E_{2}|\geq M+1$,
implying that $|\hat{E}^{\prime}|\geq M+1$. This contradicts the assumption
that $\hat{E}^{\prime}$ is an optimal solution: any solution to $\mathcal{A}$
is a solution to $f(\mathcal{A})$ and its cost is at most $M$. The analogous
argument holds if $s_{2}$ and $s_{3}$ are connected in $G_{1}$. Thus, a
solution to $f(\mathcal{A})$ cannot be optimal if it does not include a
solution to $\mathcal{A}$, implying that
$\mathrm{opt}(f(\mathcal{A}))\geq\mathrm{opt}(\mathcal{A})$. This in
conjunction with Corollary A.3 proves that the optima of $\mathcal{A}$ and
$f(\mathcal{A})$ are the same. ∎

To show that the reduction also satisfies condition (3), we first prove the
following lemma.

###### Lemma A.5.

Let $\mathcal{A}$ be an instance of 3-Terminal Cut where all weights are
equal, with $G=(V,E)$. Let $\mathcal{B}=f(\mathcal{A})$ be the instance of
Force Path Cut obtained by applying Algorithm 7 to $\mathcal{A}$, with
$\hat{G}=(\hat{V},\hat{E})$. Further, let $\hat{E}^{\prime}$ be a solution to
$\mathcal{B}$. Then $g(\hat{E}^{\prime})$ is a solution to $\mathcal{A}$.

###### Proof.

The case where $|\hat{E}^{\prime}|\geq M$ is trivial: If all edges are
removed, then the terminals are disconnected. With the assumption that
$|\hat{E}^{\prime}|<M$, partition $\hat{E}^{\prime}$ into two parts:
$E_{1}=\hat{E}^{\prime}\cap E$ and $E_{2}=\hat{E}^{\prime}\setminus E1$, i.e.,
$E_{1}$ is the edges in the solution to $\mathcal{B}$ that existed in the
original graph, and $E_{2}$ consists of the edges in the solution added by $f$
(Algorithm 7). Since $\hat{E}^{\prime}$ is a solution to $\mathcal{B}$,
$p^{*}$ is the shortest path from $s_{1}$ to $s_{3}$ in the graph
$\hat{G}^{\prime}=(\hat{V},\hat{E}\setminus\hat{E}^{\prime})$. The length of
$p^{*}$ is $2N-1$. Assume $E_{1}$ is not a solution to $\mathcal{A}$, i.e.,
that $s_{1}$, $s_{2}$, and $s_{3}$ are not disconnected in
$G_{1}=(V,E\setminus E_{1})$. Then there would be a path between at least two
of the three terminals in $G_{1}$. If there were a path from $s_{1}$ to
$s_{3}$, the length of this path would be at most $N-1<2N-1$, so this
contradicts the assumption that $p^{*}$ is the shortest path in
$\hat{G}^{\prime}$. For the other cases, assume there is no such path (i.e.,
$s_{1}$ and $s_{3}$ are disconnected in $G_{1}$). Suppose there is a path
between $s_{1}$ and $s_{2}$. This path’s length is at most $N-2$ (since it
cannot include $s_{3}$). In addition, either (1) one of the paths from $s_{2}$
to $s_{3}$ added by $f$ remains, or (2) all $M+1$ such paths were cut, which
contradicts our assumption since it would require $\hat{E}^{\prime}$ to
contain at least $M+1$ edges. The paths from $s_{2}$ to $s_{3}$ added in
Algorithm 7 have length $N$, thus creating a path from $s_{1}$ to $s_{3}$ with
length at most $2N-2<2N-1$, which also contradicts the assumption that $p^{*}$
is the shortest path. A similar argument is made for the case where a path
from $s_{2}$ to $s_{3}$ remains in $G_{1}$: Such a path would have length at
most $N-2$, and at least one of the paths added between $s_{1}$ and $s_{2}$
remains, resulting in a path of length at most $2N-2$. Thus, in the case where
$|\hat{E}^{\prime}|<M$, $\hat{E}^{\prime}\cap E$ is a solution to
$\mathcal{A}$. ∎

With this result, we can show the reduction meets the final criterion.

###### Lemma A.6.

If $\mathcal{A}$ is an instance of 3-Terminal Cut with $G=(V,E)$, $y$ is a
solution to $\mathcal{B}=f(\mathcal{A})$, and $x=g(y)$, then

$|\mathrm{cost}(x)-\mathrm{opt}(\mathcal{A})|\leq|\mathrm{cost}(y)-\mathrm{opt}(\mathcal{B})|,$

satisfying (3) with $\beta=1$.

###### Proof.

Let $\hat{E}^{\prime}$ be a solution to $\mathcal{B}$, and partition
$\hat{E}^{\prime}$ into $E_{1}=\hat{E}^{\prime}\cap E$ and
$E_{2}=\hat{E}^{\prime}\setminus E_{1}$. From Lemma A.5, we know that
$g(\hat{E}^{\prime})$ solves $\mathcal{A}$. From Lemma A.4, we also know the
optimal solutions are the same size. If $|\hat{E}^{\prime}|\geq M$, then
$g(\hat{E}^{\prime})=E$, and we have

(24)
$\left||E|-\mathrm{opt}(\mathcal{A})\right|=|M-\mathrm{opt}(\mathcal{A})|=|M-\mathrm{opt}(\mathcal{B})|\leq\left||\hat{E}^{\prime}|-\mathrm{opt}(\mathcal{B})\right|,$

so the condition holds. If $|\hat{E}^{\prime}|<M$, we have

(25) $\left||\hat{E}^{\prime}\cap
E|-\mathrm{opt}(\mathcal{A})\right|=\left||\hat{E}^{\prime}\cap
E|-\mathrm{opt}(\mathcal{B})\right|\leq\left||\hat{E}^{\prime}|-\mathrm{opt}(\mathcal{B})\right|,$

which proves the claim. ∎

These intermediate results show that the proposed reduction is a linear
reduction of 3-Terminal Cut to Force Path Cut, implying that Force Path Cut is
APX-hard.

###### Proof of Lemma A.1.

By construction, $f$, as described by Algorithm 7, takes an instance of
3-Terminal Cut and maps it to an instance of Force Path Cut. As shown in the
pseudocode, this takes $O(MN)$ time to compute. By Lemma A.5, $g$ maps a
solution to the instance of Force Path Cut obtained via $f$ to a solution to
the original 3-Terminal Cut problem. The procedure of removing the original
edge set takes polynomial time that varies depending on the data structure,
e.g., $O(MN)$ per removal in an adjacency list. Thus, $f$ and $g$ are
appropriate mappings that take polynomial time to compute, satisfying
condition (1). By Corollary A.3, the reduction satisfies condition (2), and by
Lemma A.6, it satisfies (3). This means that $f$ and $g$ provide a linear
reduction from 3-Terminal Cut to Force Path Cut. Since 3-Terminal Cut is APX-
hard, Force Path Cut for undirected graphs is APX-hard as well. ∎

###  A.2. Proof for Directed Graphs

To prove that Force Path Cut is APX-hard for directed graphs, we formulate a
linear reduction from Force Path Cut for undirected graphs to the directed
case. The linear reduction in this case is simple. The function $f$ that maps
an undirected instance of Force Path Cut to a directed one simply takes each
edge from the former and includes the two edges between the associated nodes
in both directions. The values of $p^{*}$, $s$, and $t$ remain the same.
Formally, $f$ replaces $E$ with

(26) $\hat{E}=\bigcup_{\\{u,v\\}\in E}{\\{(u,v),(v,u)\\}}.$

The graph $\hat{G}=(V,\hat{E})$ can be constructed in $O(N+M)$ time.

If we have a solution to Force Path Cut on the directed graph $\hat{G}$, there
is a similarly simple mapping to a solution to undirected Force Path Cut:
include the undirected version of each edge in the solution. This takes $O(M)$
time. We show that this mapping provides a solution to the original problem in
the following lemma.

###### Lemma A.7.

Let $\mathcal{A}$ be an undirected instance of Force Path Cut, and
$f(\mathcal{A})$ be its corresponding directed instance. If $\hat{E}^{\prime}$
is a solution to $f(\mathcal{A})$, then the undirected solution

(27) $E^{\prime}=\bigcup_{(u,v)\in\hat{E}^{\prime}}{\\{\\{u,v\\}\\}}$

solves $\mathcal{A}$.

###### Proof.

Suppose $E^{\prime}$ did not solve $\mathcal{A}$, i.e., $p^{*}$ is not the
shortest path from $s$ to $t$ in $G^{\prime}=(V,E\setminus E^{\prime})$. Then
there is some other path, $\hat{p}$, from $s$ to $t$ that is not longer than
$p^{*}$. However, this path also exists in
$\hat{G}^{\prime}=(V,\hat{E}\setminus\hat{E}^{\prime})$: all edges from $E$
were added in the creation of $\hat{E}$, so if $\hat{p}$ were not in
$\hat{G}^{\prime}$, at least one edge from $\hat{p}$ would have to be in
$\hat{E}^{\prime}$. The mapping $g$ would include the undirected version of
this edge in $E^{\prime}$, which would cut $\hat{p}$ in $G$ as well. Thus, the
existence of $\hat{p}$ contradicts the assumption that $\hat{E}^{\prime}$ is a
solution to $f(\mathcal{A})$, proving the claim. ∎

###### Lemma A.8.

Let $E^{\prime}$ be a solution to Force Path Cut on a directed graph. If
$(u,v)\in E^{\prime}$ and $(v,u)\in E^{\prime}$, then either
$E^{\prime}\setminus\\{(u,v)\\}$ or $E^{\prime}\setminus\\{(v,u)\\}$ is also a
solution to Force Path Cut.

###### Proof.

Let $d(v_{1},v_{2})$ be the distance between $v_{1}$ and $v_{2}$ in the
directed graph $G^{\prime}=(V,E\setminus E^{\prime})$. (If a path does not
exist between $v_{1}$ and $v_{2}$, then $d(v_{1},v_{2})=\infty$.)

First, consider the case where both $u$ and $v$ are on $p^{*}$. Assume without
loss of generality that $u$ precedes $v$ on the path. Then $(v,u)$ did not
need to be removed from the edge set. Since $p^{*}$ is the shortest path from
$s$ to $t$, it is comprised of shortest paths between all intermediate nodes
on the path; for example, the shortest path from $s$ to $v$ and the shortest
path from $v$ to $t$. Removing $(v,u)$ from $E^{\prime}$—leaving the edge in
the graph when solving Force Path Cut—would not change the status of $p^{*}$
as the shortest path from $s$ to $t$: The shortest path from $s$ to $v$ would
still include $u$, and adding $(v,u)$ back to the graph would only enable
moving backward along the path. This means that
$E^{\prime}\setminus\\{(v,u)\\}$ is also a solution.

Now consider a case where one of $u$ and $v$ is part of $p^{*}$, but the other
is not. Without loss of generality, assume $u$ is on $p^{*}$ and $v$ is not.
Let $\ell_{p^{*}}$ be the length of $p^{*}$. Since $p^{*}$ is the shortest
path, we know that $d(s,v)+d(v,t)>\ell_{p^{*}}$. Since $u$ is on $p^{*}$, we
have $d(s,u)+d(u,t)=\ell_{p^{*}}$. Suppose the claim does not hold: that
neither $E^{\prime}\setminus\\{(u,v)\\}$ nor $E^{\prime}\setminus\\{(v,u)\\}$
is a solution. This means that adding $(u,v)$ back into the edge set must
create a path not longer than $p^{*}$, so we have
$d(s,u)+d(v,t)+1\leq\ell_{p^{*}}$. The same is true for $(v,u)$, implying that
$d(s,v)+d(u,t)+1\leq\ell_{p^{*}}$. Adding the latter two inequalities, we have

(28) $d(s,u)+d(u,t)+d(s,v)+d(v,t)+2\leq 2\ell_{p^{*}}\Rightarrow
d(s,v)+d(v,t)\leq\ell_{p^{*}}-2,$

where we use the equation $d(s,u)+d(u,t)=\ell_{p^{*}}$. This contradicts the
first inequality, that the path from $s$ to $t$ via $v$ is longer than
$p^{*}$. In the case where neither $u$ nor $v$ is on $p^{*}$, we replace
$d(s,u)+d(u,t)=\ell_{p^{*}}$ with $d(s,u)+d(u,t)>\ell_{p^{*}}$, and the
inequality in (28) becomes strict. Thus, if both $(u,v)$ and $(v,u)$ are in
$E^{\prime}$, then either $E^{\prime}\setminus\\{(u,v)\\}$ or
$E^{\prime}\setminus\\{(v,u)\\}$ is also a solution to Force Path Cut. ∎

This lemma has an immediate consequence that is important for proving the
reduction is linear.

###### Corollary A.9.

Let $E^{\prime}$ be an optimal solution to Force Path Cut on a directed graph.
If $(u,v)\in E^{\prime}$, then $(v,u)\notin E^{\prime}$.

###### Proof.

From Lemma A.8, if $E^{\prime}$ contained both $(u,v)$ and $(v,u)$, then
removal of one of these edges would still be a solution. Since the resulting
solution would be smaller than $E^{\prime}$, this contradicts the premise of
the claim. ∎

In addition, we obtain the optimal solution to the undirected problem if we
find the optimal solution to the directed problem via the reduction.

###### Lemma A.10.

Let $\mathcal{A}$ be an undirected instance of Force Path Cut and
$f(\mathcal{A})$ be the corresponding directed instance. Then the optimal
solution to $f(\mathcal{A})$ is the optimal solution to $\mathcal{A}$.

###### Proof.

By Lemma A.7, we know that the optimal solution to $f(\mathcal{A})$ solves
$\mathcal{A}$, so $\mathrm{opt}(\mathcal{A})\leq\mathrm{opt}(f(\mathcal{A}))$.
Let $E^{\prime}$ be an optimal solution to $\mathcal{A}$. Let
$\hat{E}^{\prime}$ be a solution to $f(\mathcal{A})$ that includes both
directed edges for each undirected edge in $E^{\prime}$, i.e.,

(29) $\hat{E}^{\prime}=\bigcup_{\\{u,v\\}\in E^{\prime}}{\\{(u,v),(v,u)\\}}.$

Since $E^{\prime}$ is a solution to $\mathcal{A}$, $\hat{E}^{\prime}$ is a
solution to $f(\mathcal{A})$. (Otherwise a path $\hat{p}$ in $f(\mathcal{A})$
that is shorter than $p^{*}$ would not be removed by $E^{\prime}$.) However,
$\hat{E}^{\prime}$ contains a pair of edges for each edge in $E^{\prime}$: for
any $(u,v)\in\hat{E}^{\prime}$, we have $(v,u)\in\hat{E}^{\prime}$. By Lemma
A.8, one edge from each pair can be removed. This means that, for an optimal
solution to $\mathcal{A}$, we can find a solution to $f(\mathcal{A})$ that is
the same size, which implies that
$\mathrm{opt}(f(\mathcal{A}))\leq\mathrm{opt}(\mathcal{A})$. This means that
$\mathrm{opt}(\mathcal{A})=\mathrm{opt}(f(\mathcal{A}))$, and an optimal
solution for one problem can be applied to the other. ∎

Combining these intermediate results, we show that the reduction from
undirected Force Path Cut to the directed version is linear, and the directed
version of the problem is also APX-hard.

###### Lemma A.11.

Force Path Cut is APX-hard for directed graphs, including the case where all
weights and all costs are equal.

###### Proof.

The function $f$ simply takes edges from an undirected graph and builds a
directed graph with the same (directed) edges, which takes $O(N+M)$ time. The
function $g$ takes a set of directed edges and converts it into a set of
undirected edges, which takes $O(M)$ time. By Lemma A.7, $g$ maps to a true
solution to the undirected Force Path Cut problem. This means that condition
(1) is satisfied.

Lemma A.10 guarantees that condition (2) is satisfied as well, with
$\alpha=1$. Finally, let $\mathcal{A}$ be an undirected instance of Force Path
Cut. For any solution $\hat{E}^{\prime}$ to $f(\mathcal{A})$, we know that

(30)
$\frac{1}{2}|\hat{E}^{\prime}|\leq|g(\hat{E}^{\prime})|\leq|\hat{E}^{\prime}|.$

Thus, we have

(31)
$\left||g(\hat{E}^{\prime})|-\mathrm{opt}(\mathcal{A})\right|\leq\left||\hat{E}^{\prime}|-\mathrm{opt}(\mathcal{A})\right|=\left||\hat{E}^{\prime}|-\mathrm{opt}(\mathcal{B})\right|,$

so condition (3) is satisfied with $\beta=1$.

Since all three conditions are satisfied, $f$ and $g$ provide a linear
reduction from Force Path Cut on an undirected graph to the same problem on a
directed graph. By Lemma A.1, Force Path Cut for undirected graphs is APX-
hard, so the reduction implies it is APX-hard for directed graphs as well. ∎

Theorem 3.1 is a direct consequence of Lemma A.1 and Lemma A.11.

##  Appendix B PATHATTACK Convergence

We consider the case where the ellipsoid algorithm is used to optimize the
relaxed version of the integer program. At each iteration, we consider the
center of an ellipsoid and determine whether this point violates any
constraints. Call this point $\Delta_{f}\in[0,1]^{M}$. In addition, let $P$ be
the current set of explicit path constraints and $P_{f}$ be the set of path
constraints—both implicit and explicit—that $\Delta_{f}$ does not violate.

Given $\Delta_{f}$, we perform the randomized rounding routine used in
Algorithm 2. With probability at least $1/2$, this procedure will yield a
result that is within the guaranteed approximation margin (i.e., the objective
of the integer solution is within $\ln{(4|P|)}$ of the fractional solution)
and satisfying all explicit constraints. Thus, with high probability, it will
yield such a solution in $O(\log{|E|})$ trials. Note that this holds for the
full set $P_{f}$ if $|P_{f}|\leq\frac{1}{4}e^{\lceil\ln{(4|P|)}\rceil}$, since
the two set sizes result in the same success bounds. If we attempt for
$O(\log{|E|})$ trials and never find a violated constraint, we increment the
number of Bernoulli random variables used in the randomized rounding procedure
and the approximation factor. With high probability, this will yield a valid
solution if $|P_{f}|\leq e^{\lceil\ln{(4|P|)}\rceil+1}$. We continue until we
find a path that needs to be cut that is not (fractionally) cut by the
solution of the relaxed problem. Algorithm 8 provides pseudocode for this
procedure. The algorithm will complete in polynomial time: There are at most
$N\ln{N}$ iterations of the outer loop, at most $\lceil\log_{2}{|E|}\rceil$
iterations of the second loop, inside of which:

  * •

At most $O(|E|N\log{N})$ Bernoulli random variables instantiated and
aggregated

  * •

An $O(|E|)$-length vector is created

  * •

Edges are removed from a graph (at most $O(|E|)$ time)

  * •

In the worst case, the _second_ shortest path is found, which takes $O(N^{3})$
time

  * •

The constraints are checked ($O(N)$ time).

Each item takes polynomial time to complete, so the overall algorithm takes
polynomial time.

Input: Graph $G=(V,E)$, weights $w$, costs $\mathbf{c}$, path $p^{*}$,
fractional cut vector $\Delta_{f}$, path set $P$

Output: Path $p$ that violates

$s\leftarrow$ first node of $p^{*}$;

$t\leftarrow$ last node of $p^{*}$;

$\mathrm{apxFactor}\leftarrow\lceil\ln{(4|P|)}\rceil$;

$\hat{\Delta}\leftarrow\mathbf{0}$;

$E^{\prime}\leftarrow\emptyset$;

not_cut$\leftarrow\mathbf{True}$;

while  _$(\mathrm{apxFactor} <N\ln{N})$ $\mathbf{and}$ $\mathrm{not\\_cut}$_
do

$\mathrm{ctr}\leftarrow 0$;

while  _$(\mathbf{c}^{\top}\Delta_{f}
>\mathbf{c}^{\top}\hat{\Delta}(4\cdot\mathrm{apxFactor})$ $\mathbf{or}$
$\mathrm{not\\_cut})$ $\mathbf{and}$ $\mathrm{ctr}<\lceil\log_{2}{|E|}\rceil$_
do

$E^{\prime}\leftarrow\emptyset$;

for  _$i\leftarrow 1$ to $\mathrm{apxFactor}$_ do

// randomly select edges based on $\Delta_{f}$

$E_{1}\leftarrow\\{e\in E\textrm{ with probability }\Delta_{f}[e]\\}$;

$E^{\prime}\leftarrow E^{\prime}\cup E_{1}$;

end for

$\hat{\Delta}\leftarrow$ indicator vector for $E^{\prime}$;

$G^{\prime}\leftarrow(V,E\setminus E^{\prime})$;

$p\leftarrow$ shortest path (other than $p^{*}$) from $s$ to $t$ in
$G^{\prime}$ with weights $w$;

if  _$\sum_{(u,v)\in p}{\Delta_{f}[u,v]}\geq 1$_ then

// $p$ does not violate $\Delta_{f}$

not_cut$\leftarrow$True;

else

not_cut$\leftarrow$False;

if  _$p$ is longer than $p^{*}$_ then

// found solution (if within approximation factor)

$p\leftarrow\emptyset$;

end if

end if

$\mathrm{ctr}\leftarrow\mathrm{ctr}+1$;

end while

$\mathrm{apxFactor}\leftarrow\mathrm{apxFactor}+1$

end while

return $p$

Algorithm 8 Randomized Rounding Oracle

##  Appendix C PATHATTACK for Node Removal

As discussed in Section 4.5, PATHATTACK can be used for node removal in
addition to edge removal. We refer to the associated problem as _Force Path
Remove_ : Given a weighted graph $G=(V,E)$, $w:E\rightarrow\mathbb{R}_{\geq
0}$, where each node has a cost of removal, $c:V\rightarrow\mathbb{R}_{\geq
0}$, a path $p^{*}$ from $s\in V$ to $t\in V$, and a budget $b$, is there a
subset of nodes $V^{\prime}\subset V$ such that $\sum_{v\in
V^{\prime}}{c(v)}\leq b$ and $p^{*}$ is the shortest path from $s$ to $t$ in
$G^{\prime}=(V\setminus V^{\prime},E\setminus E_{V^{\prime}})$, where
$E_{V^{\prime}}\subset E$ is the set of edges with at least one node in
$V^{\prime}$? In this section, we prove that this problem is also APX-hard,
and provide empirical results on the same datasets as shown in Section 6.

###  C.1. Computational Complexity

We propose the following reduction from Force Path Cut to Force Path Remove
for unweighted, undirected graphs:

  * •

Take the input graph $G=(V,E)$ and create its line graph
$\hat{G}=(\hat{V},\hat{E})$

  * •

Create new nodes $\hat{s}$ and $\hat{t}$ and add these to $\hat{V}$

  * •

For all edges $e\in E$ incident to $s$, create a new edge in $\hat{E}$
connecting $\hat{s}$ to the corresponding node $v_{e}\in\hat{V}$

  * •

For all edges $e\in E$ incident to $t$, create a new edge in $\hat{E}$
connecting $\hat{t}$ to the corresponding node $v_{e}\in\hat{V}$

  * •

Let $\hat{p}^{*}$ be the path from $\hat{s}$ to $\hat{t}$ where all
intermediate nodes are those that correspond to the edges in $p^{*}$, in the
same order

  * •

Solve Force Path Remove on $\hat{G}$ targeting $\hat{p}^{*}$.

This procedure is the function $f$ that maps an instance of Force Path Cut to
an instance of Force Path Remove. When we solve Force Path Remove, we obtain a
set of nodes $\hat{V}^{\prime}$ to remove. Since all nodes in $\hat{G}$ other
than $\hat{s}$ and $\hat{t}$ correspond to edges in $E$—and $\hat{s}$ and
$\hat{t}$ cannot be in $\hat{V}^{\prime}$—the function $g$ mapping a solution
to Force Path Remove to a solution to Force Path Cut is to make $E^{\prime}$
the set of edges in $E$ corresponding to the nodes in $\hat{V}^{\prime}$.

We first prove that the reduction yields a solution to Force Path Cut in the
following lemma.

###### Lemma C.1.

Let $\mathcal{A}$ be an unweighted, undirected instance of Force Path Cut and
$\hat{V}^{\prime}$ be a solution to $f(\mathcal{A})$. Then
$E^{\prime}=g(\hat{V}^{\prime})$ is a solution to $\mathcal{A}$.

###### Proof.

Suppose $E^{\prime}$ were not a solution to $\mathcal{A}$. This means that
$p^{*}$ is not the shortest path from $s$ to $t$ in $G^{\prime}=(V,E\setminus
E^{\prime})$. Let $p^{\prime}$ be the competing path. Since $p^{\prime}$
remains a path from $s$ to $t$, none of its edges are in $E^{\prime}$, and
therefore none of those edges’ corresponding nodes from $\hat{G}$ are in
$\hat{V}^{\prime}$. This means that all edges in $p^{\prime}$ have nodes in
$\hat{G}$. These nodes, however, form a path $\hat{p}^{\prime}$ from $\hat{s}$
to $\hat{t}$, and since the length of $p^{\prime}$ is less than or equal to
the length of $p^{*}$, $\hat{p}^{\prime}$ is also no longer than
$\hat{p}^{*}$, which contradicts the assumption that removing
$\hat{V}^{\prime}$ makes $\hat{p}^{*}$ the shortest path from $\hat{s}$ to
$\hat{t}$. ∎

In addition, the optimal solution to Force Path Cut is also the optimal
solution to the derived Force Path Remove instance.

###### Lemma C.2.

Let $\mathcal{A}$ be an instance of Force Path Cut. If $\hat{V}^{\prime}$ is
an optimal solution of $f(\mathcal{A})$, then $E^{\prime}=g(\hat{V}^{\prime})$
is an optimal solution of $\mathcal{A}$.

###### Proof.

Suppose there were a better solution $E_{1}\subset E$, $|E_{1}|<|E^{\prime}|$.
Consider the corresponding set of nodes $V_{1}\subset\hat{V}$. The augmented
line graph of $G_{1}=(V,E\setminus E_{1})$ would be the same as $\hat{G}$ with
$V_{1}$ (and all edges adjacent to nodes in $V_{1}$) removed. Since $p^{*}$ is
the shortest path from $s$ to $t$ in $G_{1}$, however, $\hat{p}^{*}$ would be
the shortest path from $\hat{s}$ to $\hat{t}$ in the augmented line graph.
This means that $V_{1}$ is a solution to $f(\mathcal{A})$. The fact that
$|E_{1}|<|E^{\prime}|$, however, implies that $|V_{1}|<|\hat{V}^{\prime}|$,
which contradicts the assumption that $\hat{V}^{\prime}$ is an optimal
solution, proving the claim. ∎

Using these results, we now prove APX-hardness in the undirected case.

###### Lemma C.3.

Force Path Remove is APX-hard for undirected graphs, including the case where
all costs are equal.

###### Proof.

To prove the claim, we show that the reduction described above satisfies the
requirements of a linear reduction: $f$ and $g$ can be computed in polynomial
time, the optimal solutions differ by at most a constant factor, and the
absolute difference of any solution from the optimal solution. We consider
each criterion in turn.

To create the line graph, a new graph is created with $|E|$ nodes. For each
node in the original graph, edges are created in the new graph connecting two
of the incident edges. Thus, for a node in $V$ with degree $d$, we have
$\binom{d}{2}$ edges in $\hat{E}$, meaning that $|\hat{E}|$ is $O(|E|^{2})$.
After creating the line graph, we add two new nodes and their associated
edges, which will be a total of $O(|V|)$. Overall, the new graph has $|E|+2$
nodes and $O(|E|^{2}+|V|)$ edges. Finally, to identify $\hat{p}^{*}$, we only
need to keep track of which nodes are associated with edges in $p^{*}$ in the
original graph, which requires $O(|V|)$ additional time to convert the node
labels. This means that $f$ can be computed in polynomial time. To compute
$g$, we only need to maintain a mapping of the edges in $G$ to the nodes in
$\hat{G}$, which will take $O(|E|)$ time to populate. Converting the solution
to Force Path Remove to a solution to Force Path Cut will take
$O(|V^{\prime}|)=O(|E|)$ lookups in the mapping. Thus, both $f$ and $g$ can be
computed in polynomial time.

By Lemma C.2, if $V^{\prime}$ is the optimal solution for $f(\mathcal{A})$,
then $g(V^{\prime})$ is the optimal solution for $\mathcal{A}$, which means
condition (2) is satisfied with $\alpha=1$. In addition, since the solutions
of the two problems are the same size—each node removed to solve
$f(\mathcal{A})$ corresponds with an edge removed to solve $\mathcal{A}$— we
have, for any proposed solution $x$ to $f(\mathcal{A})$,

(32)
$|\mathrm{cost}(x)-\mathrm{opt}(f(\mathcal{A}))|=|\mathrm{cost}(g(x))-\mathrm{opt}(\mathcal{A})|,$

satisfying condition (3) with $\beta=1$. Thus, all conditions of a linear
reduction are satisfied. Since Force Path Cut is APX-hard for unweighted,
undirected graphs (Lemma A.1), this implies that Force Path Remove is APX-hard
as well. ∎

We can trivially reduce from the undirected case to the directed case by
creating a directed edge set that includes edges in both directions for each
undirected edge in the original graph. Solving Force Path Remove on the
resulting directed graph yields the same solution as solving the Force Path
Remove on the original graph, thus corresponding solutions in the directed and
undirected cases are always equally costly. The formal proof of the following
lemma is straightforward, and we omit it for brevity.

###### Lemma C.4.

Force Path Remove is APX-hard for directed graphs, including the case where
all costs are equal.

The following theorem is a direct consequence of Lemmas C.3 and C.4.

###### Theorem C.5.

Force Path Remove is APX-hard, including the case where all costs are equal.

###  C.2. Experiments

We use the same experimental setup as in Section 6.3, in this case only
considering the 200th shortest path between the source and target. The
baseline method is analogous to the edge removal case: the lowest-cost node
along the shortest path is removed until $p^{*}$ is the shortest path. In all
cases, the cost of edge removal is the edge weight, while the cost of node
removal is degree. For node removal, we only consider values of $p^{*}$ that
have viable solutions (i.e., $p^{*}$ is the shortest path from $s$ to $t$ in
the subgraph induced on the nodes used by $p^{*}$).

Figure 10 shows results on unweighted graphs. We consider the equal-weighted
case, without random weights added, as this case highlights the greatest
difference between edge cuts and node removal. We did not consider cliques,
since there is never a viable solution when $p^{*}$ is more than one hop.
Results for edge removal are shown for comparison. There are a few substantial
differences between relative performance using edge removal and node removal.
For example, PATHATTACK provides a much more significant cost reduction with
node removal rather than edge removal for Erdős–Rényi graphs. In the vast
majority of these cases ($99/100$ for edge removal, $97/100$ for node
removal), randomized PATHATTACK finds the optimal solution. This suggests that
targeting the low-degree nodes—as the baseline does for node removal—is not an
effective strategy in this context, i.e., the increased cost of removing
higher-degree nodes pays off by removing more competing paths. Another major
difference is that the baseline outperforms PATHATTACK for lattices with equal
weights. In this case, while PATHATTACK finds the optimal solution with edge
removal in $94\%$ of cases, it is only optimal $20\%$ of the time with node
removal. Since degrees are equal, GreedyCost simply removes the first node
that deviates from $p^{*}$, which works well for unweighted lattices, while
the analogous strategy for edge removal is suboptimal. We see a similar
phenomenon with the autonomous system graph: the baseline method of removing
low-degree nodes yields a near-optimal solution, suggesting that focusing on
disrupting the intermediate low-degree nodes between the endpoints and the
hubs is a cost-effective strategy. While attacking high-degree nodes is useful
for disconnecting networks with skewed degree distributions (Albert et al.,
2000), the degree-based cost and focus on making a particular path shortest
make a different strategy ideal here.

Figure 10. Results on unweighted networks when PATHATTACK removes nodes rather
than edges. Results are shown where all edges have equal weight and removal
cost, in terms of attack cost (left column) and running time (right column).
Lower is better for both metrics. Bar heights are means across these trials
and error bars are standard errors. Results are shown for edge removal (top
row) as a comparison to the results for node removal (bottom row). For (D)ER
graphs, PATHATTACK yields much more substantial improvement with node removal
than edge removal, while for lattices PATHATTACK actually underperforms the
baseline. This demonstrates the variation in effectiveness of the baseline
(greedily removing low-degree nodes) over differences in topology.

Figure 11 illustrates results on real weighted graphs. Unlike the autonomous
system graph, here the power grid and road networks outperform the baseline
more significantly using node removal. Here, the diversity of edge weights
among the real graphs—and their contribution to path length—makes greedily
selecting low-cost edges a more effective heuristic than selecting low-degree
nodes.

Figure 11. Results on weighted networks when PATHATTACK removes nodes rather
than edges. Results are shown in terms of attack cost (left column) and
running time (right column). Lower is better for both metrics. Bar heights are
means across these trials and error bars are standard errors. Results are
shown for edge removal (top row) as a comparison to the results for node
removal (bottom row). Unlike the unweighted graphs, PATHATTACK outperforms the
baseline by a higher margin with node removal than with edge removal.

##  Appendix D Dataset Features

Our experiments were run on several synthetic and real networks across
different edge-weight distributions. All networks are undirected except DER,
WIKI, and LBL. We described the edge-weight distributions in Section 6 of the
paper. Table 1 provides summary statistics of the synthetic networks.

Networks | Nodes | Edges | $\langle k\rangle$ | $\sigma_{k}$ | $\kappa$ | $\tau$ | $\triangle$ | $\varphi$
---|---|---|---|---|---|---|---|---
ER | $16,000$ | $159,880$ | $19.985$ | $4.469$ | $0.001$ | $0.001$ | $1,326$ | $1$
| $\pm 0$ | $\pm 38$ | $\pm 0.05$ | $\pm 0.02$ | $\pm 0.0$ | $\pm 0.0$ | $\pm 39$ | $\pm 0$
DER | 16,000 | 319,901 | $39.988$ | $6.317$ | 0.001 | 0.001 | 10,639 | $1$
| $\pm 0$ | $\pm 568$ | $\pm 0.071$ | $\pm 0.034$ | $\pm 0.0$ | $\pm 0.0$ | $\pm 105$ | $\pm 0$
BA | $16,000$ | $159,900$ | $19.987$ | $24.475$ | $0.007$ | $0.006$ | $17,133$ | $1$
| $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0.3$ | $\pm 0.0$ | $\pm 0$ | $\pm 500$ | $\pm 0$
WS | 16,000 | 160,000 | 20 | 0.629 | 0.669 | 0.668 | 677682.42 | 1
| $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0.007$ | $\pm 0.001$ | $\pm 0.001$ | $\pm 818.171$ | $\pm 0$
KR | 16,337 | 159,595 |  19.537 |  16.537 |  $0.003$ | $0.005$ | $8,492$ |  $1.18$
| $\pm 22$ | $\pm 94$ | $\pm 0.02$ | $\pm 1.32$ | $\pm 0$ |  $\pm 0.002$ | $\pm 2,234$ |  $\pm 0.38$
LAT |  81,225 | $161,880$ | $3.985$ | $0.118$ | $0$ | $0$ | $0$ | $1$
| $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$
COMP | $565$ |  159,330 | $564$ | $0$ | $1$ | $1$ |  $29,900,930$ | $1$
| $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$ | $\pm 0$
Table 1. Properties of the synthetic networks used in our experiments. For
each random graph model, we generate 100 networks. Note that the number of
edges across the different networks is $\approx 160$K. The table shows the
average degree ($\langle k\rangle$), standard deviation of the degree
($\sigma_{k}$), average clustering coefficient ($\kappa$), transitivity
($\tau$), number of triangles ($\triangle$), and the number of components
($\varphi$). The $\pm$ values show the standard deviation across 100 runs of
each random graph model.

We ran experiments on both weighted and unweighted real networks. In cases of
unweighted networks, we added edge weights from the same distributions as the
synthetic networks. Below is a brief description of each network used. Table 2
summarizes the properties of each network.

The unweighted networks are:

  * •

Wikispeedia graph (WIKI): The network consists of Web pages (nodes) and
connections (edges) created from the user-generated paths in the Wikispeedia
game (West et al., 2009). Available at
https://snap.stanford.edu/data/wikispeedia.html.

  * •

Oregon autonomous system network (AS): Nodes represent autonomous systems of
routers and edges denote communication between the systems (Leskovec et al.,
2005). The dataset was collected at the University of Oregon on 31 March 2001.
Available at https://snap.stanford.edu/data/Oregon-1.html.

  * •

Pennsylvania road network (PA-ROAD): Nodes are intersections in Pennsylvania,
connected by edges representing roads (Leskovec et al., 2009). Available at
https://snap.stanford.edu/data/roadNet-PA.html.

Networks | Nodes | Edges | $\langle k\rangle$ | $\sigma_{k}$ | $\kappa$ | $\tau$ | $\triangle$ | $\varphi$
---|---|---|---|---|---|---|---|---
GRID | 347 | 444 | 2.559 | 1.967 | 0.086 | 0.087 | 40 | 1
LBL | 3,186 | 15,553 | 9.763 | 40.702 | 0.048 | 0.001 | 1821 | 10
WIKI | 4,592 | 119,882 | 52.213 | 78.601 | 0.195 | 0.158 | 550,545 | 2
AS | 10,670 | 22,002 | 4.124 | 31.986 | 0.296 | 0.009 | 17,144 | 1
PA-ROAD |  1,088,092 |  1,541,898 | 2.834 | 1.016 | 0.046 | 0.059 | 67,150 | 206
NEUS | 1,524,453 | 1,934,010 | 2.537 | 0.950 | 0.022 | 0.030 | 37,012 | 1
DBLP | 1,836,596 | 8,309,938 | 9.049 |  21.381 |  0.631 |  0.165 |  26,912,200 |  60,512
Table 2. Properties of the real networks used in our experiments. For each
network, we are listing the average degree ($\langle k\rangle$), standard
deviation of the degree ($\sigma_{k}$), average clustering coefficient
($\kappa$), transitivity ($\tau$), number of triangles ($\triangle$), and the
number of components ($\varphi$).

The weighted networks are:

  * •

Central Chilean Power Grid (GRID): Nodes represent power plants, substations,
taps, and junctions in the Chilean power grid. Edges represent transmission
lines, with distances in kilometers (Kim et al., 2018). The capacity of each
line in kilovolts is also provided. Available at
https://figshare.com/collections/An_in-
depth_network_structural_data_and_hourly_activity_on_the_Central_Chilean_power_grid/4053374.

  * •

Lawrence Berkeley National Laboratory network data (LBL): A graph of computer
network traffic, which includes counts of the number of connections between
machines over time. Counts are inverted for use as distances. Available at
https://www.icir.org/enterprise-tracing/download.html.

  * •

Northeast US Road Network (NEUS): Nodes are intersections in the northeastern
part of the United States, interconnected by roads (edges), with weights
corresponding to distance in kilometers. Available at
https://www.diag.uniroma1.it/c̃hallenge9/download.shtml.

  * •

DBLP coauthorship graph (DBLP): This is a co-authorship network (Benson et
al., 2018). We invert the number of co-authored papers to create a distance
(rather than similarity) between the associated authors. Available at
https://www.cs.cornell.edu/ãrb/data/coauth-DBLP/.