2026/05/28 by Jyothish S, Sadagopan Narasimhan · 1 voice
Computer Science · #cs.DM
paper · pdf · doi:10.48550/arxiv.2605.29540
Given a connected graph G and a terminal set R ⊆ V(G), the minimum Steiner tree problem (ST) asks for a tree that spans all of R with at most r vertices from V(G)\backslash R, for some integer r≥ 0. A split graph is a graph which can be partitioned into a clique and an independent set. It is known from (Garey et al.,1977) that ST is NP-complete, even for split graphs . We introduce the class of split-like graphs which unifies several known graph classes like bipartite graphs, split graphs, and bisplit graphs, allowing for a cohesive study across multiple structural constraints. We investigate the computational complexity of the Steiner tree problem under structural constraints, specifically K1,r-free, bounded diameter, chordality and star-convexity. Through reductions (primarily from Exact-3-Cover and its variants), the paper establishes a series of dichotomy results. It precisely gives the boundary for K1,r-free bipartite graphs: ST is in P for r ≤ 3 and NP-complete for r ≥ 4; whereas on K1,r-free bisplit graphs, ST is in P for any fixed r≥ 3. On bisplit graphs, the Steiner tree problem admits a polynomial-time solution when the diameter is 2. In contrast, for diameters 3 and 4, the problem is NP-complete. The problem is NP-complete under star convexity constraints on the independent set. When star convexity is imposed on the k-clique side, the problem is solvable in polynomial time. The problem is NP-complete on chordal bipartite graphs and chordal split graphs (i.e., split graphs themselves), while polynomial-time algorithms exist for other subclasses of split-like graphs.