Аннотация:
Рассматривается задача о $(\{K_{1},K_{2}\},k,l)$-упаковке наибольшего веса в графе, которая обобщает ряд известных задач, например: о независимом множестве; о максимальном индуцированном паросочетании; о $k$-разделенном паросочетании; о связном паросочетании; о диссоциирующем множестве; о $k$-упаковке. Пусть $\Gamma$ – класс графов и $\Gamma^*$ – класс всех порожденных подграфов из $\Gamma$ являющимися атомами относительно декомпозиции по минимальным кликовым разделителям. Доказано, что если задача об оптимальной $(\{ K_{1} ,K_{2} \} ,k,l)$-упаковке графа может быть решена в классе графов $\Gamma^*$ за время $O(f_{atoms}(n)),$ то эта задача может быть решена в классе графов $\Gamma$ за время $O(n(n+m)\cdot f_{atoms}(n)).$