Vertex-edge domination on subclasses of bipartite graphs

Given a simple undirected graph $G=(V,E)$, the open neighbourhood of a vertex $v\in V$ is defined as $N_G(v)=\{u\in V\mid uv\in E\}$, and the closed neighbourhood as $N_G[v]=N_G(v)\cup \{v\}$. A subset $D\subseteq V$ is called a vertex-edge dominating set if, for every edge $uv\in E$, at least one vertex from $D$ appears in $N_G[u]\cup N_G[v]$; that is, $\mathrm{\mid }(N_G[u]\cup N_G[v])\cap D\mathrm{\mid }\ge 1$. Intuitively, a vertex-edge dominating set ensures that every edge, as well as all edges incident to either of its endpoints, is dominated by at least one vertex from the set. The $\text{textsc}Min-VEDS$ problem asks for a vertex-edge dominating set of minimum size in a given graph. This problem is known to be NP-complete even for bipartite graphs. In this paper, we strengthen this hardness result by proving that the problem remains NP-complete for two specific subclasses of bipartite graphs: star-convex and comb-convex bipartite graphs. For a graph $G$ on $n$ vertices, it is known that the $\text{textsc}Min-VEDS$ problem cannot be approximated within a factor of $(1-\epsilon )\ln \mathrm{\mid }V\mathrm{\mid }$ for any $\epsilon >0$, unless $\text{NP}\subseteq \text{DTIME}(\mathrm{\mid }V{\mathrm{\mid }}^{O(\log \log \mathrm{\mid }V\mathrm{\mid })})$. We also prove that this inapproximability result holds even for star-convex and comb-convex bipartite graphs. On the positive side, we present a polynomial-time algorithm for computing a minimum vertex-edge dominating set in convex bipartite graphs. A polynomial-time algorithm for this graph class was also proposed by B{ü}y{ü}k{ç}olak et al.~\cite{buyukccolak2025linear}, but we show that their algorithm has certain flaws by providing instances where it fails to produce an optimal solution. We address this issue by presenting a modified algorithm that correctly computes an optimal solution.