Computing Weighted Strength and Applications to Partitioning
Jérôme Galtier · SIAM Journal on Discrete Mathematics · 2018
We study the mathematical concept of the strength of a graph as defined by Cunningham to partition very large graphs. The strength is the objective value of an attack problem on a graph where the striker aims at dividing the graph into a maximum number of connected components removing as few edges as possible per component uncoupled. The strength is the optimal number of edges per component uncoupled or, in the weighted version, the sum of the weights of the edges removed per component uncoupled. Given a connected graph with $n$ vertices and $m$ weighted edges, we denote by $W$ the total sum of the integer weights, and we describe an algorithm that approximates within a factor of $1+\varepsilon$ the weighted strength in time $O(m\log(W)\log^3(n)/\varepsilon^2)$, and that can be implemented with $O(m)$ memory use if we allow a complexity of $O(m\log^2(W)\log^3(n)/\varepsilon^2)$. This result has several important applications, in particular for the detection of dense areas of a graph, in terms of weighted edges, which in turn can be used for spam detection, community identification, and partitioning.