Solving the problem of findingan independent $\{K_1,K_2\}$-packing of maximum weight in tree-cographs

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk

Abstract: 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_{H\in\mathcal{S},~H\cong K_1}V(H),$ and $F=\bigcup_{H\in\mathcal{S}}E(H).$ The problem of finding an independent $\{K_1,K_2\}$-packing of maximum weight is considered. We present a linear-time algorithm solving this problem for tree-cographs when the decomposition tree is a part of the input.

UDC: 519.1

Received: 30.10.2018