Решение взвешенной задачи о $k$-разделителе графа, имеющего особые модули

Если дан граф $G$ с весовой функцией $\omega:~V(G)\to\mathbb{R}^+,$ то весом подмножества вершин $U\subseteq V(G)$ называется $\omega(U)=\sum_{v\in U}\omega(v).$ Рассматривается задача нахождения наименьшего веса подмножества вершин $W$ такого, что каждая компонента $G-W$ имеет размер, не превосходящий $k.$ Представлен алгоритм, который решает эту задачу для графов обладающих особой модульной декомпозицией. Модулем графа $G$ называется множество вершин $M\subseteq V$ такое, что каждая вершина из $V\setminus M$ либо смежна со всеми вершинами из $M,$ либо ни с одной из них. Множество $V$ и каждое одновершинное множество называются тривиальными модулями. Если граф $G$ имеет только тривиальные модули, то он называется простым графом. Дан алгоритм, решающий эффективно взвешенную задачу о $k$-разделителе в классе графов, у которых все простые подграфы принадлежат множеству $\{P_4,\ldots,P_m\}\cup\{C_5,\ldots,C_m\}.$ Временная сложность алгоритма $O(n^2),$ где $n$ — число вершин графа. В классе кографов и последовательно-параллельных графов взвешенная задача о $k$-разделителе графа решается за линейное время.