Abstract:
The maximum weight $(\{ K_{1} ,K_{2} \} ,k,l)$-packing problem in graph is considered. This problem generalizes a number of well-known problems, for example: maximum induced matching, k-separated matching, connected matching, independent set, dissociating set, $k$-packing. Let $\Gamma $ be a class of graphs and $\Gamma^*$ the class of all atoms (with respect to the clique minimal separator decomposition) generated subgraphs from $\Gamma $. Proof that if the maximum weight $(\{ K_{1} ,K_{2} \} ,k,l)$-packing problem can be solve in the class of graphs $\Gamma^*$ in time $O(f_{atoms}(n)),$ then this problem can be solved in the class of graphs $\Gamma$ in time $O(n(n+m)\cdot f_{atoms}(n)).$