For comb-convex split graphs, STREE is NP-complete.


STREE is NP-Hard: It is known [1]} that VC on general graphs is NP-complete and this can be reduced in polynomial time to STREE on comb-convex split graphs using the following reduction. We map an instance \((G,k)\)  of VC on general graphs to the corresponding instance \((G^*,R,k^{\prime }=k)\)  of STREE as follows: \(V(G^*)=V_1\cup V_2\cup V_3\) ,
