Алгоритмы для нахождения независимой $\{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\}$-упаковки наибольшего веса. Представлены алгоритмы, которые решают эту задачу для деревьев за время $O(n),$ для унициклических графов за время $O(n^2),$ для кографов и thin spider графов за время $O(n+m),$ для co-gem-свободных графов за время $O(m(m+n)),$ где $n$ — число вершин и $m$ — число ребер графа. Дан робастный $O(m(m+n))$ алгоритм, который решает эту задачу в классе $\mathcal{T}\cup \mathcal{U}\cup\mathcal{G}_1\cup\mathcal{G}_2\cup\mathcal{G}_3,$ где $\mathcal{T}$ — деревья, $\mathcal{U}$ — унициклические графы, $\mathcal{G}_1$ — (bull,fork)-свободные графы, $\mathcal{G}_2$ — (co-P,fork)-свободные графы, $\mathcal{G}_3$ — ($P_5,$fork)-свободные графы.