The k-separator problem: polyhedra, complexity and approximation results

Given a vertex-weighted undirected graph G=(V,E,w) and a positive integer k, we consider the k-separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to k. We show that this problem can be solved in polynomial time for some graph classes including bounded treewidth, mK2-free, (G1,G2,G3,P6)-free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Polyhedral results with respect to the convex hull of the incidence vectors of k-separators are reported. Approximation algorithms are also presented.