Solving the problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight on graphs with special blocks

V. V. Lepin

Trudy Instituta matematiki, Tome 23 (2015) no. 2, pp. 62-71

Résumé

Let $\mathcal{H}$ be a fixed set of connected graphs. A $\mathcal{H}$-packing of a given graph $G$ is a pairwise vertex-disjoint set of subgraphs of $G,$ each isomorphic to a member of $\mathcal{H}$. An independent $\mathcal{H}$-packing of a given graph $G$ is an $\mathcal{H}$-packing of $G$ in which no two subgraphs of the packing are joined by an edge of $G$. Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{N}$ and an edge weight function and $\omega_E:~E(G)\to\mathbb{N}$. Weight of an independent $\{K_1,K_2\}$-packing $S$ in $G$ is $\sum_{v\in U}\omega_V(v)+\sum_{e\in F}\omega_E(e),$ where $U=\bigcup_{G_i\in\mathcal{S},~G_i\cong K_1}V(G_i),$ and $F=\bigcup_{G_i\in\mathcal{S}}E(G_i)$. The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. We present an algorithm to solve this problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs include trees, block graphs, cacti and block-cactus graphs. The time complexity of the algorithm is $O(n^2m),$ where $n=|V(G)|$ and $m=|E(G)|$.