Algorithms for finding an independent $\{K_1,K_2\}$-packing of maximum weight in a graph

V. V. Lepin

Trudy Instituta matematiki, Tome 22 (2014) no. 1, pp. 78-97

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 algorithms to solve this problem for trees in time $O(n)$, for unicyclic graphs in time $O(n^2)$, and cographs and thin spider graphs in time $O(n+m)$, for co-gem-free graphs in time $O(m(m+n))$, where $n$ and $m$ are the number of vertices and edges in the graph. Moreover, we give a robust $O(m(m+n))$ time algorithm solving this problem for the graph class $\mathcal{T}\cup\mathcal{U}\cup\mathcal{G}_1\cup\mathcal{G}_2\cup\mathcal{G}_3$, where $\mathcal{T}$ — trees, $\mathcal{U}$ — unicycle, $\mathcal{G}_1$ — (bull,fork)-free, $\mathcal{G}_2$ — (co-P,fork)-free, $\mathcal{G}_3$ — ($P_5,$fork)-free graphs.