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

V. V. Lepin

Trudy Instituta matematiki, Tome 23 (2015) no. 1, pp. 98-114

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_{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 an algorithm to solve this problem for graphs that are given together with a tree decomposition $(\{X_i|i\in I\},T)$ in time $O(2^kmk),$ where $m=|I|$ and $k$ denotes the width of the tree decomposition. If $\omega_V(u)=0$ for all $u\in V(G),$ and $\omega_E(e)=1$ for all $e\in E(G)$ then an independent $\{K_1,K_2\}$-packing of maximum weight give an optimal solution the induced matching problem on graph $G.$ Our result improves the $O(4^km)$ algorithm of Moser and Sikdar for solution of the induced matching problem.