Total domination and open packing in some subclasses of bipartite graphs

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.