Steiner tree in k-star caterpillar convex bipartite graphs: a dichotomy

A bipartite graph G(X, Y) whose vertex set is partitioned into X and Y is a convex bipartite graph, if there is an ordering of \(X=(x_1,\ldots ,x_m)\) such that for all \(y \in Y\), \(N_G(y)\) is consecutive with respect to the ordering of X, and G is said to have convexity with respect to X. A k-star caterpillar is a tree with a collection of stars with each star having k vertices of degree one whose roots are joined by a path. For a bipartite graph with partitions X and Y, we associate a k-star caterpillar on X such that for each vertex in Y, its neighborhood induces a tree. The minimum Steiner tree problem (STREE) is defined as follows: given a connected graph \(G=(V,E)\) and a subset of vertices \(R \subseteq V(G)\), the objective is to find a minimum cardinality set \(S \subseteq V(G)\) such that the set \(R \cup S\) induces a connected subgraph. In this paper, we present the following dichotomy result: we show that STREE is NP-complete for 1-star caterpillar convex bipartite graphs and polynomial-time solvable for 0-star caterpillar convex bipartite graphs (also known as convex bipartite graphs). We also strengthen the well-known result of Müller and Brandstädt (Theoret Comput Sci 53(2-3):257-265, 1987), which says STREE in chordal bipartite graphs is NP-complete (reduction instances are 3-star caterpillar convex bipartite graphs). As an application, we use our STREE results to solve: (i) the classical dominating set problem in convex bipartite graphs, (ii) STREE on interval graphs, linear time.