The Steiner tree in K1,r-free split graphs-A Dichotomy

Given a connected graph G and a terminal set R subset of V(G), the Steiner tree problem (STREE) asks for a tree that includes all of R with at most r vertices from V(G) \ R, for some integer r >= 0. It is known from (Garey et al., 1977) that STREE is NP-complete in general graphs. A Split graph is a graph which can be partitioned into a clique and an independent set. White et al. (1985) have established that STREE in split graphs is NP-complete. In this paper, we present an interesting dichotomy: we show that STREE on K-1,K-4-free split graphs is polynomial-time solvable, whereas STREE on K-1,K-5-free split graphs is NP-complete. We investigate K-1,K-4-free and K-1,K-3-free (also known as claw-free) split graphs from a structural perspective. Further, using our structural study, we present polynomial-time algorithms for STREE in K-1,K-4-free and K-1,K-3-free split graphs. Although, polynomial-time solvability of K-1,K-3-free split graphs is implied from K-1,K-4-free split graphs, we wish to highlight our structural observations on K-1,K-3-free split graphs which may be of use in solving other combinatorial problems. (C) 2018 Elsevier B.V. All rights reserved.