A polynomial algorithm for weighted scattering number in interval graphs

The scattering number of a graph was introduced by Jung (1978) in relation to hamiltonian properties and network vulnerability, and it can also be regarded as the additive analogue of the toughness introduced by Chvátal. In this paper, we consider the problem of computing a generalized variant, namely the weighted scattering number. In general, computing the scattering number of a graph is NP-hard. Here we investigate the computational complexity of the weighted scattering number and give a polynomial time algorithm for computing this parameter when the input graph is an interval graph. Our results generalize the algorithm given by Broersma et al. (2015) which can only deal with the unweighted case, i.e., the special case when all the vertex weights are equal to 1.