STREE is NP-Hard: It is known [1]} that X3C is NP-complete. X3C can be reduced in polynomial time to STREE on star-convex split graphs using the following reduction. We map an instance \((X,\mathcal {C})\)  of X3C to the corresponding instance \((G,R,k)\)  of STREE as follows: \(V(G)=V_1\cup V_2\) , \(V_1=\lbrace c_i\mid 1\le i \le m\rbrace \) , \(V_2=\lbrace x_1,x_2,\ldots ,x_{3q},x_{3q+1}\rbrace \) , \(E(G)=\lbrace \lbrace c_i,x_j\rbrace \mid x_j\in C_i, 1\le j\le 3q, 1\le i \le m\rbrace  \cup \lbrace \lbrace x_{3q+1},c_i\rbrace \mid 1\le i \le m\rbrace  \cup \lbrace \lbrace c_i,c_j\rbrace \mid 1\le i\le j \le m\rbrace \) . Let \(R=V_2\) , \(k=q\) . Note that \(G\)  is a split graph with \(V_1\)  being a clique and \(V_2\)  being an independent set. Now we show that \(G\)  is a star-convex split graph by defining an imaginary star \(T\)  on \(V_2\) :
