Finding the Maximum Subgraph of Prescribed Strength

The strength of a graph was introduced by Cunningham (1985) as the minimum ratio of the number of edges that could be removed from the graph to the number (minus one) of the connected components created by such a removal. The role of the strength of a graph as a connectivity and resilience measure is further highlighted by its connection to the spanning tree packing number of a graph, namely, the maximum number of edge‐disjoint spanning trees that can be contained in a graph. In this work, we investigate the question of determining a subset of a given graph's vertices of maximum cardinality that induces a subgraph of at least the prescribed strength. We show that the stated problem is polynomially solvable, and present the corresponding algorithm. In addition, we propose a mathematical programming‐based cutting plane method for computing graph strength, which can be integrated into larger mathematical programming models. Numerical experiments on a diverse array of real‐world graphs illustrate the computational properties of the proposed algorithms.