Approximation Hardness and Algorithms for Domination Problems on Chordal Bipartite Graphs

This paper advances the study of domination problems on generalized convex graphs, a hierarchical family of bipartite graphs defined via connectivity constraints with respect to a host graph. Building on our prior work that established the approximation hardness of five classical variants—domination, connected domination, total domination, paired domination, and independent domination—on star and comb convex graphs, we close several remaining gaps in the hierarchy. We prove that domination, connected domination, and independent domination remain hard to approximate on chordal bipartite graphs, completing the inapproximability landscape across major subclasses of generalized convex graphs. We also present constant-factor approximation algorithms for domination and connected domination on chordal bipartite graphs, all of which tightly match the APX-hardness of those problems. These results sharpen the approximability landscape within the generalized convex graph framework and clarify how the host graph structure influences the computational complexity of domination-type problems.