## 3 Problem Description  
The power system can be represented by an undirected, connected and node-weighted graph \(G=(V,E,W)\), where \(V\) is the set of \(n\) nodes, \(E\) is the edge set and \(W\) is the set containing the node weights. The node set \(V\) is composed of two mutually exclusive subsets \(V^{G}\) and \(V^{L}\), _i.e._, \(V=V^{G}\cup V^{L}\) and \(V^{G}\cap V_{L}=\emptyset\), where \(V^{G}\) is the set of \(m\) generator nodes and \(V^{L}\) includes the \(n\)-\(m\) load nodes. Let \(v_{i}\) (\(1\leq i\leq n\)) denote a node in \(V\) and \(v_{i}^{g}\) (\(1\leq i\leq m\)) be a generator node in \(V^{G}\). In a real situation, generators and loads may be situated at the same node. Thus, if the generation power exceeds the load power, we regard this node as a generator node; otherwise, it is a load node. The element \(e_{i,j}\) is included in \(E\) only if there is a transmission line between nodes \(i\) and \(j\). Each element \(e_{i,j}\in E\) is associated with a parameter \(\bar{P}_{i,j}\), which represents the capacity of the corresponding transmission line. Actually, the splitting strategy is a set of edges belonging to \(E\). If the node \(v_{i}\) is a generator node, then its corresponding \(w_{i}\) is a positive number; otherwise, \(w_{i}\) is negative. For convenience, we view the \(v_{i}\) that only acts as the connecting node without any power generation or consumption (_i.e._, \(w_{i}=0\)) as a load node. The power system islanding problem is a graph partitioning problem that has to abide by the following two types of constraints. The first constraint is called the connectivity constraint (CC) [24], which requires that any pair of nodes in each resultant island is linked by at least one path. The second constraint is the generator coherency constraint (GCC). The generators that have similar operating states are called coherent generators. The generator set \(V^{G}\) consists of \(u\) subsets of coherent generators, denoted by \(V^{G}_{k}\) (\(1\leq k\leq u\)). The power system must be split into \(u\) islands, where the generators in the same \(V^{G}_{k}\) can only exist in the same island. We denote the \(k\)-th (\(1\leq k\leq u\)) island by \(G_{k}=(V_{k},V^{G}_{k},E_{k},W_{k})\), where \(V_{k}\subseteq V\) is its node set, \(V^{G}_{k}\) is its associated set of coherent generators, \(E_{k}\subseteq E\) is the edge set and \(W_{k}\) contains the weights of the nodes in \(V_{k}\). Let \(P_{i,j}\) be the real active power on transmission line \(e_{i,j}\). The notational expression of the generator coherency constraint is given as follows:  
\[ \begin{cases}V^{G}_{k}\subseteq V_{k}\\ \cup_{k=1}^{u}V_{k}=V\\ \cup_{k=1}^{u}V^{G}_{k}=V^{G}\\ V^{G}_{k}\cap V^{G}_{l}=\emptyset,\ \forall\ k\
eq l\\ V_{k}\cap V_{l}=\emptyset,\ \forall\ k\
eq l\\ P_{i,j}\leq\bar{P}_{i,j}\end{cases}  \tag{1}\]  
When the system is partitioned after losing its stability, the imbalanced power will circulate between generators and loads within the isolated islands. If the imbalanced power is too large, cascading faults are very likely to occur within the islands. To resolve this issue, the load shedding and generator tripping measures must be performed, increasing the operational and social cost. Therefore, when splitting the power system, we aim to minimize the imbalance of the generation and load among all islands, lowering the needs of load shedding and generator tripping. The objective of the PSIP is to minimize the sum of the power imbalance of all resultant islands. The power imbalance of the \(k\)-th island is computed as:  
\[\Delta_{k}=|\sum_{v_{i}\in V_{k}}w_{i}| \tag{2}\]  
Thus, the objective value of the solution \(S\) is:  
\[C(S)=\min\ \sum_{k=1}^{u}\Delta_{k} \tag{3}\]In [7], the authors set a tolerance \(d>0\) on the power imbalance in each island and try to find feasible splitting strategies that satisfy \(\Delta_{k}<d\) for each \(1\leq k\leq u\). They proved that their problem is NP-complete. The PSIP can also be proven to be NP-complete in the same way.