A New Lower Bound on the Size of the Smallest Vertex Separator of a Graph
Yongyan Guo, Gang Wu · SIAM Journal on Matrix Analysis and Applications · 2022
Separator minimization is an important problem in graph partitioning. Although finding an optimum partitioning for a given graph is NP-hard, estimating the size of the smallest vertex separator is an interesting problem since it can be used to assess the quality of a vertex separator. In [A. Pothen, H. Simon, and K. Liou, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 430--452], two classical lower bounds on the size of the smallest vertex separator of a graph were established. In the present work, we revisit this problem and establish a new and easily computable lower bound on the smallest vertex separator.