A total dominating set in a graph G(V, E) is a vertex subset D such that every vertex in V is adjacent to some vertex in D. The cardinality of a minimum total dominating set in G is called the total domination number of G. Given a graph G and a positive integer \(k\le |V(G)|,\) the decision problem Total Dominating Set is to decide whether G has a total dominating set of size at most k. We prove that Total Dominating Set is NP-complete on (i) 2-degenerate planar perfect elimination bipartite graphs of maximum degree three (Class \(\mathcal {G}\) ), which improves a result by Garnero and Sau (Discr Math Theor Comput Sci 20:20, 2018. https://doi.org/10.23638/DMTCS-20-1-14), and (ii) the intersection class of star-convex, comb-convex, and perfect elimination bipartite graphs (Class \(\mathcal {H}\) ). Chlebík and Chlebíková (Inf Comput 206(11):1264–1275, 2008) proved that the total domination number cannot be approximated within a factor of \((1-\epsilon )\ln n\) for any \(\epsilon >0\) on bipartite graphs unless \(NP\subseteq Dtime(n^{O(\log \log n)})\) . We strengthen this result by showing that the approximation hardness bound holds for the class \(\mathcal {H}\) , a subclass of bipartite graphs. Also, we proved that Total Dominating Set parameterized by solution size is W[2]-complete on the class \(\mathcal {H}\) . On the positive side, we show that Total Dominating Set parameterized by maximum degree is fixed-parameter tractable in star-convex bipartite graphs. A vertex subset S is called an open packing in G if, for every distinct \(x',x''\in S\) , \(N_G(x')\cap N_G(x'')=\emptyset \) , where \(N_G(x)=\{y\in V(G):\, xy\in E(G)\}\) for every \(x\in V(G)\) . The cardinality of a maximum open packing in G is called the open packing number of G. Open packing and total domination is a pair of primal-dual graph problems and, for graphs without isolated vertices, the open packing number is a lower bound for the total domination number. The Open Packing problem takes a graph G and a positive integer k as inputs and checks whether G has an open packing of size at least k. It is known that Open Packing is NP-complete in bipartite graphs. Our work strengthens this result by showing that the problem remains NP-complete on (i) class \(\mathcal {G}\) and (ii) class \(\mathcal {H}\) . We further infer that on the graph class \(\mathcal {H}\) , (i) open packing number is hard to approximate within a factor of \(n^{\frac{1}{2}-\epsilon }\) for any \(\epsilon >0\) unless P = NP and (ii) Open Packing parameterized by solution size is W[1]-complete. Also, we show that Open Packing parameterized by maximum degree is fixed-parameter tractable in star convex bipartite graphs. In addition, we design polynomial time algorithms to find a maximum open packing in circular-convex bipartite graphs and triad-convex bipartite graphs.
