The frustration index of a signed graph \(\Large (G,\sigma)\), denoted by \(\Large F(G,\sigma)\), is the minimum number of edges whose removal makes \(\Large (G,\sigma)\) a balanced signed graph.
The definition generalizes the Max-Cut problem. If \(\Large (G,-)\) denotes the signed graph in which every edge is negative, then
$$ \Large F(G,-)=|E(G)|-\operatorname{MaxCut}(G). $$
Indeed, a balanced subgraph of \(\Large (G,-)\) is precisely a bipartite subgraph, so maximizing the number of edges that remain after deletion is equivalent to finding a maximum cut.
It is therefore NP-hard to compute the frustration index of an input signed graph. However, efficient algorithms can be developed when the input is restricted to specific families of signed graphs.
Using the characterization of balanced signed graphs in terms of the signs of their cycles, one observes that \(\Large F(G,\sigma)\) is the minimum number of edges whose removal leaves no negative cycle.
There is, in fact, a somewhat deeper relation as follows.
A subset \(\Large E'\) of the edges of \(\Large (G,\sigma)\) is called a negative cycle cover if \(\Large (G-E',\sigma')\), where \(\Large \sigma'\) is the restriction of \(\Large \sigma\) to \(\Large E(G)\setminus E'\), has no negative cycle. In other words, \(\Large E'\) contains at least one edge from every negative cycle.
A simple example of a negative cycle cover is the set of all negative edges, or the set of all negative edges after switching at some vertices. Not every negative cycle cover is necessarily the set of negative edges of an equivalent signature, though. However, there is a 1-1 correspondence between minimal negative cycle covers and inclusion-minimal signatures.
A negative cycle cover is minimal if no proper subset of it is a negative cycle cover. A signature \(\Large \sigma\) of a graph \(\Large G\) is inclusion-minimal if no switching-equivalent signature has a proper subset of its negative-edge set.
Theorem. The minimal negative cycle covers of a signed graph \(\Large (G,\sigma)\) are exactly the negative-edge sets of inclusion-minimal signatures.
Proof. Let \(\Large E^\sigma\) denote the set of negative edges of an inclusion-minimal signature \(\Large \sigma\). Since every negative cycle contains an odd number of negative edges, in particular a nonzero number of them, \(\Large E^\sigma\) is a negative cycle cover.
Suppose that \(\Large E' \subsetneq E^\sigma\) were also a negative cycle cover. Then \(\Large (G-E',\sigma)\) is balanced. Hence there is a switching-equivalent signature \(\Large \sigma'\) in which all edges of \(\Large G-E'\) are positive. Therefore
$$ \Large E^{\sigma'}\subseteq E'\subsetneq E^\sigma, $$
contradicting the inclusion-minimality of \(\Large \sigma\). Thus \(\Large E^\sigma\) is a minimal negative cycle cover.
Conversely, let \(\Large E'\) be a minimal negative cycle cover. Since \(\Large (G-E',\sigma)\) is balanced, there is a switching-equivalent signature \(\Large \sigma'\) in which every edge of \(\Large G-E'\) is positive. Hence
$$ \Large E^{\sigma'}\subseteq E'. $$
Since \(\Large E^{\sigma'}\) is itself a negative cycle cover, the minimality of \(\Large E'\) implies
$$ \Large E^{\sigma'}=E'. $$
Finally, suppose that \(\Large \sigma'\) were not inclusion-minimal. Then some switching-equivalent signature \(\Large \tau\) would satisfy
$$ \Large E^\tau\subsetneq E^{\sigma'}=E'. $$
But \(\Large E^\tau\) is a negative cycle cover, contradicting the minimality of \(\Large E'\). Thus \(\Large \sigma'\) is an inclusion-minimal signature.
Historical notes
Abelson-Rosenberg (1958) developed a formal mathematical model of positive and negative relations and introduced the notion of a cost of changing relations, leading to their measure of imbalance which they called complexity.
Harary, who had earlier introduced the terminology of signed graphs and balance in Harary (1953), introduced the same parameter under the name line index in Harary (1959). This is perhaps why, in much of the literature, the parameter is denoted by \(\Large \ell(G,\sigma)\).
Without using the term signed graph, Toulouse (1977) introduced the frustration model for spin glasses.
A bit of physics: in an Ising spin system, each site carries a two-state spin \(\Large s_i\in\{+1,-1\}\), and neighboring spins interact through positive or negative couplings. In a crystal, the interactions are sufficiently ordered and compatible that the spins can settle into a regular configuration satisfying all interactions. In a glass, by contrast, the interactions are disordered and competing, so satisfying one interaction may prevent another from being satisfied. Frustration occurs when these interactions cannot all be simultaneously satisfied; consequently, the ground state is obtained by minimizing the total energy rather than satisfying every interaction.
Connection to matching theory was studied in Bieche-Maynard-Rammal-Uhry (1980). Connecting frustration in spin glasses to the line index in signed graphs, Zaslavsky (1987) introduced the term frustration index.
Remarks
Frustration index is the most studied measure of how far a signed graph is from being balanced. But it is far from being the only one. Among others, the degree of balance introduced in Cartwright-Harary (1956) dates to the same period as the frustration index. It considers the proportion of balanced cycles among all cycles.
For a modern reference on the frustration index, with emphasis on the computational aspects, see Aref-Mason-Wilson (2020). For a recent reference on the theoretical aspects, see Cappello-Naserasr-Steffen-Wang (2025).
A notion that further generalizes the concept is Correlation Clustering.
References
Abelson-Rosenberg (1958) Abelson, Robert P. & Rosenberg, Milton J. (1958). Symbolic psycho-logic: A model of attitudinal cognition. Behavioral Science, 3(1), 113. DOI.
Harary (1953) Harary, Frank (1953). On the Notion of Balance of a Signed Graph. Michigan Mathematical Journal, 2(2), 143146. DOI.
Harary (1959) Harary, Frank (1959). On the Measurement of Structural Balance. Behavioral Science, 4(4), 316323. DOI.
Toulouse (1977) Toulouse, G้rard (1977). Theory of the frustration effect in spin glasses. I. Communications on Physics, 2(4), 115119. DOI.
Bieche-Maynard-Rammal-Uhry (1980) Bieche, Isabelle, Maynard, Roger, Rammal, R้mi & Uhry, Jean-Pierre (1980). On the ground states of the frustration model of a spin glass by a matching method of graph theory. Journal of Physics A: Mathematical and General, 13(8), 25532576. DOI.
Zaslavsky (1987) Zaslavsky, Thomas (1987). Balanced decompositions of a signed graph. Journal of Combinatorial Theory, Series B, 43(1), 113. DOI.
Cartwright-Harary (1956) Cartwright, Dorwin & Harary, Frank (1956). Structural balance: A generalization of Heider's theory. Psychological Review, 63(5), 277293. DOI.
Aref-Mason-Wilson (2020) Aref, Samin, Mason, Andrew J. & Wilson, Mark C. (2020). A modeling and computational study of the frustration index in signed networks. Networks, 75(1), 95110. DOI.
Cappello-Naserasr-Steffen-Wang (2025) Cappello, Chiara, Naserasr, Reza, Steffen, Eckhard & Wang, Zhouningxin (2025). Critically 3-frustrated signed graphs. Discrete Mathematics, 348(1), Paper No. 114258. DOI.