Некоторые случаи полиномиальной разрешимости задачи нахождения независимой $\{K_1,K_2\}$-упаковки наибольшего веса в графе

Пусть $\mathcal{H}$ — фиксированное множество связных графов. $\mathcal{H}$-упаковкой графа $G$ называется множество $\mathcal{S}=\{G_1,G_2,\ldots,G_m\}$ попарно не пересекающихся подграфов графа $G,$ каждый из которых изоморфен графу из $\mathcal{H}.$ Независимой $\mathcal{H}$-упаковкой графа $G$ называется $\mathcal{H}$-упаковка $S,$ в которой никакие два подграфа упаковки не соединены ребром графа $G.$ Если дан граф $G$ с весовыми функциями $\omega_V:~V(G)\to\mathbb{N}$ и $\omega_E:~E(G)\to\mathbb{N}$ на вершинах и ребрах и независимая $\{K_1,K_2\}$-упаковка $S$ графа $G,$ то весом $S$ называется $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ где $U=\bigcup_{G_i\in\mathcal{S},~G_i\cong K_1}V(G_i)$ и $F=\bigcup_{G_i\in\mathcal{S}}E(G_i).$ Рассматривается задача нахождения независимой $\{K_1,K_2\}$-упаковки наибольшего веса.
Пусть $C(G_1,\ldots ,G_{|V(C)|})$ обозначает граф, полученный из помеченного графа $C$ и непомеченных графов $G_1,\ldots ,G_{|V(C)|},$ заменой каждой вершины $v_i\in V(C)$ графом $G_i$ и соединением вершин $V(G_i)$ со всеми вершинами таких множеств $V(G_j),$ для которых $v_iv_j\in E(C).$ Для непомеченных графов $C,G_1,\ldots ,G_{|V(C)|},$ среди которых могут быть изоморфные, через $\Phi_C(G_1,\ldots ,G_{|V(C)|})$ обозначают класс всех графов $C(G_1,\ldots ,G_{|V(C)|}),$ когда берутся все возможные упорядочения вершин $V(C).$
Пусть $\mathcal{B,C}$ — классы простых графов такие, что $K_1\in \mathcal{B}\backslash \mathcal{C}.$ Простой рекурсивно-порождаемый класс $I(\mathcal{B,C})$ — это класс графов, который определяется индуктивно следующим образом: (1) все графы $\mathcal{B}$ принадлежат $I(\mathcal{B,C});$ (2) если $C\in \mathcal{C}$ и $\{G_1,\ldots ,G_{|V(C)|}\}\subseteq$ $\subseteq I(\mathcal{B,C}),$ то все графы $\Phi_C(G_1,\ldots ,G_{|V(C)|})$ принадлежат $I(\mathcal{B,C}).$
Представлен алгоритм, который решает задачу о взвешенной независимой $\{K_1,K_2\}$-упаковке графа в классе $I(\{K_1\}, \mathcal{G}_1\cup \mathcal{G}_2\cup \mathcal{G}_3\cup \mathcal{G}_4),$ где $\mathcal{G}_1$ — простые расщепляемые графы, $\mathcal{G}_2$ — простые деревья, $\mathcal{G}_3$ — простые унициклические графы, $\mathcal{G}_4$ — простые co-gem-свободные графы. Временная сложность алгоритма $O(n^2m),$ где $n=|V(G)|$ и $m=|E(G)|.$