Solving the weighted $k$-separator problem in graphs with specific modules

V. V. Lepin

Trudy Instituta matematiki, Tome 24 (2016) no. 1, pp. 61-74

Résumé

Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{R}^+$ 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.$ Using the notion of modular decomposition we extend the class of graphs on which this problem can be solved in polynomial time. For a graph $G$ that is modular decomposable into $\pi(G)\subseteq\{P_4,\ldots,P_m\}\cup\{C_5,\ldots,C_m\}$ we give an $O(n^2)$ algorithm for finding the minimum weight of $k$-separators. The algorithm solves this problem for cographs in time $O(n).$ Moreover, we give an $O(n)$ time algorithm solving this problem for the series-parallel graphs.