We consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the star degree centrality (SDC) problem, has been shown to be 𝒩𝒫-complete. In this work, we first propose a new integer programming (IP) formulation, which has a fewer number of constraints and non-zero coefficients in them than the existing formulation in the literature. We present classes of networks where the problem is solvable in polynomial time and offer a new proof of 𝒩𝒫-completeness that shows the problem remains 𝒩𝒫-complete for both bipartite and split graphs. In addition,we propose a decomposition framework which is suitable for both the existing and our formulations. We implement several acceleration techniques in this framework, motivated by those techniques used in Benders decomposition. We test our approaches on networks generated based on the Barabási–Albert, Erdös–Rényi,and Watts–Strogatz models. Our decomposition approach outperforms solving the IP formulations in most of the instances in terms of both solution time and solution quality; this is especially true when the graph gets larger and denser. We then test the decomposition algorithm on large-scale protein-protein interaction networks, for which SDC was shown to be an important centrality metric.
Citation
Forthcoming in INFORMS Journal on Computing.