In the $k$ red (blue) domination problem for a bipartite graph $G=(X,Y,E)$ we seek a subset $D \subseteq X$ (respectively $D \subseteq Y$) of cardinality at most $k$ that dominates vertices in $Y$ (respectively $X$). The decision version of this problem is $NP$-complete for perfect elimination bipartite graphs but solvable in polynomial time for chordal bipartite graphs. We present a linear time algorithm to solve the minimum cardinality red domination problem for convex bipartite graphs. The algorithm presented is faster and simpler than that in the literature. Due to the asymmetry in convex bipartite graphs, the algorithm does not extend to $k$ blue domination. We present a linear time algorithm to solve the minimum cardinality blue domination problem for convex bipartite graphs.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_3