A brief introduction to the CNDPs

The Critical Node Detection Problems (CNDPs) constitute one of the most extensively studied classes of combinatorial optimization problems. A central issue in CNDPs is the selection of an appropriate network connectivity metric, for which a wide range of alternatives has been proposed in the literature. According to the adopted metrics, CNDPs can be broadly categorized into two groups: fragmentation-based CNDPs and distance-based CNDPs. The PyCNP package currently supports two representative variants, namely the Critical Node Problem (CNP) and the Distance-based Critical Node Problem (DCNP), which belong to the fragmentation-based and distance-based categories, respectively.

Problem formulation

The Critical Node Problem (CNP) and its variants can be formally described as optimization problems on an undirected graph \(G = (V, E)\), where \(V\) is the set of nodes and \(E\) is the set of edges. The goal is to find a subset of nodes \(S \subseteq V\) to remove, such that a specific connectivity metric of the residual graph \(G[V \setminus S]\) is minimized, subject to a budget constraint.

Supported problem variants

Critical Node Problem (CNP)

The standard CNP seeks to identify a set of critical nodes \(S\) whose removal minimizes the pairwise connectivity of the residual graph. The pairwise connectivity metric calculates the total number of node pairs that remain connected by a path.

Formally, the CNP is defined as:

\[ \begin{align}\begin{aligned}\begin{split}\min_{S \subseteq V} \; \sum_{\substack{i,j \in V \setminus S \\ i < j}} w_{ij} \cdot x_{ij}\end{split}\\\text{s.t.} \qquad \sum_{i \in S} c_i \;\leq\; k\end{aligned}\end{align} \]

Where:

\(k\): Budget constraint (maximum cost of removed nodes).
\(w_{ij}\): Weight associated with the connection between nodes \(i\) and \(j\).
\(x_{ij}\): Binary variable, equal to 1 if a path exists between \(i\) and \(j\) in \(G[V \setminus S]\), and 0 otherwise.
\(c_i\): Cost of removing node \(i\).

PyCNP focuses on the unweighted case where \(c_i = 1\) and \(w_{ij} = 1\). In this context, the objective simplifies to minimizing the total number of connected node pairs in the residual graph.

Distance-based Critical Node Problem (DCNP)

The Distance-based CNP (DCNP) considers the actual pairwise distances between nodes rather than just their connectivity. The objective is to minimize a distance-based connectivity metric.

Formally, the DCNP is defined as:

\[ \begin{align}\begin{aligned}\begin{split}\min_{S \subseteq V} \; \sum_{\substack{i,j \in V \setminus S \\ i < j}} w_{ij} \cdot \phi(d_{ij})\end{split}\\\text{s.t.} \qquad \sum_{i \in S} c_i \;\leq\; k\end{aligned}\end{align} \]

Where:

\(d_{ij}\): Shortest path distance between \(i\) and \(j\) in the residual graph \(G[V \setminus S]\).
\(\phi(d_{ij})\): Distance-based connectivity measure, defined as:

\[\begin{split}\phi(d_{ij}) = \begin{cases} 1, & \text{if } d_{ij} < b, \\ 0, & \text{otherwise}. \end{cases}\end{split}\]

\(b\): Predefined hop distance limit. Two nodes are considered “connected” only if their distance is strictly less than \(b\).

Notably, when \(b \geq |V|\), the DCNP reduces to the standard CNP.

Hint

Check out the quick tutorial for step-by-step examples of solving CNP and DCNP instances.