11institutetext: Indian Institute of Information Technology, Design and
Manufacturing, Kancheepuram, Chennai. 22institutetext: National Institute of
Technology, Calicut
22email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
# On Convexity in Split graphs: Complexity of Steiner tree and Domination
††thanks: This work is partially supported by the DST-ECRA Project—
ECR/2017/001442.111A preliminary version of this paper appeared in the
proceedings of $8^{th}$ International conference, CALDAM 2022, Lecture Notes
in Computer Science, vol. 13179, pp. 128-139, 2022

A Mohanapriya 11 P Renjith 22 N Sadagopan 11

###### Abstract

Given a graph $G$ with a terminal set $R\subseteq V(G)$, the Steiner tree
problem (STREE) asks for a set $S\subseteq V(G)\setminus R$ such that the
graph induced on $S\cup R$ is connected. A split graph is a graph which can be
partitioned into a clique and an independent set. It is known that STREE is
NP-complete on split graphs [1]. To strengthen this result, we introduce
convex ordering on one of the partitions (clique or independent set), and
prove that STREE is polynomial-time solvable for tree-convex split graphs with
convexity on clique ($K$), whereas STREE is NP-complete on tree-convex split
graphs with convexity on independent set ($I$). We further strengthen our NP-
complete result by establishing a dichotomy which says that for unary-tree-
convex split graphs (path-convex split graphs), STREE is polynomial-time
solvable, and NP-complete for binary-tree-convex split graphs (comb-convex
split graphs). We also show that STREE is polynomial-time solvable for triad-
convex split graphs with convexity on $I$, and circular-convex split graphs.
Further, we show that STREE can be used as a framework for the dominating set
problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of
STREE and DS is the same for all these subclasses of split graphs.
Furthermore, it is important to highlight that in [2], it is incorrectly
claimed that the problem of finding a minimum dominating set on split graphs
cannot be approximated within $(1-\epsilon)\ln|V(G)|$ in polynomial-time for
any $\epsilon>0$ unless NP $\subseteq$ DTIME $n^{O(\log\log n)}$. When the
input is restricted to split graphs, we show that the minimum dominating set
problem has $2-\frac{1}{|I|}$-approximation algorithm that runs in polynomial
time. Finally, from the parameterized perspective with solution size being the
parameter, we show that the Steiner tree problem on split graphs is
$W[2]$-hard, whereas when the parameter is treewidth and the solution size, we
show that the problem is fixed-parameter tractable, and if the parameter is
the solution size and the maximum degree of $I$ ($d$), then we show that the
Steiner tree problem on split graphs has a kernel of size at most
$(2d-1)k^{d-1}+k,~{}k=|S|$.
Keywords: Steiner tree, Domination, Split graphs, Tree-convex, Circular-convex
split graphs, Approximation algorithms, Parameterized complexity.

##  1 Introduction

The classical complexity of the Steiner tree problem (STREE), the dominating
set problem (DS), and their variants for different classes of graphs have been
well studied. Given a graph $G$ with a terminal set $R\subseteq V(G)$, STREE
asks for a set $S\subseteq V(G)\setminus R$ such that the graph induced on
$S\cup R$ is connected. In the literature, the set $S$ is referred to as the
Steiner set. The objective is to minimize the number of vertices in $S$. STREE
is NP-complete for general graphs, chordal bipartite graphs [3], and split
graphs [1] whose vertex set can be partitioned into a clique and an
independent set. It is polynomial-time solvable in strongly chordal graphs
[1], series-parallel graphs [4], outerplanar graphs [5], interval graphs [6]
and for graphs with fixed treewidth [7]. The only known subclass of split
graphs where STREE is polynomial-time solvable is the class of threshold
graphs. Interestingly the results of [8] strengthen the result of [1] by
providing a dichotomy result which says that STREE is polynomial-time solvable
in $K_{1,4}$-free split graphs, whereas in $K_{1,5}$-free split graphs, STREE
is NP-complete. In this paper, we focus on new subclasses of split graphs and
study the tractability versus intractability status (P vs NPC) of STREE in
those subclasses of split graphs.
It is important to highlight that many problems that are NP-complete on
bipartite graphs become polynomial-time solvable when a linear ordering is
imposed on one of the partitions. Such graphs are known as convex bipartite
graphs in the literature [9, 10, 11]. For example, DS is NP-complete on
bipartite graphs, whereas it is polynomial-time solvable in convex bipartite
graphs [9]. A bipartite graph $G=(X,Y)$ is said to be tree-convex if there is
a tree (imaginary tree) on $X$ such that the neighborhood of each $y$ in $Y$
is a subtree in $X$. Apart from linear ordering (path-convex ordering), tree-
convex ordering, comb-convex ordering, star-convex ordering, triad-convex
ordering, and circular-convex ordering on bipartite graphs have been
considered in the literature [12, 13, 14]. Further, the convex ordering on
bipartite graphs yielded many interesting algorithmic results for STREE, DS,
Hamiltonicity, and its variants [6, 12, 11]. Similarly, the feedback vertex
set problem (FVS) is NP-complete on star-convex bipartite graphs, and comb-
convex bipartite graphs, whereas it is polynomial-time solvable on convex
bipartite graphs [11]. Thus, the convex ordering on bipartite graphs
reinforces the borderline separating P-versus-NPC instances of many classical
combinatorial problems.
Imposing the property convexity on bipartite graphs is a promising direction
for further research because many problems that are NP-complete on bipartite
graphs become polynomial-time solvable on convex bipartite graphs. Further,
some of the NP-hard reductions restricted to bipartite graphs can be
reinforced further by introducing convex properties such as star, comb, tree,
etc., For example, Hamiltonian cycle and Hamiltonian path are NP-hard on star-
convex bipartite graphs [11]. While convexity in bipartite graphs seems to be
a promising direction in strengthening the existing classical hardness result
or in discovering a polynomial-time algorithm, we wish to investigate this
line of research for STREE and DS problems restricted to split graphs.
Since the tractability versus intractability status of many combinatorial
problems on bipartite graphs (graphs with two partitions satisfying some
structural properties) can be investigated with the help of convex ordering on
bipartite graphs, it is natural to explore this line of study on graphs having
two partitions satisfying some structural properties. A natural choice after
bipartite graphs is the class of split graphs. We wish to extend this line of
study to split graphs by considering convex ordering with respect to the
clique part and independent set part. To the best of our knowledge, this paper
makes the first attempt in introducing convex properties on split graphs for
STREE and DS. We believe that our results shall strengthen the result of [1],
and also we discover a dichotomy similar to [8]. As part of this paper, we
consider the following convex properties; path-convex, star-convex, comb-
convex, tree-convex, and circular-convex split graphs. Henceforth, we refer to
split graphs satisfying some convex properties (path, star, comb, triad, tree,
and circular) as convex split graphs.
Recently in [6], a framework for STREE and DS was developed, and as per [8],
the classical complexity of STREE is the same as the classical complexity of
DS for split graphs. We attempt a similar framework for STREE and DS, and its
variants are restricted to convex split graphs.
For tree-convex and its subclasses, and circular-convex split graphs, the
computational complexity of the following graph problems is studied in this
paper.

  1. 1.

The Steiner tree problem (STREE).
_Instance:_ A graph $G$, a terminal set $R\subseteq V(G)$, and a positive
integer $k$.
_Question:_ Does there exist a set $S\subseteq V(G)\setminus R$ such that
$|S|\leq k$, and $G[S\cup R]$ is connected ?

  2. 2.

The Dominating set problem (DS).
_Instance:_ A graph $G$, and a positive integer $k$.
_Question:_ Does $G$ admit a dominating set of size at most $k$ ?

  3. 3.

The Connected Dominating set problem (CDS).
_Instance:_ A graph $G$, and a positive integer $k$.
_Question:_ Does $G$ admit a connected dominating set of size at most $k$ ?

  4. 4.

The Total Dominating set problem (TDS).
_Instance:_ A graph $G$, and a positive integer $k$.
_Question:_ Does $G$ admit a total dominating set of size at most $k$ ?

Figure 1: The Hierarchical relationship among subclasses of convex split
graphs

Figure 1 illustrates the hierarchical relationship on various convex split
graphs. An interesting theoretical question is

_-What is the boundary between the tractability and intractability of STREE in
split graphs when convex ordering is imposed on one of the partitions ?_

In this paper, we answer this question by imposing a convex ordering on clique
or independent set. In particular, we show that STREE is polynomial-time
solvable for tree-convex split graphs with convexity on $K$, and is NP-
complete for star-convex and comb-convex split graphs, and thus for tree-
convex split graphs with convexity on $I$. Further, we investigate path,
triad, and circular-convex properties, and show that STREE is polynomial-time
solvable for triad, path-convex split graphs with convexity on $I$, circular-
convex split graphs with convexity on $I$, and circular-convex split graphs
with convexity on $K$. We then ask

_-For which convex property on split graphs with convexity on $K$, STREE is
intractable?_

In this paper, we show that if the convex property is chordality, then STREE
is NP-complete for chordal-convex split graphs with convexity on $K$.

To deal with computationally intractable problems, the practical approach is
to use approximation algorithms or parameterized algorithms. Algorithms that
output near-optimal solutions in polynomial time are precisely the class of
approximation algorithms. It is known [15], that DS has an approximation
algorithm with approximation ratio $(1+\ln n)$ on general graphs. On the
negative side, DS does not admit $(1-\epsilon)\ln n$ on general graphs, for
any $\epsilon>0$ unless NP $\subseteq$ DTIME ($n^{O(\log\log n)}$) [2]. In
this paper, restricted to split graphs, we prove that DS exhibits
$2-\frac{1}{|I|}$-approximation algorithm.
For decision problems with input size $n$, and a parameter $k$ (which can be a
tuple of parameters), the goal of parameterized algorithms is to obtain an
algorithm with runtime $f(k)n^{O(1)}$, where $f$ is a function of $k$ and
independent of $n$. Problems having such algorithms are Fixed-Parameter
Tractable (FPT). There is a hierarchy of intractable parameterized problem
classes above FPT [16], they are:

$\mbox{FPT}\subseteq\mbox{M[1]}\subseteq\mbox{W[1]}\subseteq\mbox{M[2]}\subseteq\mbox{W[2]}\subseteq\ldots\subseteq\mbox{W[P]}\subseteq\mbox{XP}.$

In [17] it is shown that STREE in general graphs is in FPT if the parameter is
the size of the terminal set. It is known [18] that STREE in general graphs
with parameter $|S|$ (solution size) is W[2]-hard. We strengthen the result of
[18] by proving that the Steiner tree problem on split graphs is still
W[2]-hard with the parameter being the solution size. Further, the
parameterized Steiner tree problem is in FPT, when parameters are
(i) the solution size and the treewidth,
(ii) the solution size and the maximum degree of $I$.
We reiterate that our FPT results for STREE are true for DS as well,
restricted to split graphs.

This paper is structured as follows: In Section 2, we analyze the classical
complexity of STREE on convex split graphs and present dichotomy results for
convex split graphs with convexity on $I$ as well as for convex split graphs
with convexity on $K$. We also identify polynomial-time solvable instances and
FPT instances of STREE on star-convex split graphs with convexity on $I$ which
we present in Section 2.1.1, and we also prove that the Steiner tree problem
with the parameter being solution size and backbone path length on comb-convex
split graphs is in XP in Section 2.1.2. We then present results on the
dominating set problem and its variants on convex split graphs in Section 3.
In Section 4, we present parameterized hardness of STREE on split graphs, and
we also identified parameters for which parameterized version of STREE on
split graphs becomes fixed-parameter tractable. Further, we present
$2-\frac{1}{I}$-approximation algorithm for domination on split graphs in
Section 5.

Graph preliminaries: In this paper, we consider connected, undirected,
unweighted, and simple graphs. For a graph $G$, $V(G)$ denotes the vertex set,
and $E(G)$ represents the edge set. For a set $S\subseteq V(G)$, $G[S]$
denotes the subgraph of $G$ induced on the vertex set $S$. The open
neighborhood of a vertex $v$ in $G$ is $N_{G}(v)=\\{u~{}|~{}\\{u,v\\}\in
E(G)\\}$ and the closed neighborhood of $v$ in $G$ is $N_{G}[v]=\\{v\\}\cup
N_{G}(v)$. The degree of vertex $v$ in $G$ is $d_{G}(v)=|N_{G}(v)|$. A split
graph $G$ is a graph in which $V(G)$ is partitioned into two sets; a clique
$K$ and an independent set $I$. In a split graph, for each vertex $u$ in $K$,
$N^{I}_{G}(u)=N_{G}(u)\cap I$, $d^{I}_{G}(u)=|N^{I}_{G}(u)|$, and for each
vertex $v$ in $I$, $N^{K}_{G}(v)=N_{G}(v)\cap K$,
$d^{K}_{G}(v)=|N^{K}_{G}(v)|$. For each vertex $u$ in $K$,
$N^{I}_{G}[u]=(N_{G}(u)\cap I)\cup\\{u\\}$, and for each vertex $v$ in $I$,
$N^{K}_{G}[v]=(N_{G}(v)\cap K)\cup\\{v\\}$. For a split graph $G$,
$\Delta^{I}_{G}=\mbox{max}\\{d^{I}_{G}(u)\\},u\in K$ and
$\Delta^{K}_{G}=\mbox{max}\\{d^{K}_{G}(v)\\},v\in I$. For a set $S$, $G-S$
denotes the graph induced on $V(G)\setminus S$. For
$A=\\{x_{1},\ldots,x_{p}\\}$, $\max(x_{1},\ldots,x_{p})$ is $x_{p}$; the
vertex having largest index.
A tree is a connected acyclic graph. A path is a tree $T$ with
$V(T)=\\{v_{1},\ldots,v_{n}\\},~{}n\geq 1$ and
$E(T)=\\{\\{v_{i},v_{i+1},~{}1\leq i\leq n-1\\}\\}$. A cycle is a graph $C$
with $V(C)=\\{v_{1},\ldots,v_{n}\\},~{}n\geq 3$ and
$E(C)=\\{\\{v_{i},v_{i+1},~{}1\leq i\leq
n-1\\}\\}\cup\\{\\{v_{n},v_{1}\\}\\}$. We consider three special kinds of
trees, namely, star, comb, and triad. A star is a tree $T$ with
$V(T)=\\{v_{1},\ldots,v_{n}\\},~{}n\geq 2$ and $E(T)=\\{\\{v_{1},v_{i}\\}\mid
2\leq i\leq n\\}$. The root of $T$ is $v_{1}$ and $v_{2},\ldots,v_{n}$ are the
pendant vertices in $T$. A comb is a tree $T$ with
$V(T)=\\{v_{1},\ldots,v_{2n}\\}$ and $E(T)=\\{\\{v_{i},v_{n+i}\\}\mid 1\leq
i\leq n\\}\cup\\{\\{v_{i},v_{i+1}\\}\mid 1\leq i<n\\}$. The path on
$\\{v_{1},v_{2},\ldots,v_{n}\\},~{}n\geq 1$ is the backbone of the comb, and
$\\{v_{n+1},v_{n+2},\ldots,v_{2n}\\},~{}n\geq 1$ are the teeth of the comb. A
triad is a tree $T$ with
$V(T)=\\{u,v_{1},\ldots,v_{p},w_{1},\ldots,w_{q},x_{1},\ldots,x_{r}\\},~{}p\geq
2,~{}q\geq 2,~{}r\geq 2$ and
$E(T)=\\{\\{u,v_{1}\\},\\{u,w_{1}\\},\\{u,x_{1}\\}\\}\cup\cup\\{\\{v_{i},v_{i+1}\\}\mid
1\leq i\leq p-1\\}\cup\\{\\{w_{i},w_{i+1}\\}\mid 1\leq i\leq
q-1\\}\cup\\{\\{x_{i},x_{i+1}\\}\mid 1\leq i\leq r-1\\}$.

Figure 2: An example; Star, Comb, and Triad

###### Definition 1

A split graph $G$ is called $\pi$-convex with convexity on $K$ if there is an
associated structure $\pi$ on $K$ such that for each $v\in I$, $N_{G}(v)$
induces a connected subgraph in $\pi$.

###### Definition 2

A split graph $G$ is called $\pi$-convex with convexity on $I$ if there is an
associated structure $\pi$ on $I$ such that for each $v\in K$, $N^{I}_{G}(v)$
induces a connected subgraph in $\pi$.

In general $\pi$ can be any arbitrary structure. In this paper, We consider
the following structures for $\pi$; ”tree”, ”star”, ”comb”, ”path”, ”triad”,
and ”cycle”. Note that the structure $\pi$ in $G$ is an imaginary structure.
In the rest of the sections, we solve STREE for the case $R=I$ and it is
sufficient to look at this case and all other cases can be solved using $R=I$
as a black box. In Section 6, we present a transformation using which we can
solve other cases.

##  2 The classical complexity of STREE

In Section 2.1, we analyze the classical complexity of STREE on split graphs
with convexity on $I$, and in Section 2.2, we analyze the classical complexity
of STREE on split graphs with convexity on $K$.

###  2.1 STREE in split graphs with convexity on $I$

When we refer to convex split graphs in this section, we refer to convex split
graphs with convexity on $I$. For STREE on split graphs with convexity on I,
we establish hardness results for star-convex and comb-convex split graphs,
and polynomial-time algorithms for path-convex, triad-convex, and circular-
convex split graphs.

####  2.1.1 Star-convex split graphs

In this section, we establish a classical hardness of STREE on star-convex
split graphs by presenting a polynomial-time reduction from the Exact-3-Cover
problem to STREE on star-convex split graphs.
The decision version of Exact-3-Cover problem (X3C) is defined below:

_X3C $(X,\mathcal{C})$_ Instance: A finite set $X=\\{x_{1},\ldots,x_{3q}\\}$
and a collection $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{m}\\}$ of 3-element
subsets of $X$. Question: Is there a subcollection $\mathcal{C^{\prime}}$
$\subseteq$ $\mathcal{C}$ such that for every $x\in X$, $x$ belongs to exactly
one member of $\mathcal{C^{\prime}}$ (that is, $\mathcal{C^{\prime}}$
partitions $X$) ?

The decision version of Steiner tree problem (STREE) is defined below:

_STREE $(G,R,k)$_ Instance: A graph $G$, a terminal set $R\subseteq V(G)$, and
a positive integer $k$. Question: Is there a set $S\subseteq V(G)\setminus R$
such that $|S|\leq k$, and $G[S\cup R]$ is connected ?

###### Theorem 2.1

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

###### Proof

STREE is in NP: Given a star-convex split graph $G$ and a certificate
$S\subseteq V(G)$, we show that there exists a deterministic polynomial-time
algorithm for verifying the validity of $S$. Note that the standard Breadth
First Search (BFS) algorithm can be used to check whether $G[S\cup R]$ is
connected. It is easy to check whether $|S|\leq k$. The certificate
verification can be done in $O(|V(G)|+|E(G)|)$. Thus, we conclude that STREE
is in NP.
STREE is NP-Hard: It is known [19] 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}=\\{c_{i}\mid 1\leq i\leq m\\}$,
$V_{2}=\\{x_{1},x_{2},\ldots,x_{3q},x_{3q+1}\\}$,
$E(G)=\\{\\{c_{i},x_{j}\\}\mid x_{j}\in C_{i},1\leq j\leq 3q,1\leq i\leq
m\\}\cup\\{\\{x_{3q+1},c_{i}\\}\mid 1\leq i\leq
m\\}\cup\\{\\{c_{i},c_{j}\\}\mid 1\leq i\leq j\leq m\\}$. 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}$:
Let $V(T)=V_{2}$ and $E(T)=\\{\\{x_{3q+1},x_{i}\\}\mid 1\leq i\leq 3q\\}$. We
see that $x_{3q+1}$ is the root of the star $T$.
An illustration for X3C with $X=\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\\}$ and
$\mathcal{C}=\\{C_{1}=\\{x_{1},x_{2},x_{3}\\},C_{2}=\\{x_{2},x_{3},x_{4}\\},C_{3}=\\{x_{1},x_{2},x_{5}\\},C_{4}=\\{x_{2},x_{5},x_{6}\\},C_{5}=\\{x_{1},x_{5},x_{6}\\}\\}$,
and the corresponding graph $G$ with $R=I$, $k=2$ is shown in Figure 3. Note
that the imaginary star on $I$ with the root $x_{7}$ is also shown in Figure
3. For this instance the solution to X3C is
$\mathcal{C^{\prime}}=\\{C_{2},C_{5}\\}$, and the corresponding solution for
graph $G$ is $S=\\{c_{2},c_{5}\\}$.

Figure 3: Reduction: An instance of X3C to STREE on star-convex split graphs

Claim 2.1.1. $G$ is a star-convex split graph.

###### Proof

For each $c_{i}\in V_{1}$, $N_{G}^{I}(c_{i})\subseteq V_{2}$. By construction
$x_{3q+1}$ is adjacent to all of $V_{1}$. Therefore, for each $c_{i}\in K$,
$N_{G}^{I}(c_{i})$ is a subtree in $T$. Hence $G$ is a star-convex split
graph. ∎

Claim 2.1.2. Exact-3-Cover ($X,\mathcal{C}$) if and only if STREE
($G,R=V_{2},k=q$)

###### Proof

_Only if:_ If there exists $\mathcal{C^{\prime}}\subseteq\mathcal{C}$ which
partitions $X$, then the set of vertices $S=\\{c_{i}\in V_{1}\mid
C_{i}\in\mathcal{C^{\prime}}\\}$, where $c_{i}$ is the vertex corresponding to
$C_{i}$, forms a Steiner set with $R=V_{2}$.
_If:_ Assume that there exists a Steiner tree $T$ in $G$ for $R=V_{2}$. Let
$S\subseteq V_{1}$ be the Steiner set of $T$, $|S|=q$. We now construct the
corresponding solution to X3C, $\mathcal{C^{\prime}}=\\{C_{i}\in C\mid
c_{i}\in S\\}$. Since $|S|=q$, we have $|\mathcal{C^{\prime}}|=q$. Further,
$S$ is the Steiner set for the terminal set
$R=\\{x_{1},\ldots,x_{3q},x_{3q+1}\\}$. Therefore, for any $c_{i}\in S$, we
have $|N^{I}_{G}(c_{i})\setminus\\{x_{3q+1}\\}|=3$. Since $|S|=q$ and
$|I\setminus\\{x_{3q+1}\\}|=3q$, for all $c_{i},c_{j}\in S,i\neq j$,
$N^{I}_{G}(c_{i})\cap N^{I}_{G}(c_{j})=\\{x_{3q+1}\\}$. Hence for all
$\\{C_{i},~{}C_{j}\\}\subseteq C^{\prime}$, we see that $C_{i}\cap
C_{j}\neq\emptyset$. Therefore, $\mathcal{C^{\prime}}$ is the corresponding
solution to X3C. ∎

Thus we conclude STREE is NP-Hard on the star-convex split graph. Therefore,
STREE is NP-complete on star-convex split graphs. ∎

###### Corollary 1

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

###### Proof

Since star-convex split graphs are a subclass of tree-convex split graphs,
from Theorem 2.1, this result follows. ∎

We next define the parameterized version of the Steiner tree problem and prove
that Theorem 2.1 is indeed a parameter preserving reduction which we establish
in Theorem 2.2. Further, the following result strengthens the result of [18].
The parameterized version of Steiner tree problem (PSTREE) is defined below:

_PSTREE $(G,R,k)$_ Instance: A star-convex split graph $G$, a terminal set
$R\subseteq V(G)$. Parameter: A positive integer $k$. Question: Is there a set
$S\subseteq V(G)\setminus R$ such that $|S|\leq k$, and $G[S\cup R]$ is
connected ?

###### Theorem 2.2

For star-convex split graphs, STREE is W[1]-hard with parameter $|S|$.

###### Proof

It is known [20] that the parameterized Exact Cover problem (generalization of
X3C) with parameter $|\mathcal{C^{\prime}}|$ is W[1]-hard. Note that the
reduction presented in Theorem 2.1 maps $(X,\mathcal{C},q)$ to $(G,R,k=q)$.
From Claim 1.2 of Theorem 2.1, we can observe that the reduction is a solution
preserving reduction. Hence the reduction is a deterministic polynomial-time
parameterized reduction. Therefore, PSTREE on star-convex split graphs is
W[1]-hard. ∎

Since the Steiner tree problem for $R=I$ on star-convex split graphs is
unlikely to have a polynomial-time algorithm, we shall explore the following
two subclasses of star-convex split graphs: (i) star-convex split graphs with
bounded degree $d$ such that for each $y\in I,~{}d_{G}(y)\leq d$, and (ii)
star-convex split graph with imaginary star $T$ on $I$ with $l$ pendent
vertices. For (i), we present a polynomial-time algorithm, and for (ii), we
present an FPT algorithm. Let $T$ be the imaginary star on $I$. In a graph
$G$, the vertices $a,b\in V(G)$ are called twins, if $N_{G}[a]=N_{G}[b]$.
Observe that twins in a split graph can occur only in $K$. For (i) and (ii),
we consider graphs that do not have twins.
We shall now present a polynomial-time algorithm for star-convex split graphs
with bounded degree $d$ such that for each $y\in I,~{}d_{G}(y)\leq d$.

###### Theorem 2.3

Let $G$ be a star-convex split graph with bounded degree $d$ such that for
each $y\in I,~{}d_{G}(y)\leq d$. A minimum Steiner tree $S$ can be found in
polynomial time on $G$ for $R=I$.

###### Proof

Let the root of $T$ be $z$. By the structure of star-convex split graphs, we
know that any $v\in K$ is either adjacent to $z$ or it is adjacent to exactly
one vertex in $T$. We consider the following two cases to find a minimum
Steiner set of $G$ for $R=I$.
_Case 1:_ There exists $y$ in $(T-\\{z\\})$ such that $N_{G}(y)\cap
N_{G}(z)=\emptyset$.
Let $R_{1}=\\{r\mid r\in(I\setminus\\{z\\})\mbox{ such that }N_{G}(r)\cap
N_{G}(z)=\emptyset\\}$. For each $r\in R_{1}$, we include the neighbor of $r$
in $S_{1}$, say $v$. The set $S_{1}$ can be found in linear time.
_Case 2:_ There exists $y$ in $(T-\\{z\\})$ such that $N_{G}(y)\cap
N_{G}(z)\neq\emptyset$.
Let $R_{2}=\\{s\mid s\in(I\setminus\\{z\\})\mbox{ such that }N_{G}(s)\cap
N_{G}(z)\neq\emptyset\\}$. Since $|N_{G}(z)|\leq d$, we find a minimum sized
subset $S_{2}$ in $N_{G}(z)$ such that for each $s\in R_{2}$, $N_{G}(s)\cap
R_{2}\neq\emptyset$. Since $d$ is a constant, the set $S_{2}$ can be found in
linear time.
If $R_{1}\neq\emptyset,~{}R_{2}\neq\emptyset$, then the $S$ of $G$ for $R=I$
is $S_{1}\cup S_{2}$. If $S_{2}=\emptyset$, then the Steiner set $S$ of $G$
for $R=I$ is $S=S_{1}\cup\\{v\\}$, where $v\in N_{G}(z)$. If
$S_{1}=\emptyset$, then the Steiner set $S$ of $G$ for $R=I$ is $S=S_{2}$.
Observe that for each $a\in I$, $N_{G}(a)\cap S\neq\emptyset$. It is clear
that $S$ is a Steiner set of $G$ for $R=I$.
For each vertex $r\in R_{1}$, $|N_{G}(r)\cap S|=1$, and for each vertex $s\in
R_{2}$, $|N_{G}(s)\cap S|=1$. Note that $R_{1}\cap R_{2}=\emptyset$ and
$R_{1}\cup R_{2}=I$. Therefore, $S$ is a minimum Steiner set of $G$ for $R=I$.
∎

Further, we analyze the complexity of STREE for $R=I$ on star-convex split
graphs with the number of pendent vertices in the imaginary star is bounded,
say $l$ (degree of root vertex in imaginary star $T$). The parameterized
version of the Steiner tree problem (PSTREE1) is defined below:

_PSTREE1 $(G,R,k)$_ Instance: A star-convex split graph $G$ with imaginary
star $T$ on $I$ with $l$ pendent vertices, a terminal set $R=I$. Parameter: A
positive integers $l$ and $k$. Question: Is there a set $S\subseteq
V(G)\setminus R$ such that $|S|\leq k$, and $G[S\cup R]$ is connected ?

###### Theorem 2.4

Let $G$ be an instance of PSTREE1. Then $G$ has a kernel of size $2^{l}-1$.

###### Proof

Let $z$ be the root of the imaginary star $T$. Since $|V(T)|=l$, it is clear
that $S\subseteq(N_{G}(V(T)\setminus\\{z\\}))$. We preprocess the graph $G$
and $G^{\prime}$ is obtained as follows; Let $Y=\\{y\mid y\in
I,~{}|N_{G}(y)|=1\\}$. We obtain the graph $G^{\prime}=G-N_{G}[Y]$ with
$k=k-|Y|$. Let the imaginary structure in $I$ of $G^{\prime}$ be $T^{\prime}$.
The cardinality of $(N_{G^{\prime}}(V(T^{\prime})\setminus\\{z\\}))$ in
$G^{\prime}$ is at most $2^{l}-1$. Thus $S^{\prime}\subseteq
N_{G^{\prime}}(V(T)\setminus\\{z\\})$, and we obtain a kernel of size
$2^{l}-1$ for PSTREE1. From the kernel of size $2^{l}-1$, we obtain the
Steiner set $S^{\prime}$ of $G^{\prime}$ by finding all possible subsets of
size at most $k$. Thus the Steiner set $S$ of $G$ for $R=I$ is obtained in
time $O(2^{lk}n^{2})$. ∎

Highlights:
It turns out that STREE on tree-convex split graphs is NP-complete. It is
natural to ask for complexity when the imaginary tree has a special structure.
For example, binary-tree, ternary tree, and so on. Interestingly, a comb is a
special case of binary trees; in Section 2.1.2, for comb-convex split graphs,
we show that STREE is NP-complete. As far as a study on unary-tree-convex
split graphs is concerned, we observe that unary-tree-convex split graphs are
precisely path-convex split graphs. In Section 2.1.3, we show that STREE on
path-convex split graphs is polynomial-time solvable. This draws a thin line
between P-versus-NPC input instances of STREE; polynomial-time solvable for
unary-tree-convex split graphs and NP-complete for binary-tree-convex split
graphs. One can also see the dichotomy status of this problem via these two
structures as well.

####  2.1.2 Comb-convex split graphs

We present a polynomial-time reduction from the vertex cover problem on
general graphs to STREE on comb-convex split graphs.
The decision version of Vertex Cover problem (VC) is defined below:

_VC $(G,k)$_ Instance: A graph $G$, a non-negative integer $k$. Question: Does
there exist a set $S\subseteq V(G)$ such that for each edge $e=\\{u,v\\}\in
E(G)$, $u\in S$ or $v\in S$ and $|S|\leq k$ ?

###### Theorem 2.5

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

###### Proof

STREE is NP-Hard: It is known [15] 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}$,
$V_{1}=\\{x_{i}\mid v_{i}\in V(G)\\}$,
$V_{2}=\\{y_{i}\mid e_{i}\in E(G)\\}$,
$V_{3}=\\{z_{i}\mid e_{i}\in E(G)\\}$.
We shall now describe the edges of $G^{*}$,
$E(G^{*})=E_{1}\cup E_{2}\cup E_{3}$. Let $n=|V(G)|,~{}m=|E(G)|$
$E_{1}=\\{\\{y_{i},x_{p}\\},\\{y_{i},x_{q}\\},\mid e_{i}=\\{v_{p},v_{q}\\}\in
E(G),~{}x_{p},x_{q}\in V_{1},~{}y_{i}\in V_{2},~{}1\leq i\leq m,~{}1\leq p\leq
n,~{}1\leq q\leq n\\}\\\ E_{2}=\\{\\{x,z_{i}\\}\\}\mid x\in V_{1},~{}z_{i}\in
V_{3},~{}1\leq i\leq m\\}$
$E_{3}=\\{\\{x_{i},x_{j}\\}\mid,x_{i},x_{j}\in V_{1},1\leq i\leq j\leq n\\}$.
We define $K=V_{1}$, $I=V_{2}\cup V_{3}$, and the imaginary comb $T$ on $I$ is
defined with $V_{3}$ as the backbone and $V_{2}$ as the pendant vertex set.
That is, $V(T)=I$ and
$E(T)=\\{\\{y_{1},z_{1}\\},\\{y_{2},z_{2}\\},\ldots,\\{y_{i},z_{i}\\}\mid
1\leq i\leq m\\}$.
An example is illustrated in Figure 4, the vertex cover instance $G$ with
$k=2$ is mapped to STREE instance of comb-convex split graph $G^{*}$ with
$R=\\{y_{1},y_{2},y_{3}\\}$, $k^{\prime}=2$.

Figure 4: An example: VC reduces to STREE.

Claim 2.5.1. $G^{*}$ is a comb-convex split graph.

###### Proof

For each $x_{i}\in V_{1}$, $N_{G}^{I}(x_{i})=V_{3}\cup W,~{}W\subseteq V_{2}$.
By our construction $x_{i}$ is adjacent to all of $V_{3}$. Therefore, the
graph induced on $N_{G}^{I}(x_{i})$ is a subtree in $T$. Hence $G^{*}$ is a
comb-convex split graph. ∎

Claim 2.5.2. $(G,k)$ has a vertex cover with at most $k$ vertices if and only
if $(G^{*},R=\\{y_{i}\mid 1\leq i\leq m\\}\\},k^{\prime}=k)$ has a Steiner
tree of size at most $k^{\prime}=k$ Steiner vertices.

###### Proof

_(Only if)_ Let $V^{\prime}=\\{v_{i}\mid 1\leq i\leq k\\}$ is a vertex cover
of size $k$ in $G$. Then we construct the Steiner set $S$ of $G^{*}$ for
$R=\\{y_{i}\mid 1\leq i\leq m\\}$ as follows: $S=\\{x_{i}\mid 1\leq i\leq
k,~{}v_{i}\in V^{\prime},~{}x_{i}\in V(G^{*})\\}$. Since $V^{\prime}$ is a
vertex cover, for any edge $e_{i}=\\{v_{p},v_{q}\\}\in E(G)$, $v_{p}$ or
$v_{q}$ is in $V^{\prime}$. Hence $S$ contains $x_{p}$ or $x_{q}$. Therefore,
by the definition of $V_{2}$, for each vertex $y_{i}$, there exists a neighbor
in $S$. Since $V_{1}$ is a clique by our construction, $G[R\cup S]$ is
connected.
_(If)_ For $R$ in $G^{*}$, let $S=\\{x_{i}\mid 1\leq i\leq k^{\prime}\\}$ is a
Steiner set of $G^{*}$ of size $k^{\prime}$. Then, we construct the vertex
cover $V^{\prime}$ of size $k$ in $G$ as follows; $V^{\prime}=\\{v_{i}\mid
x_{i}\in S,~{}v_{i}\in V(G),~{}1\leq i\leq k^{\prime}\\}$. We now claim that
$V^{\prime}$ is a vertex cover in $G$. Suppose that there is an edge
$e_{i}=\\{v_{p},v_{q}\\}\in E(G)$ for which neither $v_{p}$ nor $v_{q}$ is in
$V^{\prime}$. This implies that neither $x_{p}$ nor $x_{q}$ is in $S$. Since
$R$ contains $y_{i}$, it follows that $N_{G}(y_{i})\cap S=\emptyset$. Thus $S$
is not a Steiner set. A contradiction. Therefore, $V^{\prime}$ is a vertex
cover of size $k$ in $G$. ∎

Thus we conclude STREE is NP-Hard. Therefore, STREE is NP-complete on comb-
convex split graphs. ∎

Having arbitrary comb $T$ as imaginary structure, STREE on comb-convex split
graphs is NP-complete. We show that finding STREE on comb-convex split graphs
$G$ with backbone path of length $l$ for $R=I$ is in XP with respect to the
parameter $l$. Let the backbone path $B$ of imaginary comb $T$ be
$(a_{1},a_{2}\ldots,a_{l})$. Observe that $d_{T}(a_{i})=3,~{}2\leq i\leq l-1$.
Hence Lemma 2 in triad-convex split graphs is also true for each $a_{i}\in
I,~{}2\leq i\leq l-1$ in the comb-convex split graphs.

###### Lemma 1

Let $G$ be a comb-convex split graph. Let $S$ be a minimum Steiner set of $G$
for $R=I$. Then $1\leq|N_{G}(z)\cap S|\leq 3$, where
$z\in\\{a_{2},\ldots,a_{l-1}\\}$.

###### Proof

The proof is similar to the proof of Lemma 2.

The parameterized version of the Steiner tree problem (PSTREE2) is defined
below:

_PSTREE2 $(G,R,k)$_ Instance: A star-convex split graph $G$ with imaginary
comb $T$ on $I$ with $l$ vertices in the backbone path, a terminal set $R=I$.
Parameter: A positive integer $l$. Question: Is there a set $S\subseteq
V(G)\setminus R$ such that $|S|\leq k$, and $G[S\cup R]$ is connected ?

###### Theorem 2.6

Let $G$ be an instance of PSTREE2. Then $S$ can be found in $O(n^{3l})$ time.

###### Proof

Our proof is constructive. For each $a_{i}\in I,~{}2\leq i\leq l-1$, we
explore at most three vertex combinations in $N_{G}(a_{i})$, which is similar
to Algorithm 2. The proof of correctness is similar to the proof of Theorem
2.9. Since there are $l$ vertices in the backbone path of $T$, $S$ can be
found in $O(n^{3l})$ time. ∎

Insights into reduction instances of Theorem 2.5
A closer look at the reduction instances of Theorem 2.5 reveals that the
presence of pendant vertices in the comb makes the problem NP-hard. It is
natural to ask for the complexity of STREE in a variant of comb-convex split
graphs where there are no pendant vertices (no teeth) in the comb which is
precisely the class of path-convex split graphs. Interestingly, STREE on path-
convex split graphs is polynomial-time solvable, which we prove in the next
section.

####  2.1.3 Path-convex split graphs

In this section, we propose a polynomial-time algorithm for STREE on path-
convex split graphs. Recall that a split graph $G$ is called path-convex if
there exists a linear ordering $\sigma$ of vertices in $I$ such that for each
$u\in K$, $N_{G}(u)$ is consecutive in $I$ with respect to $\sigma$.
Let $G$ be a path-convex split graph. Let the vertices in $K$ be
$w_{1},\ldots,w_{m}$, and the vertices in $I$ be $x_{1},\ldots,x_{n}$. Path-
convex split graphs can also be interpreted as follows: there exists an
imaginary path $P=(x_{1},\ldots,x_{n})$ on $I$ such that for each $u\in K$,
$N^{I}_{G}(u)$ is an interval (subpath in the imaginary path) in $I$. When we
refer to $x_{i}$ in $\sigma$, the index of $x_{i}$ in $\sigma$ is $i$. For
$u\in K$, if $N_{G}^{I}(u)=\\{x_{p},\ldots,x_{q}\\}$, then $l(u)=x_{p}$ and
$r(u)=x_{q}$. That is $l(u)$ is the least indexed vertex of $N^{I}_{G}(u)$ in
$\sigma$, and $r(u)$ is the greatest indexed vertex in $N^{I}_{G}(u)$. For
each $x_{i}\in I$, $1\leq i\leq n$, let $\alpha(x_{i})=u$ such that $u\in
N_{G}(x_{i})$ and $r(u)$ is maximum. For $w_{i},w_{j}\in K$, when we write
$w_{i}\prec w_{j}$, we mean that $r(w_{i})$ appears before $r(w_{j})$ with
respect to $\sigma$. We order the vertices in $K$ as follows; $w_{1}\prec
w_{2}\prec\ldots\prec w_{m}$.
The idea behind our Algorithm 1 is to visualize the neighborhood of each
vertex in $K$ as intervals and each vertex in $I$ as points. All points in $I$
are unmarked initially. Choose the largest interval, say $\gamma$ starting
from $x_{1}$. Mark all the points in $I$ that are in $\gamma$. Among the
unmarked points in $I$ choose the point whose index is minimum, say $x_{j}$.
We continue our algorithm by choosing the interval, say $\beta$ that contains
$x_{j}$ and whose right endpoint is maximum. Mark all points in $I$ that are
contained in $\beta$ and proceed in the similar line until we hit the point
$x_{t}$. This greedy approach is indeed optimum, which we establish in this
section.

Algorithm 1 STREE for path-convex split graphs.

1:Input: A connected path-convex split graph $G$ and $R=I$.

2:All vertices in $I$ are unmarked initially. Let $i=1$, $b=r(\alpha(x_{1}))$,
the Steiner set $S=\\{\alpha(x_{1})\\}$.

3:Mark all vertices in $I$ that are adjacent to $\alpha(x_{1})$.

4:while $b\neq x_{t}$ do

5: Let $c$ be the least indexed unmarked vertex in $I$.

6: $b=r(\alpha(c))$, $S=S\cup\\{\alpha(c)\\}$.

7:end while

Let $S=\\{u_{1},\ldots,u_{p}\\}$ be the Steiner vertices chosen by the
algorithm. Note that as per our algorithm $u_{1}\prec u_{2}\prec\ldots\prec
u_{p}$. Let $S^{\prime}=\\{u^{\prime}_{1},\ldots,u^{\prime}_{q}\\}$ be the
Steiner vertices chosen by any optimal algorithm. Without loss of generality,
we arrange $S^{\prime}$ such that $u^{\prime}_{1}\prec
u^{\prime}_{2}\prec\ldots\prec u^{\prime}_{q}$. Since $R=I$, observe that
$S\subseteq K$ and $S^{\prime}\subseteq K$.

###### Theorem 2.7

For all indices $i\leq q$, $N_{G}^{I}(\\{u_{1},\ldots,u_{i}\\})\supseteq
N_{G}^{I}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{i}\\})$

###### Proof

By mathematical induction on $i$, $i\geq 1$.
Base Case: For $i=1$,
Since $u^{\prime}_{1}\prec u^{\prime}_{j},~{}j>1$, we have
$\\{x_{1},u^{\prime}_{1}\\}\in E(G)$. Since our algorithm has chosen $u_{1}$,
$\\{x_{1},u_{1}\\}\in E(G)$ and by Step 2 of Algorithm 1,
$u_{1}=\alpha(x_{1})$. Therefore, $u^{\prime}_{1}\prec u_{1}$. The ordering of
$K$ and the convexity on $I$ imply that $N_{G}(u_{1})\supseteq
N_{G}(u^{\prime}_{1})$.
Induction Hypothesis: Assume for $i\geq 2$,
$N^{I}_{G}(\\{u_{1},\ldots,u_{i-1}\\})\supseteq
N^{I}_{G}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{i-1}\\})$ is true.
Induction Step: We prove that when $i\geq 2$,
$N^{I}_{G}(\\{u_{1},\ldots,u_{i}\\})\supseteq
N^{I}_{G}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{i}\\})$.
By the induction hypothesis, we know that up to $i-1$,
$N^{I}_{G}(\\{u_{1},\ldots,u_{i-1}\\})\supseteq
N^{I}_{G}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{i-1}\\})$. Observe that as per
Step 6 of the algorithm, we have included $u_{i}\in S$. This implies that
after inclusion of $u_{1},\ldots u_{i-1}$ into the solution, $u_{i}$ refers to
$\alpha(c)$ where $c$ is the least indexed unmarked vertex in $I$.
Assume on the contrary, $N^{I}_{G}(\\{u_{1},\ldots,u_{i}\\})\nsupseteq
N^{I}_{G}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{i}\\})$. Then there exists
$y\in I$ such that $y\in N_{G}(u^{\prime}_{i})$ and $y\notin N_{G}(u_{i})$. It
is clear that $\alpha(y)\prec u_{i}$. Since our algorithm must have included
at least one vertex adjacent to $y$, it must be the case that $y\in
N_{G}(u_{j})$, for some $j$, $1\leq j\leq i-1$. This implies that $y\in
N^{I}_{G}(\\{u_{1},\ldots,u_{i-1}\\})$, which is a contradiction.
Therefore, $N_{G}^{I}(\\{u_{1},\ldots,u_{i}\\})\supseteq
N_{G}^{I}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{i}\\})$. Hence the proof. ∎

###### Theorem 2.8

Algorithm 1 outputs a minimum Steiner set, that is $p=q$.

###### Proof

By Theorem 2.7, we know that $N_{G}^{I}(\\{u_{1},\ldots,u_{q}\\})\supseteq
N_{G}^{I}(\\{u^{\prime}_{1},\ldots,u^{\prime}_{q}\\})$, and hence
$|S|\leq|S^{\prime}|$. Since $S^{\prime}$ is an optimal solution,
$|S|\geq|S^{\prime}|$. Therefore, $|S|=|S^{\prime}|$, and $p=q$. ∎

It is easy to see that Algorithm 1 runs in time $O(mn)$.
Now we see that for comb-convex split graphs, STREE is NP-complete, whereas,
for path-convex split graphs, STREE is polynomial-time solvable. This brings
out the P-versus-NPC investigation of STREE on tree-convex split graphs. This
is one of the objectives of this research.
It is important to highlight that we can solve STREE on triad-convex and
circular-convex split graphs by using the algorithm of STREE on path-convex
split graphs as a black box, which we prove in the following two sections.

Application 1: Triad-convex split graphs

We investigate the classical complexity of STREE on triad-convex split graphs
which are a variant of path-convex split graphs. Since a triad structure has
three paths with a common endpoint (root vertex), we shall explore the
possibility of solving STREE on triad-convex split graphs using the algorithm
for STREE on path-convex split graphs as a black box.
We now present a polynomial-time reduction to map the instances of triad-
convex split graphs to the instances of path-convex split graphs. The
reduction is similar to the reduction presented in [12].
Let $G$ be a triad-convex split graph with triad $T$ defined on $I$ such that
for every $u\in K,~{}N_{G}^{I}(u)$ is a subtree in $T$. Let $z$ be the root
vertex of the triad $T$. There are three paths in $T-z$, let those paths be
$B_{1},B_{2},$ and $B_{3}$. Let the vertices in $B_{i}$ be
$(x^{i}_{1},~{}x^{i}_{2},\ldots,~{}x^{i}_{|B_{i}|}),~{}1\leq i\leq 3$. Let the
vertices in $K$ be $w_{1},\ldots,w_{m}$. Since $T$ is a triad,
$N_{T}(z)=\\{x_{1}^{1},x_{1}^{2},x_{1}^{3}\\}$. Let
$N_{G}(z)=\\{u_{1},\ldots,u_{s}\\}$. Observe that $N_{G}(z)\subseteq K$.
For each vertex $u_{j}\in N_{G}(z)$, $1\leq j\leq s$, we define
$r(B_{i},u_{j})=x^{i}_{p}$ such that $N_{G}(u_{j})\cap B_{i}\neq\emptyset$,
$x^{i}_{p}\in N_{G}(u_{j})$ and there does not exist $x^{i}_{q}\in
N_{G}(u_{j})$, $p+1\leq q\leq|B_{i}|$. Let

$\alpha_{i,j}=\max_{u_{j}}~{}r(B_{i},u_{j}),~{}\beta_{i,j}=v,~{}v\in(N_{G}(\alpha_{i,j})\cap
N_{G}(z)),~{}1\leq i\leq 3,~{}1\leq j\leq s.$

The following lemma is a key result for our reduction in work.

###### Lemma 2

Let $G$ be a triad-convex split graph. Let $S$ be a minimum Steiner set of $G$
for $R=I$. Then, $1\leq|N_{G}(z)\cap S|\leq 3$, where $z$ is the root of the
triad.

###### Proof

It is clear that for every vertex $y\in R$, $|N_{G}(y)\cap S|\geq 1$.
Suppose that $|N_{G}(z)\cap S|>3$. We claim that $N^{I}_{G}(\beta_{1,j})\cup
N^{I}_{G}(\beta_{2,k})\cup N^{I}_{G}(\beta_{3,l})\supseteq
N^{I}_{G}(N_{G}(z)\cap S),~{}1\leq j<k<l\leq s$. On the contrary, there exists
$y\in I$ such that $y\in N_{G}^{I}(N_{G}(z)\cap S)$ and
$y\notin(N^{I}_{G}(\beta_{1,j})\cup N^{I}_{G}(\beta_{2,k})\cup
N^{I}_{G}(\beta_{3,l}))$. Without loss of generality, we shall assume that
$y\in B_{1}$. Let $\alpha_{1,j}$ be $x^{1}_{p}$, for some $p$, $1\leq
p\leq|B_{1}|$. Then $y\in\\{x^{1}_{1},\ldots,x^{1}_{p}\\}$. By the definition
of $\beta_{1,j}$, we know that $\\{x^{1}_{1},\ldots,x^{1}_{p}\\}\subseteq
N^{I}_{G}(\beta_{1,j})$. Hence, $y\in(N^{I}_{G}(N_{G}(z)\cap S))\cap B_{1}$
and $y\in N_{G}^{I}(\beta_{1,j})$, which is a contradiction that $y\notin
N_{G}^{I}(\beta_{1,j})$. Similarly, the argument is true if $y\in\beta_{2,k}$
or $y\in\beta_{3,l}$. Thus there exists $y\in I$ such that $y\in
N_{G}^{I}(N_{G}(z)\cap S)$ and $y\notin(N^{I}_{G}(\beta_{1,j})\cup
N^{I}_{G}(\beta_{2,k})\cup N^{I}_{G}(\beta_{3,l}))$ is a contradiction and
$N^{I}_{G}(\beta_{1,j})\cup N^{I}_{G}(\beta_{2,k})\cup
N^{I}_{G}(\beta_{3,l})\supseteq N^{I}_{G}(N_{G}(z)\cap S)$.
Observe that $\beta_{1,j},~{}\beta_{2,k},~{}\beta_{3,l}$ need not be distinct
always. Consider $S^{\prime}=(S\setminus
N_{G}(z))\cup\\{\beta_{1,j},~{}\beta_{2,k},~{}\beta_{3,l}\\}$. Note that
$|S^{\prime}|\leq|S|-1$, which is a contradiction that $S$ is a minimum
Steiner set of $G$ for $R=I$. ∎

The above lemma indicates that $|N_{G}(z)\cap S|=1$, $|N_{G}(z)\cap S|=2$, and
$|N_{G}(z)\cap S|=3$. Accordingly, for each triad-convex split graph, we
construct a corresponding set of path-convex split graphs as part of
Construction 1, Construction 2, and Construction 3 which are explained below.
Further, using our construction and Algorithm 1, we obtain a polynomial-time
algorithm for triad-convex split graphs. We have the following cases:

Case 1: Exactly one neighbor of $z$ is in $S$.
Case 2: Exactly two neighbors of $z$ is in $S$.
Case 3: Exactly three neighbors of $z$ is in $S$.

For each $u_{j}\in N_{G}(z),~{}1\leq j\leq s$, $A(u_{j})$ represents a minimum
Steiner set of $G$ for $R=I$ containing $u_{j}$. For each $u_{j},u_{k}\in
N_{G}(z),~{}1\leq j<k\leq s$, $A(u_{j},u_{k})$ represents a minimum Steiner
set of $G$ for $R=I$ containing $u_{j},u_{k}$. For each
$u_{j},u_{k},u_{l},~{}\\{u_{j},u_{k},u_{l}\\}\subseteq N_{G}(z),~{}1\leq
j<k<l\leq s$, $A(u_{j},u_{k},u_{l})$ represents a minimum Steiner set of $G$
for $R=I$ containing $u_{j},u_{k},u_{l}$.
Computation of a minimum Steiner set in each of the three cases.
For each case, we shall construct a set of path-convex split graphs using
which we compute a minimum Steiner set $S$ of $G$.
Case 1: Exactly one neighbor of $z$ is in $S$.
Construction 1:
For each $u_{j}\in N_{G}(z),~{}1\leq j\leq s$, we do the following:
Since $(N_{G}(z)\setminus\\{u_{j}\\})\cap S=\emptyset$, using the graph
$G_{j}=G-(N_{G}(z)\cup N^{I}_{G}(u_{j}))$, we construct $G^{i}_{j}$, for each
$i,~{}1\leq i\leq 3$ as follows;
The graph $G^{i}_{j}$ with
$I^{i}_{j}=B_{i}\cap(I\setminus\\{N^{I}_{G}(u_{j})\\})$,
$K^{i}_{j}=K\cap(N_{G}(B_{i})\setminus N_{G}(z))$, and
$E(G^{i}_{j})=\\{\\{x,y\\}\mid x,y\in V(G^{i}_{j}),~{}\\{x,y\\}\in E(G)\\}$.
The ordering of $I^{i}_{j}$ for $G^{i}_{j}$ is given by
$B_{i}\cap(I\setminus\\{N^{I}_{G}(u_{j})\\})$ with respect to the ordering $I$
in $G$. Hence each $G^{i}_{j}$ is a path-convex split graph with ordering on
$I^{i}_{j}$. Let $S^{i}_{j}$ be a minimum Steiner set $G^{i}_{j}$ for
$R=I^{i}_{j}$, obtained using Algorithm 1. Then a minimum Steiner set of $G$
for $R=I$ containing $u_{j}$ is $A(u_{j})=S^{i}_{j}\cup\\{u_{j}\\}$ and the
proof for minimality of $A(u_{j})$ is established in Lemma 3.

###### Lemma 3

For some $u_{j}\in N_{G}(z)$, if $N_{G}(z)\cap S=\\{u_{j}\\}$ then
$|S|=|S^{1}_{j}|+|S^{2}_{j}|+|S^{3}_{j}|+1$.

###### Proof

Let $S^{1}_{j}\cup S^{2}_{j}\cup S^{3}_{j},~{}1\leq j\leq s$ be a Steiner set
of the graph $G^{1}_{j}\cup G^{2}_{j}\cup G^{3}_{j}$. Let $G^{\prime}$ be the
graph induced on $N^{I}_{G}[u_{j}]\cup V(G^{1}_{j})\cup V(G^{2}_{j})\cup
V(G^{3}_{j}),~{}1\leq j\leq s$. The graph $G^{\prime}$ for $R=I$, the Steiner
set is $S^{\prime}=\\{u_{j}\\}\cup S^{1}_{j}\cup S^{2}_{j}\cup S^{3}_{j}$. We
can observe that $G^{\prime}$ is a subgraph of $G$, since
$V(G)=V(G^{\prime})\cup N_{G}(z)$. Thus $S^{\prime}$ is a Steiner set of $G$
for $R=I$. For any minimum Steiner set $S$ of $G$ containing $u_{j}$ for
$R=I$, clearly, $|S|\leq|S^{\prime}|=|S^{1}_{j}|+|S^{2}_{j}|+|S^{3}_{j}|+1$.

We now show that for any minimum Steiner set $S$ of $G$ containing $u_{j}$ for
$R=I$, $|S|\geq|S^{1}_{j}|+|S^{2}_{j}|+|S^{3}_{j}|+1$. Assume $S$ is the
minimum Steiner set of $G$ for $R=I$ and $N_{G}(z)\cap S=\\{u_{j}\\}$. Then
$S^{1}_{j}$ is a Steiner set of $G^{1}_{j}$ for $R=I^{1}_{j}$ such that
$S^{1}_{j}=S\cap V(G^{1}_{j})$. For each $v\in V(G^{1}_{j})$,
$N_{G^{1}_{j}}(v)\cap S^{1}_{j}\neq\emptyset$. Similarly, for $R=I^{2}_{j}$ of
$G^{2}_{j}$, $S^{2}_{j}=S\cap V(G^{2}_{j})$ and for $R=I^{3}_{j}$ of
$G^{3}_{j}$, $S^{3}_{j}=S\cap V(G^{3}_{j})$. Hence,
$S=(S\cap V(G^{1}_{j}))\cup(S\cap V(G^{2}_{j}))\cup(S\cap
V(G^{3}_{j}))\cup\\{u_{j}\\}$
$|S|=|(S\cap V(G^{1}_{j}))\cup(S\cap V(G^{2}_{j}))\cup(S\cap
V(G^{3}_{j}))\cup\\{u_{j}\\}|$
$=|(S\cap V(G^{1}_{j}))\cup(S\cap V(G^{2}_{j}))\cup(S\cap V(G^{3}_{j}))|+1$
Since $|S\cap V(G^{1}_{j})|\geq|S^{1}_{j}|$, $|S\cap
V(G^{2}_{j})|\geq|S^{2}_{j}|$,and $|S\cap V(G^{3}_{j})|\geq|S^{3}_{j}|$, we
get
$|S|\geq|S^{1}_{j}|+|S^{2}_{j}|+|S^{3}_{j}|+1$
Therefore, $|S|=|S^{1}_{j}|+|S^{2}_{j}|+|S^{3}_{j}|+1$ is a minimum Steiner
set of $G$ for $R=I$. ∎

Case 2: Exactly two neighbors of $z$ is in $S$.
Construction 2:
For each $u_{j},u_{k}\in N_{G}(z),~{}1\leq j<k\leq s$, we do the following:
Since $(N_{G}(z)\setminus\\{u_{j},u_{k}\\})\cap S=\emptyset$, using the graph
$G_{jk}=G-(N_{G}(z)\cup N^{I}_{G}(u_{j})\cup N^{I}_{G}(u_{k}))$, we construct
$G^{i}_{jk}$, for each $i,~{}1\leq i\leq 3$ as follows;
The graph $G^{i}_{jk}$ with
$I^{i}_{jk}=B_{i}\cap(I\setminus\\{N^{I}_{G}(u_{j})\cup N^{I}_{G}(u_{k})\\})$,
$K^{i}_{jk}=K\cap(N_{G}(B_{i})\setminus N_{G}(z))$, and
$E(G^{i}_{jk})=\\{\\{x,y\\}\mid x,y\in V(G^{1}_{ij}),~{}\\{x,y\\}\in E(G)\\}$.
The ordering of $I^{i}_{jk}$ for $G^{i}_{jk}$ is given by
$B_{i}\cap(I\setminus(\\{N^{I}_{G}(u_{j})\\}\cup N^{I}_{G}(u_{k})))$ with
respect to ordering $I$ in $G$. Hence each $G^{i}_{jk}$ is a path-convex split
graph with ordering on $I^{i}_{jk}$. Let $S^{i}_{jk}$ a minimum Steiner set of
$G^{i}_{jk}$ for $R=I^{i}_{jk}$ is obtained using Algorithm 1. Then a minimum
Steiner set of $G$ for $R=I$ containing $u_{j},~{}u_{k}$ is
$A(u_{j},u_{k})=S^{i}_{jk}\cup\\{u_{j},u_{k}\\}$ and the proof of minimality
of $A(u_{j},u_{k})$ is as per Lemma 4.

###### Lemma 4

For some $u_{j},u_{k}\in N_{G}(z)$, if $N_{G}(z)\cap S=\\{u_{j},u_{k}\\}$ then
$|S|=|S^{1}_{jk}|+|S^{2}_{jk}|+|S^{3}_{jk}|+2$.

###### Proof

The proof is similar to the proof of Lemma 3. ∎

Case 3: Exactly three neighbors of $z$ are in $S$.
Construction 3:
For each $u_{j},u_{k},u_{l}$ such that $\\{u_{j},u_{k},u_{l}\\}\subseteq
N_{G}(z),~{}1\leq j<k<l\leq s$, we do the following:
Since $(N_{G}(z)\setminus\\{u_{j},u_{k},u_{l}\\})\cap S=\emptyset$, using the
graph $G_{jkl}=G-(N_{G}(z)\cup N^{I}_{G}(u_{j})\cup N^{I}_{G}(u_{k})\cup
N^{I}_{G}(u_{l}))$, we construct $G^{i}_{jkl}$, for each $i,~{}1\leq i\leq 3$
as follows;
The graph $G^{i}_{jkl}$ with
$I^{i}_{jkl}=B_{i}\cap(I\setminus\\{N^{I}_{G}(u_{j})\cup N^{I}_{G}(u_{k})\cup
N^{I}_{G}(u_{l})\\}$, $K^{i}_{jkl}=K\cap(N_{G}(B_{i})\setminus N_{G}(z))$, and
$E(G^{i}_{jkl})=\\{\\{x,y\\}\mid x,y\in V(G^{i}_{jkl}),~{}\\{x,y\\}\in
E(G)\\}$.

The ordering of $I^{i}_{jkl}$ for $G^{i}_{jkl}$ is given by
$B_{i}\cap(I\setminus(\\{N^{I}_{G}(u_{j})\\}\cup N^{I}_{G}(u_{k})\cup
N^{I}_{G}(u_{l})))$ with respect to ordering $I$ in $G$. Hence each
$G^{i}_{jkl}$ is a path-convex split graph with ordering on $I^{i}_{jkl}$. Let
$S^{i}_{jkl}$ a minimum Steiner set of $G^{i}_{jkl}$ for $R=I^{i}_{jkl}$ is
obtained using Algorithm 1. Then a minimum Steiner set of $G$ for $R=I$
containing $u_{j},~{}u_{k},~{}u_{l}$ is
$A(u_{j},u_{k},u_{l})=S^{i}_{jkl}\cup\\{u_{j},u_{k},u_{l}\\}$ and the proof of
minimality of $A(u_{j},u_{k},u_{l})$ is as per Lemma 5.

###### Lemma 5

For some $u_{j},u_{k},u_{l}$ such that $\\{u_{j},u_{k},u_{l}\\}\subseteq
N_{G}(z)$, If $N_{G}(z)\cap S=\\{u_{j},u_{k},u_{l}\\}$ then
$|S|=|S^{1}_{jkl}|+|S^{2}_{jkl}|+|S^{3}_{jkl}|+3$.

###### Proof

The proof is similar to the proof of Lemma 3. ∎

Now we shall present an algorithm to find a minimum Steiner set of $G$ for
$R=I$.

Algorithm 2 STREE for triad-convex split graphs.

1:Input: A connected triad-convex split graph $G$, $R=I$.

2:Let $z$ be the central vertex of triad $T$, and let
$S=\emptyset,~{}S_{1}=\emptyset,~{}S_{2}=\emptyset,~{}S_{3}=\emptyset$.

3:for all $u_{j},~{}u_{j}\in N_{G}(z)$ do

4: Construct $G^{1}_{j},~{}G^{2}_{j},~{}G^{3}_{j}$ using Construction 1.

5: Using Algorithm 1, find minimum Steiner sets $S^{1}_{j}$, $S^{2}_{j}$, and
$S^{3}_{j}$ for $G^{1}_{j},~{}G^{2}_{j},$ and $G^{3}_{j}$, respectively.

6: Update $S_{1}=S_{1}\cup\\{S^{1}_{j}\cup S^{2}_{j}\cup
S^{3}_{j}\cup\\{u_{j}\\}\\}$

7:end for

8:for all $u_{j},u_{k},~{}u_{j},u_{k}\in N_{G}(z)$ do

9: Construct $G^{1}_{jk},~{}G^{2}_{jk},~{}G^{3}_{jk}$ using Construction 2.

10: Using Algorithm 1, find minimum Steiner sets $S^{1}_{jk}$, $S^{2}_{jk}$,
and $S^{3}_{jk}$ for $G^{1}_{jk},~{}G^{2}_{jk},$ and $G^{3}_{jk}$,
respectively.

11: Update $S_{2}=S_{2}\cup\\{S^{1}_{jk}\cup S^{2}_{jk}\cup
S^{3}_{jk}\cup\\{u_{j},u_{k}\\}\\}$

12:end for

13:for all $u_{j},u_{k},u_{l},~{}\\{u_{j},u_{k},u_{l}\\}\subseteq N_{G}(z)$ do

14: Construct $G^{1}_{jkl},~{}G^{2}_{jkl},~{}G^{3}_{jkl}$ using Construction
3.

15: Using Algorithm 1, find minimum Steiner sets $S^{1}_{jkl}$, $S^{2}_{jkl}$,
and $S^{3}_{jkl}$ for $G^{1}_{jkl},~{}G^{2}_{jkl},$ and $G^{3}_{jkl}$,
respectively.

16: Update $S_{3}=S_{3}\cup\\{S^{1}_{jkl}\cup S^{2}_{jkl}\cup
S^{3}_{jkl}\cup\\{u_{j},u_{k},u_{l}\\}\\}$

17:end for

18:The minimum cardinality set in $S_{1}\cup S_{2}\cup S_{3}$ is $S$.

The proof of correctness of Algorithm 2 follows from Lemmas 2, 3, 4, and 5.
Observe that in Case 1 for $u_{j}\in N_{G}(z)$, the time required for
constructing $G^{1}_{j},~{}G^{2}_{j}$, and $G^{3}_{j}$ is $O(n^{2})$. Finding
the Steiner set for each of $G^{1}_{j},~{}G^{2}_{j}$, and $G^{3}_{j}$ incurs
$O(n^{2})$ time. Thus finding the Steiner set for each $u_{j}\in N_{G}(z)$
incurs $O(n^{3})$ time. Similarly, for Case 2, the time required for
constructing $G^{1}_{jk},~{}G^{2}_{jk}$, and $G^{3}_{jk}$ is $O(n^{2})$.
Finding the Steiner set for each of $G^{1}_{jk},~{}G^{2}_{jk}$, and
$G^{3}_{jk}$ incurs $O(n^{2})$ time. Thus the finding the Steiner set for each
$u_{j},u_{k}\in N_{G}(z)$ incurs $O(n^{4})$ time. Similarly, for the Case 3,
the time required for constructing $G^{1}_{jkl},~{}G^{2}_{jkl}$, and
$G^{3}_{jkl}$ is $O(n^{2})$. Finding the Steiner set for
$G^{1}_{jkl},~{}G^{2}_{jkl}$, and $G^{3}_{jkl}$ incurs $O(n^{2})$ time. Thus
finding the Steiner set for each $\\{u_{j},u_{k},u_{l}\\}\in N_{G}(z)$ incurs
$O(n^{5})$ time. It is clear that the running time of Algorithm 2 is
$O(n^{5})$. Hence the following theorem holds.

###### Theorem 2.9

Let $G$ be a triad-convex split graph. A minimum Steiner set $S$ of $G$ for
$R=I$ can be computed in $O(n^{5})$ time, where $n$ is the number of vertices
in $G$.

Application 2: Circular-convex split graphs

We shall explore the possibility of solving STREE on circular-convex split
graphs using the algorithm of STREE of path-convex split graphs as a black
box. We present a polynomial-time reduction to map the instances of circular-
convex split graphs to the instances of path-convex split graphs. The
reduction is similar to the reduction presented in [12].
Let $G$ be a circular-convex split graph with $|K|=m$ and $|I|=n$. Let the
circular ordering $\prec$ on $I$, say $x_{1}\prec x_{2}\prec\ldots\prec
x_{m}\prec x_{m+1}=x_{1}$, such that for each $v\in K$, $N^{I}_{G}(v)$ is a
circular arc. For each $v\in K$, let $N^{I}_{G}(v)$ be
$\\{x_{a},x_{a-1},\ldots,x_{b-1},x_{b}\\}$, and $l(u)=x_{a}$, $r(u)=x_{b}$.
The following lemma is a key result for our reduction to work.

###### Lemma 6

Let $G$ be a circular-convex split graph. Let $S$ be a minimum Steiner set of
$G$ for $R=I$. Then, for a vertex $z\in I$, $1\leq|N_{G}(z)\cap S|\leq 2$.

###### Proof

It is clear that for every vertex $z\in R$, $|N_{G}(z)\cap S|\geq 1$.
Suppose that $|N_{G}(z)\cap S|\geq 3$. We observe that $N^{I}_{G}(N_{G}(z))$
is a circular arc in $I$ containing $z$. Let the endpoints of that circular
arc be $x_{i},x_{j}$, for some $i,j$, $1\leq i<j\leq n$. Then there exist two
vertices $w_{k},w_{l}\in N_{G}(z),~{}w_{k},w_{l}\in K,~{}1\leq k<l\leq m$ such
that $x_{i}\in N_{G}(w_{k})$ and $x_{j}\in N_{G}(w_{l})$. It is clear that
$N_{G}(w_{k})\cup N_{G}(w_{l})=N^{I}_{G}(N_{G}(z))$. Consider
$S^{\prime}=(S\setminus N_{G}(z))\cup\\{w_{k},w_{l}\\}$. Note that
$|S^{\prime}|\leq|S|-1$, which is a contradiction that $S$ is a minimum
Steiner set of $G$ for $R=I$. ∎

The above lemma indicates either $|N_{G}(z)\cap S|=1$ or $|N_{G}(z)\cap S|=2$.
Accordingly, for each circular-convex split graph, we construct a
corresponding path-convex split graph as part of Construction 4 and
Construction 5 which are explained below. Further, using our construction and
Algorithm 1. We obtain a polynomial-time algorithm for circular-convex split
graphs. We choose an arbitrary vertex, say $x_{i}$ from $I$. Since $x_{i}\in
R$, we have the following cases:

Case 1: Exactly one neighbor of $x_{i}$ is in $S$.
Case 2: Exactly two neighbors of $x_{i}$ is in $S$.

Let $N_{G}(x_{i})=\\{u_{1},\ldots,u_{s}\\}$. For each $u_{j}\in N_{G}(x_{i})$,
$1\leq j\leq s$, $A(u_{j})$ represents a minimum Steiner set of $G$ for $R=I$
containing $u_{j}$. For each $u_{j},u_{k}\in N_{G}(x_{i})$, $1\leq j<k\leq s$,
$A(u_{j},u_{k})$ represents a minimum Steiner set of $G$ for $R=I$ containing
$u_{j},u_{k}$.
Computation of minimum Steiner sets for Case 1 and Case 2.
In each of the two cases, corresponding to the circular-convex split graph
$G$, we define a path-convex split graph.
Case 1: Exactly one neighbor of $x_{i}$ is in $S$.
Construction 4: We define the graph $G_{j}$ as follows;
For each $u_{j}\in N_{G}(x_{i}),1\leq j\leq s$, we do the following:
Let the endpoints of $N^{I}_{G}(u_{j})$ be $l(u)=x_{a},r(u)=x_{b}$. Since
$N_{G}(x_{i})\setminus\\{u_{j}\\}$ is not in $S$, using the graph
$G-(N_{G}(x_{i}))$, we construct $G_{j}$ as follows; $V(G_{j})=(V(G)\setminus
N_{G}[x_{i}])\cup\\{\alpha_{1},\alpha_{2},\beta_{1},\beta_{2}\\}$,
$K_{j}=(K\cap V(G_{j}))\cup\\{\alpha_{1},\alpha_{2}\\}$, $I_{j}=(I\cap
V(G_{j}))\cup\\{\beta_{1},\beta_{2}\\}$, and $E(G_{j})=\\{\\{x,y\\}\mid x,y\in
V(G_{j}),\\{x,y\\}\in E(G)\\}\cup\\{\\{\alpha_{1},p\\},\\{\alpha_{2},p\\}\mid
p\in(K\cap V(G_{j}))\\}\cup\\{\\{\alpha_{1},q\\},\\{\alpha_{2},r\\}\mid
q\in\\{x_{a},x_{a+1},\ldots,x_{i-1}\\},~{}r\in\\{x_{i+1},\ldots,x_{b-1},x_{b}\\}\\}\cup\\{\\{\alpha_{1},\beta_{1}\\},\\{\alpha_{2},\beta_{2}\\},\\{\alpha_{1},\alpha_{2}\\}\\}$.

###### Lemma 7

$G_{j}$ is a path-convex split graph.

###### Proof

We prove that $G_{j}$ is a path-convex split graph, by providing a linear
ordering $\sigma$ on $I$. The ordering $\sigma$ on $I$ is $\beta_{2}\prec
x_{i+1}\ldots\prec x_{b}\prec\ldots\prec x_{a}\prec\ldots
x_{i-1}\prec\beta_{1}$. We can observe that for every $v\in K_{j}$,
$N_{G_{j}}(v)$ is consecutive in $\sigma$. Therefore, $G_{j}$ is a path-convex
split graph. ∎

Let $S_{j}$ be a minimum Steiner set $S_{j}$ of $G_{j}$ for $R=I_{j}$ is
obtained using Algorithm 1. Then a minimum Steiner set of $G$ for $R=I$
containing $u_{j}$ is $A(u_{j})=S_{j}\cup\\{u_{j}\\}$ and the proof for
minimality of $A(u_{j})$ is established in Lemma 8.

###### Lemma 8

For some $u_{j}\in N_{G}(x_{i})$, if $N_{G}(x_{i})\cap S=\\{u_{j}\\}$ then
$|S|=|S_{j}|-1$.

###### Proof

We know that $S_{j}$ is a minimum Steiner set of $G_{j}$ for $R=I$ containing
$\alpha_{1},~{}\alpha_{2}$. Construct the graph $G^{\prime}_{j}$ from $G_{j}$
as follows;
$V(G^{\prime}_{j})=(V(G_{j})\setminus\\{\alpha_{1},\alpha_{2},\beta_{1},\beta_{2}\\})\cup\\{u_{j},x_{i}\\}$,
and $E(G^{\prime}_{j})=\\{\\{u_{j},p\\}\mid p\in(N_{G_{j}}(\alpha_{1})\cup
N_{G_{j}}(\alpha_{2}))\\}\cup\\{\\{x,y\\}\mid x,y\in
V(G^{\prime}_{j}),~{}\\{x,y\\}\in E(G_{j})\\}\cup\\{\\{x_{i},q\\}\mid
q\in(N_{G_{j}}(\beta_{1})\cup N_{G_{j}}(\beta_{2}))\\}\cup\\{\\{u_{j},r\\}\mid
r\in K_{j}\\}$. The set
$(S_{j}\setminus\\{\alpha_{1},~{}\alpha_{2}\\})\cup\\{u_{j}\\}$ is a Steiner
set of $G^{\prime}_{j}$ for $R=I$. Observe that $G^{\prime}_{j}$ is a subgraph
of $G$, and $V(G)=V(G^{\prime}_{j})\cup N_{G}(x_{i})$. Since $u_{j}$ connects
$N_{G}[x_{i}]$, the set
$(S_{j}\setminus\\{\alpha_{1},~{}\alpha_{2}\\})\cup\\{u_{j}\\}$ is also a
Steiner set of $G$. For any minimum Steiner set $S$ of $G$ containing $u_{j}$
for $R=I$, clearly, $|S|\leq|S_{j}|-1$.

Suppose that $S$ is a minimum Steiner set of $G$ for $R=I$ such that $S\cap
N_{G}(x_{i})=u_{j}$. Consider the graph
$G^{\prime}=G-(N_{G}(x_{i})\setminus\\{u_{j}\\})$. Observe that $S$ is a
Steiner set of $G^{\prime}$ for $R=I$. Now we construct $G_{j}$ from
$G^{\prime}$ by using Construction 4. For $G_{j}$ the set
$(S\setminus\\{u_{j}\\})\cup\\{\alpha_{1},~{}\alpha_{2}\\}$ is a minimum
Steiner set for $R=I$. Hence for a minimum Steiner set $S_{j}$ of $G_{j}$,
$|S_{j}|\leq|S|+1$.
Thus $|S|=|S_{j}|-1$. ∎

Case 2: Exactly two neighbors of $x_{i}$ is in $S$.
Construction 5: We define the graph $G_{jk}$ as follows;
For each $u_{j},u_{k}\in N_{G}(x_{i}),~{}1\leq j<k\leq s$, we do the
following:
Let the endpoints of $N^{I}_{G}(u_{j})\cup N^{I}_{G}(u_{k})$ be
$l(u)=x_{a},~{}r(u)=x_{b}$. Since
$(N_{G}(x_{i}))\setminus\\{u_{j},u_{k}\\})\cap S=\emptyset$, from the graph
$G-(N_{G}(x_{i})\setminus\\{u_{j},u_{k}\\})$, we construct $G_{jk}$ as
follows;
$V(G_{jk})=(V(G)\setminus(N_{G}[x_{i}]\setminus\\{u_{j},u_{k}\\}))\cup\\{\beta_{1},\beta_{2}\\}$
with $K_{jk}=(K\cap V(G_{jk}))$, $I_{jk}=(I\cap
V(G_{jk}))\cup\\{\beta_{1},\beta_{2}\\}$, and $E(G_{jk})=\\{\\{x,y\\}\mid
x,y\in V(G_{jk}),~{}\\{x,y\\}\in E(G)\\}\cup\\{\\{u_{j},p\\},\\{u_{k},q\\}\mid
p\in\\{x_{a},x_{a+1},\ldots,x_{i-1}\\},~{}q\in\\{x_{i+1},\ldots,x_{b-1},x_{b}\\}\\}\cup\\{\\{u_{j},\beta_{1}\\},\\{u_{k},\beta_{2}\\}\\}$.

###### Lemma 9

$G_{jk}$ is a path-convex split graph.

###### Proof

We prove that $G_{jk}$ is a path-convex split graph, by providing a linear
ordering $\sigma$ on $I$. The ordering $\sigma$ on $I$ is $\beta_{2}\prec
x_{i+1}\ldots\prec x_{b}\prec\ldots\prec x_{a}\prec\ldots
x_{i-1}\prec\beta_{1}$. We can observe that for every $v\in K_{jk}$,
$N_{G_{jk}}(v)$ is consecutive in $\sigma$. Therefore, $G_{jk}$ is a path-
convex split graph. ∎

Let $S_{jk}$ be a minimum Steiner set of $G_{jk}$ for $R=I_{jk}$ is obtained
using Algorithm 1. Then a minimum Steiner set of $G$ for $R=I$ containing
$u_{j},u_{k}$ is $A(u_{j},u_{k})=S_{jk}$, and the proof for minimality of
$A(u_{j})$ is established in Lemma 10.

###### Lemma 10

For some $u_{j},u_{k}\in N_{G}(x_{i})$, if $N_{G}(x_{i})\cap
S=\\{u_{j},u_{k}\\}$ then $|S|=|S_{jk}|$.

###### Proof

We know that $S_{jk}$ is a minimum Steiner set of $G_{jk}$ for $R=I_{jk}$
containing $u_{j},~{}u_{k}$. Construct the graph $G^{\prime}_{jk}$ from
$G_{jk}$ as follows;
$V(G^{\prime}_{jk})=(V(G_{jk})\setminus\\{\beta_{1},\beta_{2}\\})\cup\\{x_{i}\\}$,
and $E(G^{\prime}_{jk})=\\{\\{x,y\\}\mid\\{x,y\\}\in E(G_{jk}),~{}x,y\in
V(G^{\prime}_{jk})\\}\cup\\{\\{x_{i},q\\}\mid q\in(N_{G_{jk}}(\beta_{1})\cup
N_{G_{jk}}(\beta_{2}))\\}$ with
$I^{\prime}_{jk}=(I_{jk}\setminus\\{\beta_{1},\beta_{2}\\})\cup\\{x_{i}\\}$.
The set $S_{jk}$ is a Steiner set of $G^{\prime}_{jk}$ for
$R=I^{\prime}_{jk}$. Observe that $G^{\prime}_{jk}$ is a subgraph of $G$, and
$V(G)=V(G^{\prime}_{jk})\cup N_{G}(x_{i})$. Since $u_{j},~{}u_{k}$ connects
$x_{i}$ and $N^{I}_{G_{jk}}(N_{G_{jk}}(x_{i}))$ , the set $S_{jk}$ is also a
Steiner set of $G$. For any minimum Steiner set $S$ of $G$ containing
$u_{j},~{}u_{k}$ for $R=I$, clearly, $|S|\leq|S_{jk}|$.

Suppose that $S$ is a minimum Steiner set of $G$ for $R=I$ such that $S\cap
N_{G}(x_{i})=\\{u_{j},u_{k}\\}$. Consider the graph
$G^{\prime}=G-(N_{G}(x_{i})\setminus\\{u_{j},u_{k}\\})$. Observe that $S$ a
Steiner set of $G^{\prime}$ for $R=I$. Now we construct $G_{jk}$ from
$G^{\prime}$ by using Construction 5. For $G_{jk}$, $S$ is a Steiner set for
$R=I$. Hence for a minimum Steiner set $S_{jk}$ of $G_{jk}$,
$|S_{jk}|\leq|S|$.
Thus $|S|=|S_{jk}|$. ∎

We shall present an algorithm to find a minimum Steiner set of $G$ for $R=I$.

Algorithm 3 STREE for circular-convex split graphs.

1:Input: A connected circular-convex split graph $G$, $R=I$.

2:Let $S=\emptyset$, $S_{1}=\emptyset$, $S_{2}=\emptyset$.

3:Choose an arbitrary vertex, say $x_{i}\in I$.

4:for all $u_{j},~{}u_{j}\in N_{G}(x_{i})$ do

5: Construct $G_{j}$ using construction 4.

6: Using Algorithm 1, find a minimum Steiner set $S_{j}$ of $G_{j}$ for
$R=I_{j}$.

7: Update$S_{1}=S_{1}\cup\\{S_{j}\\}$.

8:end for

9:for all $u_{j},u_{k},~{}u_{j},u_{k}\in N_{G}(x_{i})$ do

10: Construct $G_{jk}$ using construction 5.

11: Using Algorithm 1, find a minimum Steiner set $S_{jk}$ of $G_{jk}$ for
$R=I_{j}$.

12: Update $S_{2}=S_{2}\cup\\{S_{jk}\\}$.

13:end for

14:The minimum cardinality set among $S_{1}\cup S_{2}$ is $S$.

The proof of correctness of Algorithm 3 follows from Lemmas 6, 8, 10. Observe
that in Case 1 for $u_{j}\in N_{G}(z)$, the time required for constructing
$G_{j}$ is $O(n^{2})$. Finding the Steiner set for $G_{j}$ incurs $O(n^{2})$
time. Thus finding the Steiner set for each $u_{j}\in N_{G}(z)$ incurs
$O(n^{3})$ time. Similarly, for Case 2, the time required for constructing
$G_{jk}$ is $O(n^{2})$. For finding the Steiner set for $G_{jk}$ incurs
$O(n^{2})$ time. Thus finding the Steiner set for each $u_{j},u_{k}\in
N_{G}(z)$ incurs $O(n^{4})$ time. It is clear that the running time of
Algorithm 2 is $O(n^{4})$. Hence the following theorem holds.

###### Theorem 2.10

Let $G$ be a circular-convex split graph. A minimum Steiner set $S$ of $G$ for
$R=I$ can be computed in $O(n^{4})$ time, where $n$ is the number of vertices
in $G$.

Having analyzed the P-versus-NPC status of STREE for convex split graphs with
convexity on $I$, we shall now analyze the same with respect to split graphs
having convexity on $K$.

###  2.2 STREE in split graphs with convexity on $K$

When we refer to convex split graphs in this section, we refer to convex split
graphs with convexity on $K$. For STREE on split graphs with convexity on $K$,
we establish hardness results for chordal-convex split graphs, and polynomial-
time algorithms for tree-convex, and circular-convex split graphs.

####  2.2.1 Tree-convex split graphs

In this section, we present a polynomial-time algorithm to find a minimum
Steiner tree on tree-convex split graphs. Let $G$ be a tree-convex split graph
with an imaginary tree $T$ on $K$. We present a polynomial-time algorithm to
find a Steiner set $S$ of $G$ for $R=I$. We work with the underlying imaginary
tree $T$ on $K$ to compute $S$ for $R$. As part of our algorithm to compute
$S$, we color vertices of $T$ (gray, white, and black). Initially, all
vertices in the imaginary tree $T$ are colored gray. The vertex colored gray
is changed to white or black as per the following rules:
Rule 1:(Gray-colored vertex is changed to white) The color of a leaf $u\in T$
is changed to white when there does not exist a pendant vertex in
$N^{I}_{G}(u)$.
Rule 2:(Gray-colored vertex is changed to Black) The color of a leaf $u\in T$
is changed to black when there exists a pendant vertex in $N^{I}_{G}(u)$.
Our algorithm employs Rule 1 and Rule 2 iteratively in computing $S$. To begin
with, we choose an arbitrary leaf vertex, say $u$ in $T$. If Rule 1 is
applicable, then $G$ is modified to $G=G-\\{u\\}$ and $T=T-\\{u\\}$. If Rule 2
is applicable, then $S=S\cup\\{u\\}$ and $G$ is modified to
$G=G-N_{G}^{I}[u]$, $T=T-\\{u\\}$. We continue the process for $|K|-1$ times.
Observe that as per this coloring scheme gray colored vertex is recolored to
white or black. The recoloring happens exactly once for each vertex in $T$.
The vertices that are colored black during the process are included in the set
$S$. We shall now show that the set $S$ is indeed minimum in Theorem 2.11.
Let $G$ be a tree-convex split graph with imaginary tree $T$. Without loss of
generality, we shall arrange the vertices in $T$ (with the assumption that $T$
is a rooted tree) as per BFS order $(w_{1},\ldots,w_{m})$. Let the vertices in
Level $i$ be $V_{i}$, $1\leq i\leq k,~{}k$ denotes the height of $T$ such that
the root is in level 1. Let $S=(a_{1},\ldots,a_{p})$ denotes vertices chosen
by our algorithm. Let $S^{\prime}=(b_{1},\ldots,b_{q})$ denote any optimal
Steiner of $G$.
Since $S$ is an optimal Steiner set, it true that $|S^{\prime}|\leq|S|$. To
show that $|S|=|S^{\prime}|$, we need to prove that $|S^{\prime}|\geq|S|$. We
prove $|S^{\prime}|\geq|S|$ by using Theorem 2.11.

###### Theorem 2.11

For each Level $i,~{}1\leq i\leq k$, $|\bigcup\limits_{i=1}^{k}V_{i}\cap
S^{\prime}|\geq|\bigcup\limits_{i=1}^{k}V_{i}\cap S|$.

###### Proof

On the contrary, $|\bigcup\limits_{i=1}^{k}V_{i}\cap
S^{\prime}|<|\bigcup\limits_{i=1}^{k}V_{i}\cap S|$. Let $j$ be the maximum
level at which $|\bigcup\limits_{i=j}^{k}V_{i}\cap
S^{\prime}|<|\bigcup\limits_{i=1}^{j}V_{i}\cap S|$. Then there exists $v\in K$
such that $v\in V_{j}\cap S$ and $v\notin V_{j}\cap S^{\prime}$. Observe that
the algorithm has included $v$ because of Rule 2 and it is adjacent to a
pendent vertex in $I$, say $z$ in that iteration. since $S^{\prime}$ is an
optimal solution, there exists $u\in(N_{G}(z)\cap S^{\prime})$. It is clear
that $u\notin S$, and $u\in(V_{j+1}\cup\ldots\cup V_{k})$. Without loss of
generality we shall assume that $u$ is in level $r,~{}(j+1)\leq r\leq k$.
Since at level $r$, $u\in(V_{r}\cap S^{\prime})$ and $u\notin(V_{r}\cap S)$,
we continue this for each $v\in(V_{j}\cap S)$ and $v\notin(V_{j}\cap
S^{\prime})$, and it contradicts that $|\bigcup\limits_{i=j}^{k}V_{i}\cap
S^{\prime}|<|\bigcup\limits_{i=j}^{k}V_{i}\cap S|$. We continue this argument
for each level, and stop this argument when we reach level 1. Thus we obtain
$|\bigcup\limits_{i=1}^{k}V_{i}\cap
S^{\prime}|\geq|\bigcup\limits_{i=1}^{k}V_{i}\cap S|$. ∎

It is clear that $|S^{\prime}|\geq|S|$. Therefore, $S$ is also an optimal
solution of $G$.

_Remarks:_ Since STREE on tree-convex split graphs is polynomial-time
solvable, STREE is polynomial-time solvable on well-known special structures
such as path, triad, star, and comb-convex split graphs. It is important to
note that the above approach can be used as a black box for STREE on circular-
convex split graphs.

Application 3: Circular-convex split graphs

We investigate the classical complexity of STREE on circular-convex split
graphs. We shall explore the possibility of solving STREE on circular-convex
split graphs using the algorithm for STREE on path-convex split graphs
(subclass of tree-convex split graphs) as a black box We now provide a
polynomial-time reduction to map the instances of circular-convex split graphs
to the instances of path-convex split graphs. Let $G$ be a circular-convex
split graph with $|K|=m$ and $|I|=n$. Let the circular ordering $\prec$ on
$K$, say $w_{1}\prec w_{2}\prec\ldots\prec w_{t}\prec w_{t+1}=w_{1}$, such
that for each $z\in I$, $N_{G}(z)$ is a circular arc.
The following lemma is a key result for our reduction to work.

###### Lemma 11

Let $G$ be a circular-convex split graph. Let $S$ be a minimum Steiner set of
$G$ for $R=I$. Let the minimum degree vertex in $I$ be $z$. Then,
$1\leq|N_{G}(z)\cap S|\leq 2$.

###### Proof

It is clear that for every vertex $y\in R$, $|N_{G}(y)\cap S|\geq 1$.
Suppose that $|N_{G}(z)\cap S|\geq 3$, where $z$ is the minimum degree vertex
in $I$. Observe that $N_{G}(z)$ is a circular arc in $K$. Let the endpoints of
circular arc obtained by $N_{G}(z)$ be $w_{i},w_{j}$. It is clear that
$N^{I}_{G}(w_{i+1})\cup\ldots\cup N^{I}_{G}(w_{j-1})\subseteq
N^{I}_{G}(w_{i})\cup N^{I}_{G}(w_{j})$. Consider $S^{\prime}=(S\setminus
N_{G}(z))\cup\\{w_{i},w_{j}\\}$. Note that $|S^{\prime}|\leq|S|-1$, which is a
contradiction that $S$ is a minimum Steiner set of $G$ for $R=I$. ∎

The above lemma indicates either $|N_{G}(z)\cap S|=1$ or $|N_{G}(z)\cap S|=2$.
Accordingly for each circular-convex split graph, we construct a corresponding
path-convex split graph as part of Construction 6 and Construction 7 which are
explained below. Further, using our construction and Algorithm 1. We obtain a
polynomial-time algorithm for circular-convex split graphs. We have the
following cases:

Case 1: Exactly one neighbor of $z$ is in $S$.
Case 2: Exactly two neighbors of $z$ is in $S$.

Let $N_{G}(z)=\\{u_{1},\ldots,u_{s}\\}$. For each $u_{j}\in N_{G}(z),~{}1\leq
j\leq s$, $A(u_{j})$ represents a minimum Steiner set of $G$ for $R=I$
containing $u_{j}$. For each $u_{j},u_{k}\in N_{G}(z),1\leq j<k\leq s$,
$A(u_{j},u_{k})$ represents a minimum Steiner set of $G$ for $R=I$ containing
$u_{j},u_{k}$.
Computation of minimum Steiner sets for Case 1 and Case 2.
For each case, we shall construct a path-convex split graph corresponding to
the circular-convex split graph.
Case 1: Exactly one neighbor of $z$ is in $S$.
Construction 6: We define the graph $G_{j}$ as follows;
For each $u_{j}\in N_{G}(z),~{}1\leq j\leq s$, we do the following:
Let $N_{G}(z)$ be $\\{w_{i}=u_{1},\ldots,w_{k}=u_{s}\\}$Since
$(N_{G}(z)\setminus\\{u_{j}\\})\cap S=\emptyset$, we consider the graph
$G_{j}$ with $K_{j}=K\setminus N_{G}(z)$, $I_{j}=I\setminus N^{I}_{G}(u_{j})$,
$E(G_{j})=\\{\\{x,y\\}\mid x,y\in V(G_{j}),~{}\\{x,y\\}\in E(G)\\}$.

###### Lemma 12

$G_{j}$ is a path-convex split graph.

###### Proof

We prove that $G_{j}$ is a path-convex split graph, by providing a linear
ordering $\sigma$ on $K_{j}$. Let the ordering be $w_{i+1}\prec
w_{i+2}\prec\ldots\prec w_{k+1}$. We can observe that for every $y\in I$,
$N_{G_{j}}(y)$ is consecutive in $\sigma$. Therefore $G_{j}$ is a path-convex
split graph. ∎

Let $S_{j}$ be a minimum Steiner set of $G_{j}$ for $R=I_{j}$ is obtained
using the algorithm for STREE on path-convex split graphs (subclass of tree-
convex split graphs).

###### Lemma 13

If $N_{G}(z)\cap S=\\{u_{j}\\}$, then $|S|=|S_{j}|+1$.

###### Proof

Suppose that $S_{j}$ is a minimum Steiner set of $G_{j}$ for $R=I$. Construct
$G^{\prime}_{j}$ as follows;
$V(G^{\prime}_{j})=V(G_{j})\cup\\{u_{j}\\}\cup\\{z\\}$ and
$E(G^{\prime}_{j})=E(G_{j})\cup\\{\\{u_{j},z\\}\\}$ with
$I^{\prime}_{j}=I_{j}\cup\\{z\\}$. Then $S^{\prime}_{j}=S\cup\\{u_{j}\\}$ is a
Steiner set of $G^{\prime}_{j}$ for $R=I^{\prime}_{j}$. Observe that
$G^{\prime}_{j}$ is a subgraph of $G$, and $V(G)=V(G^{\prime}_{j})\cup
N^{I}_{G}(u_{j})\cup N_{G}(z)$. Hence $S=S^{\prime}_{j}$ is also a Steiner set
of $G$ for $R=I$. For any minimum Steiner set $S$ of $G$ for $R=I$ containing
$u_{j}$, clearly, $|S|\leq|S_{j}|+1$.
Suppose that $S$ is a minimum Steiner set of $G$ for $R=I$ such that $S\cap
N_{G}(z)=\\{u_{j}\\}$. Consider the graph $G^{\prime}=G-(N_{G}(z)\cup
N^{I}_{G}(u_{j}))$ with $I^{\prime}_{j}=I\setminus\\{z\\}$. The set
$S\setminus\\{u_{j}\\}$ is a Steiner set of $G^{\prime}$ for
$R=I^{\prime}_{j}$. The resultant graph is $G_{j}$. Thus
$S_{j}=S\setminus\\{u_{j}\\}$ is a minimum Steiner set of $G_{j}$ for $R=I$.
Hence for a minimum Steiner set $S_{j}$ of $G_{j}$, $|S_{j}|\leq|S|-1$.
Therefore, $|S|=|S_{j}|+1$. ∎

Case 2: Exactly two neighbors of $z$ is in $S$.
Construction 7: We define the graph $G^{\prime}$ as follows;
For each $u_{j},u_{k}\in N_{G}(z)$, $1\leq j<k\leq s$, we do the following:
Since $(N_{G}(z)\setminus\\{u_{j},u_{k}\\})\cap S=\emptyset$, from the graph
$G-(N_{G}(z)\setminus\\{u_{j},u_{k}\\})$, we construct $G_{jk}$ as follows;
$V(G_{jk})=K_{jk}\cup I_{jk}$,
$K_{jk}=K\setminus\\{u_{j},u_{j-1},\ldots,u_{k}\\}$,
$I_{jk}=I\setminus(N^{I}_{G}(u_{j})\cup N^{I}_{G}(u_{k}))$,
$E(G_{jk})=\\{\\{x,y\\}\mid x,y\in V(G_{jk}),~{}\\{x,y\\}\in E(G)\\}$.

###### Lemma 14

$G_{jk}$ is a path-convex split graph.

###### Proof

We prove that $G_{jk}$ is a path-convex split graph, by providing a linear
ordering $\sigma$ on $I$. The ordering $\sigma$ on $I$ is $u_{j+1}\prec
u_{j+2}\prec\ldots u_{k+1}$. We can observe that for every $v\in K_{jk}$,
$N_{G_{jk}}(v)$ is consecutive in $\sigma$. Therefore, $G_{jk}$ is path-convex
split graph. ∎

Let $S_{jk}$ be a minimum Steiner set $S_{jk}$ of $G_{jk}$ for $R=I_{jk}$ is
obtained using Algorithm 1.

###### Lemma 15

If $N_{G}(z)\cap S=\\{u_{j},u_{k}\\}$, then $|S|=|S_{jk}|+2$.

###### Proof

We know that $S_{jk}$ is a minimum Steiner set of $G_{jk}$ for $R=I$.
Construct the graph $G^{\prime}_{jk}$ from $G_{jk}$ as follows;
$V(G^{\prime}_{jk})=(V(G_{jk})\cup\\{u_{j},u_{k}\\}$, and
$E(G^{\prime}_{jk})=\\{\\{x,y\\}\mid\\{x,y\\}\in E(G_{jk}),~{}x,y\in
V(G^{\prime}_{jk})\\}\cup\\{\\{z,u_{j}\\},\\{z,u_{k}\\}\\}$. The set
$S^{\prime}_{jk}=S_{jk}\cup\\{u_{j},u_{k}\\}$ is a Steiner set of
$G^{\prime}_{jk}$ for $R=I^{\prime}_{jk}$. Observe that $G^{\prime}_{jk}$ is a
subgraph of $G$, and $V(G)=V(G^{\prime}_{jk})\cup N_{G}(z)$. Since
$u_{j},~{}u_{k}$ connects $N_{G}(z)$, the set $S^{\prime}_{jk}$ is also a
Steiner set of $G$. For any minimum Steiner set $S$ of $G$ containing
$u_{j},~{}u_{k}$ for $R=I$, clearly, $|S|\leq|S_{jk}|$.
Suppose that $S$ is a minimum Steiner set of $G$ for $R=I$ such that $S\cap
N_{G}(z)=\\{u_{j},u_{k}\\}$. Consider the graph
$G^{\prime}=G-(N_{G}(z)\setminus\\{u_{j},u_{k}\\})$. Observe that $S$ a
Steiner set of $G^{\prime}$ for $R=I$. Now we construct $G_{jk}$ from
$G^{\prime}$ by using Construction 5. For $G_{jk}$, $S$ is a Steiner set for
$R=I$. Hence for a minimum Steiner set $S_{jk}$ of $G_{jk}$,
$|S_{jk}|\leq|S|$.
Thus $|S|=|S_{jk}|$ ∎

Now we shall present an algorithm for finding the minimum Steiner set of $G$
for $R=I$.

Algorithm 4 STREE for circular-convex split graphs.

1:Input: A connected circular-convex split graph $G$ with $R=I$.

2:Let $S=\emptyset$, $S_{1}=\emptyset$, $S_{2}=\emptyset$.

3:Choose the minimum degree vertex, say $z\in I$.

4:for all $u_{j},~{}u_{j}\in N_{G}(z)$ do

5: Construct $G_{j}$ using Construction 6.

6: Using Algorithm 1, find a minimum Steiner set $S_{j}$ of $G_{j}$ for
$R=I_{j}$.

7: Update $S_{1}=S_{1}\cup\\{S_{j}\\}$.

8:end for

9:for all $u_{j},u_{k},~{}u_{j},u_{k}\in N_{G}(z)$ do

10: Construct $G_{jk}$ using Construction 7.

11: Using Algorithm 1, find a minimum Steiner set $S_{jk}$ of $G_{jk}$ for
$R=I_{jk}$.

12: Update $S_{2}=S_{2}\cup\\{S_{jk}\\}$.

13:end for

14:The minimum cardinality set among $S_{1}\cup S_{2}$ is $S$.

The proof of correctness of Algorithm 4 follows from Lemmas 13, 15. Observe
that in Case 1 for $u_{j}\in N_{G}(z)$, the time required for constructing
$G_{j}$ is $O(n^{2})$. Finding the Steiner set for $G_{j}$ incurs $O(n^{2})$
time. Thus finding the Steiner set for each $u_{j}\in N_{G}(z)$ incurs
$O(n^{3})$ time. similarly, the time required for constructing $G_{jk}$ is
$O(n^{2})$. For finding the Steiner set for $G_{jk}$ incurs $O(n^{2})$ time.
Thus finding the Steiner set for each $u_{j},u_{k}\in N_{G}(z)$ incurs
$O(n^{4})$ time. It is clear that the running time of Algorithm 2 is
$O(n^{4})$. Hence the following theorem holds.

###### Theorem 2.12

Let $G$ be a circular-convex split graph. A minimum Steiner set $S$ of $G$ for
$R=I$ can be computed in $O(n^{4})$ time, where $n$ is the number of vertices
in $G$.

It turns out that STREE is Polynomial-time solvable on tree-convex and
circular-convex split graphs. Further, we explore the classical complexity of
STREE on a convex split graph having a chordal graph as its imaginary
structure in the next section.

####  2.2.2 Chordal-convex split graph

We have seen that STREE on tree-convex split graphs is polynomial-time
solvable. It is natural to ask; ”Is there a property $\pi$ such that STREE on
$\pi$-convex split graphs is NP-complete?” We consider one such property
namely, chordality, and show that STREE on chordal-convex split graphs is NP-
complete.

###### Definition 3

A split graph $G$ is called chordal-convex split graph with convexity on $K$,
if there is an associated chordal graph $G^{\prime}$ defined on $K$, such that
for each $v\in I$, $N_{G}(v)$ induces a subchordal graph in $G^{\prime}$.

###### Theorem 2.13

STREE on a chordal-convex split graph with convexity on $K$ is NP-complete.

###### Proof

STREE is in NP Given an input instance $(G,R,k)$ of STREE, and a certificate
set $S\subseteq V(G)$. By using graph traversal algorithms the connectedness
of the graph induced on $R\cup S$ can be verified in deterministic polynomial
time.
STREE is NP-Hard It is known [1], that STREE on split graphs is NP-complete
and this can be reduced in polynomial time to STREE on the chordal-convex
split graph using the following reduction. We map an instance $(G,R,k)$ of
STREE on split graphs to the corresponding instance
$(G^{*},R^{*},k^{\prime}=k)$ of STREE on the chordal-convex split graph as
follows:
$V(G^{*})=V_{1}\cup V_{2}\cup V_{3}$,
$V_{1}=\\{w_{i}\mid v_{i}\in V(G)\cap K\\}$,
$V_{2}=\\{y_{i}\mid v_{i}\in V(G)\cap I\\}$,
$V_{3}=\\{x_{i}\mid v_{i}\in V(G)\cap I\\}$.
We shall now describe the edges of $G^{*}$,
$E(G^{*})=E_{1}\cup E_{2}$,
$E_{1}=\\{\\{w_{i},w_{j}\\},\\{w_{i},y_{k}\\},\\{y_{k},y_{l}\\}\mid 1\leq
i<j\leq m,1\leq k<l\leq n\\}$,
$E_{2}=\\{\\{w_{i},x_{j}\\},\\{x_{j},y_{j}\\}\mid\\{w_{i},x_{j}\\}\in
E(G),~{}w_{i},y_{j}\in K^{*},~{}x_{j}\in I^{*}\\}$.
We define $K=V_{1}\cup V_{2}$, $I=V_{3}$, and an imaginary split graph
$G^{\prime}$ with clique $K^{\prime}$ and independent set $I^{\prime}$ on
$K^{*}$ is defined with split graph $G$ as an imaginary structure.
An example is illustrated in Figure 5, the STREE in split graph with $k=2$ is
mapped to STREE on chordal-convex split graph with $R=\\{x_{i}\mid x_{i}\in
I\\}$, $k^{\prime}=2$.

Figure 5: An example: STREE in split graphs reduces to STREE on the chordal-
convex split graph.

Claim 2.13.1. $G^{*}$ is a chordal-convex split graph.

###### Proof

For each $x_{i}\in V_{3}$, $N_{G}(x_{i})\subseteq K^{*}$, $K^{*}=V_{1}\cup
V_{2}$. By our construction, $x_{i}$ is adjacent to a subset of vertices in
$K^{\prime}$. Therefore, the graph induced on $N_{G}(x_{i})$ is a split graph
in $G^{\prime}$. Hence $G^{*}$ is a chordal-convex split graph. ∎

Claim 2.13.2. STREE $(G,R,k)$ if and only if STREE $(G^{*},R^{*},k^{\prime})$.

###### Proof

Since $N_{G}(I)\setminus N_{G}(I^{*})=\emptyset$ and $N_{G}(I^{*})\setminus
N_{G}(I)=\emptyset$, $S$ is the Steiner set of $G$ is also the Steiner set of
$G^{*}$. Similarly, $S^{*}$ is the Steiner set of $G$. ∎

Thus we conclude STREE is NP-Hard on the chordal-convex split graph.
Therefore, STREE is NP-complete on chordal-convex split graphs. ∎

Note that yet another natural P-versus-NPC line we can observe from this paper
is that the tree-convex split graph with convexity on $I$ is NP-complete
whereas the tree-convex split graph is polynomial-time solvable.

##  3 Application 4: Domination and its variants

In this section, we prove that the solution to DS, TDS, and CDS, can be
obtained from STREE of a convex split graph for $R=I$. Let $G$ be some convex
split graph. It is known [8], that a minimum Steiner set is also a minimum
dominating set on the class of split graphs. Hence the result is true for a
subclass of split graphs as well. We also show that for a split graph $G$ if
dominating set $S\subseteq K$, then $S$ is also a Steiner set of $G$ for
$R=I$, which we prove in the following claim.

###### Claim 3.1

$S\subseteq K$ is a minimum dominating set if and only if for the Steiner tree
problem when $R=I$, $S\subseteq K$ is the Steiner solution.

###### Proof

Let $S$ be a minimum dominating set of $G$. We know that $S\subseteq K\cup I$.
Suppose that $S\cap I\neq\emptyset$, then let $S\cap
I=\\{x_{1},x_{2},\ldots,x_{l}\\}$. Including any one neighbor for each of
$x_{1},x_{2},\ldots,x_{l}$ in $S$ and removing
$\\{x_{1},x_{2},\ldots,x_{l}\\}$ from $S$ is also a minimum dominating set of
$G$. Hence $S$ is also a minimum Steiner set for $R=I$.
Conversely, For the Steiner tree problem Since $S$ is a minimum Steiner set
for $R=I$, it is clear that $S$ dominates all of $I$. The vertices in
$K\setminus S$ are dominated by vertices in $S$. Hence $S$ is also a minimum
dominating set.
Therefore, $S\subseteq K$ is a minimum dominating set if and only if for the
Steiner tree problem when $R=I$, $S\subseteq K$ is the Steiner solution. ∎

Since $S\subseteq K$, by the definition of CDS, and TDS, $S$ is also a
connected dominating set and total dominating set. The minimality of CDS and
TDS can be proved similar to Claim 3.1. Therefore, the following results hold;

  * •

DS for star-convex split graphs with convexity on $I$ and comb-convex split
graphs with convexity on $I$ is NP-complete. Hence DS is NP-complete for a
tree-convex split graph with convexity on $I$.

  * •

DS for path-convex and triad-convex split graphs with convexity on $I$ is
polynomial-time solvable.

  * •

DS for a tree-convex split graph with convexity on $K$ is polynomial-time
solvable.

  * •

DS for a circular-convex split graph with convexity on $K$ is polynomial-time
solvable.

  * •

DS for a chordal-convex split graph with convexity on $K$ is NP-complete.

The P-versus-NPC status of STREE for split graphs with convex properties
discussed in this paper also holds for DS, CDS, and TDS.

##  4 Parameterized results

In this section, we analyze the parameterized complexity of the Steiner tree
problem on split graphs. We wish to identify the tractability vs
intractability status of the Steiner tree problem on split graphs.
In this section, we ask the following two questions and answer them;

_Whether the parameterized version of Steiner tree problem is tractable or
intractable for split graphs?_
We answer this question by proving that the parameterized version of Steiner
tree problem with solution size as the parameter for split graphs, is
W[2]-hard. The parameterized version of Steiner tree problem which we
considered with solution size being parameter $k$ (PSTREE3) is defined below:

_PSTREE3 $(G,R,k)$_ Instance: A split graph $G$, a terminal set $R=I$.
Parameter: A positive integer $k$. Question: Is there a set $S\subseteq
V(G)\setminus R$ such that $|S|\leq k$, and $G[S\cup R]$ is connected ?

###  4.1 W-hardness of STREE on split graphs

In this section, we show that PSTREE3 on split graphs is in W[2]-hard. We know
that the dominating set problem on split graphs is known to be W[2]-hard [16].
We give a polynomial-time reduction from the parameterized version of
dominating set problem for split graphs to PSTREE2.

###### Theorem 4.1

For split graphs, PSTREE3 is W[2]-hard.

###### Proof

We prove this by giving a reduction from the parameterized version of
dominating set problem on split graphs. We map an instance $(G,k)$ of the
parameterized version of dominating set problem on split graphs to the
corresponding instance $(G,R,k)$ of PSTREE2.
We show that $G$ has a dominating set of size $k$ if and only if $G$ for $R=I$
has a Steiner set of size $k$.
_Only if:_ Let $D$ be a dominating set of size $k$ in $G$. If $D\cap
I\neq\emptyset$, then by using Claim 3.1, we obtain $S$ whose cardinality is
equal to the cardinality of $D$. Clearly, $|S|=k$.
_if:_ From [8], it is known that $S$ is a dominating set for $G$.
Therefore, PSTREE2 is W[2]-hard. ∎

Further we ask;

_Does there exists a parameter for which the corresponding parameterized
version of the Steiner tree problem on split graphs is in FPT?_
We prove that for the parameters such as (i)the treewidth, and (ii) the
solution size and the maximum degree of $I$, then the parameterized version of
Steiner tree problem for split graphs is in FPT.
The parameterized version of Steiner tree problem with parameter the treewidth
$r$ of $G$ (PSTREE4) is defined below:

_PSTREE3 $(G,R,k)$_ Instance: A split graph $G$, a terminal set $R=I$.
Parameter: The treewidth $r$ of $G$. Question: Is there a set $S\subseteq
V(G)\setminus R$ such that $|S|\leq k$, and $G[S\cup R]$ is connected ?

The parameterized version of Steiner tree problem with parameters $k$ and $d$
(PSTREE5) is defined below:

_PSTREE5 $(G,R,k)$_ Instance: A split graph $G$, a terminal set $R=I$.
Parameter: A positive integer $k$, and the maximum degree $d$ of $I$.
Question: Is there a set $S\subseteq V(G)\setminus R$ such that $|S|\leq k$,
and $G[S\cup R]$ is connected ?

We show that PSTREE4, PSTREE5 are FPT in the following section.

###  4.2 FPT algorithms for the parameterized version of the Steiner tree
problem on split graphs

####  4.2.1 FPT algorithm for PSTREE4 on split graphs with treewidth as the
parameter

In this section, we show that PSTREE4 on split graphs exhibits an FPT
algorithm when the parameters are the treewidth and the solution size. It is
known that STREE can be solved in $3^{|R|}n^{O(1)}$ on general graphs. We show
that PSTREE4 on split graphs can be solved in $2^{|K|}n^{O(1)}$.
We use the bounded search tree technique for solving PSTREE4. We shall
describe our branching algorithm; Given an instance $(G,R,r)$, we recursively
branch by two cases by considering $v\in K$ is in $S$ or not in $S$. At any
iteration, if $N^{I}_{K}(v)$ contains a pendant vertex, then the branch is for
one case $v\in K$ is in $S$. In the branch where $v\in S$, we delete
$v,~{}N^{I}_{G}(v)$ from $G$ and reduce the parameter by 1. In the second
branch, we delete $v$ from $G$ and the parameter remains the same. Suppose
that $d^{I}_{G}(v)=1$, then the second branch is not possible.

###### Lemma 16

The solution set $S$ obtained from the above strategy is a minimum Steiner set
of $G$ for $R=I$.

###### Proof

Since $R=I$, $S\subseteq K$. Let $|I|=m$. By our approach, we choose an
arbitrary vertex in $v\in K$ such that $d^{I}_{G}(v)\neq 0$, and we branch by
having $v\in S$ and another branch with $u\notin S$. We can observe that
length of the tree is $|K|$ and the number of leaves is at most $2^{|K|}$. For
each vertex $u\in K$, we explore the two possibilities, hence one of the paths
from the root to the leaf is having minimum Steiner solution. ∎

Observe that by this approach we list all feasible solutions. Note that the
length of the tree is $|K|$ and the number of leaves is at most $2^{|K|}$. The
running time of the algorithm is bounded by the number of nodes ($2^{|K|}$)
and the time is taken at each node $n^{c}$, where $c$ is a constant. The
algorithm runs in time $2^{|K|}n^{O(1)}$.

####  4.2.2 FPT algorithm for PSTREE5 on split graphs with the maximum degree
of $I$ and $|S|$ as the parameter

In this section, we show that PSTREE5 admits a kernel of size
$(2d-1)k^{(d-1)}+k$. It is known [21], that $d$-hitting set guarantees a
kernel whose order does not exceed $(2d-1)k^{d-1}+k$. The parameterized
version of $d$-hitting set can be stated as follows:

_d-Hitting set $(\mathcal{C},P,k)$_ Instance: A collection $\mathcal{C}$ of
subsets of size $d$ obtained from a set $P$. Parameter: A positive integer
$k$, cardinality of every element in $\mathcal{C}$ is $d$ . Question: Does
$\mathcal{C}$ have a hitting set of size $k$ or less ?

We show that PSTREE 5 is FPT by using the FPT algorithm of $d$-hitting set as
a black box. Let $d=max(d_{G}(x_{1}),\ldots d_{G}(x_{m}))$ be the maximum
degree among vertices in $I=\\{x_{1},x_{2},\ldots,x_{m}\\}$. We convert a
given split graph $G$ into a split graph $G^{\prime}$ with $d$ as the degree
of every vertex $z\in I$ as follows;
Let $Y=y_{1},y_{2},\ldots,y_{k}$ be the vertices in $I$ whose degree is less
than $d$. Then $V(G^{\prime})=V(G)\cup
U,~{}U=\\{u_{i1},u_{i2},\ldots,u_{i(d-d_{G}(y_{i}))}\mid y_{i}\in Y,~{}1\leq
i\leq k\\},E(G^{\prime})=\\{\\{x,y\\}\mid x,y\in V(G^{\prime}),~{}\\{x,y\\}\in
E(G)\\}\cup\\{\\{y_{i},u_{ij}\\}\mid y_{i}\in Y,~{}u_{ij}\in U,~{}1\leq i\leq
k,~{}1\leq j\leq d-d_{G}(y_{i})\\}\cup\\{\\{x,y\\}\mid x\in(V(G^{\prime})\cap
K),~{}u\in U\\}$. Observe that $K^{\prime}=K\cup U$, and $I^{\prime}=I$.

We transform an instance of a split graph $G^{\prime}$ with each $z\in I$ of
degree $d$ into the corresponding instance of $d$-hitting set with
$\mathcal{C}$ as a collection of subsets of a set $P$ as follows:
The set $P=\\{w_{i}\mid w_{i}\in K^{\prime}\\}$, and collection
$\mathcal{C}=\\{A_{i}\mid A_{i}=N_{G^{\prime}}(x_{i}),~{}x_{i}\in
I^{\prime}\\}$. Since for each $z\in I$, have degree $d$, for each
$A_{i}\in\mathcal{C},~{}1\leq i\leq m$, it is clear that cardinality of
$A_{i}$ is $d$.
It is known that $d$-hitting set admits a kernel of size $(2d-1)k^{d-1}+k$, by
using the following lemma we prove that $(G^{\prime},R^{\prime},k)$ admits a
kernel of size $(2d-1)k^{d-1}+k$.

###### Lemma 17

If $(\mathcal{C},P,k)$ admits a kernel of size $(2d-1)k^{d-1}+k$, then
$(G^{\prime},R^{\prime}=I,k)$ admits a kernel of size $(2d-1)k^{d-1}+k$.

###### Proof

Since we have a kernel for $(\mathcal{C},P,k)$, we construct a kernel for
$(G^{\prime},R^{\prime}=I^{\prime},k)$ as follows; For each element
$\mathcal{C}$ in the crown reduction, we replace it with the corresponding
$N_{G^{\prime}}(x_{i})$, and for each element $P$ in the crown reduction, we
replace it with the corresponding vertex $w_{j}\in K$. This if
$(\mathcal{C},P,k)$ admits a kernel of size $(2d-1)k^{d-1}+k$, then we can
transform the kernel such that $(G^{\prime},R^{\prime}=I,k)$ admits a kernel
of size $(2d-1)k^{d-1}+k$. ∎

###### Theorem 4.2

There is a polynomial-time algorithm that, for an arbitrary instance $(G,R,k)$
of PSTREE5, either determines that it is a no instance or computes a kernel
instance whose order is bounded above by $(2d-1)k^{d-1}+k$.

###### Proof

Theorem holds because of [21] and Lemma 17. ∎

From Theorem 17, it is clear that we can obtain solution to $(G^{\prime},R,k)$
in time $O(2^{(2d-1)k^{d-1}+k}n^{c})$, where $c$ is a constant (by using
brute-force approach for the kernel). We do a polynomial-time transform from
the solution $S^{\prime}$ of $G^{\prime}$ for $R=I^{\prime}$ to the solution
$S$ of $G$ for $R=I$ as follows;
If $S^{\prime}\cap U=\emptyset$, then $S=S^{\prime}$ is the Steiner of $G$ for
$R=I$. Suppose that $S^{\prime}\cap U\neq\emptyset$. Let
$\\{a_{1},\ldots,a_{q}\\},~{}q\geq 1$ be the vertices in $S^{\prime}\cap U$.
By the construction of $G^{\prime}$, we know that $d^{I}_{G}(a_{i})=1$,
$a_{i}\in(S^{\prime}\cap U)$. Assume that $a_{1},\ldots,a_{q}$ is included in
$S^{\prime}$ in order to connect $y_{1},\ldots,y_{q}$. We know that
$d_{G^{\prime}}(y_{i})\geq 2$ in $G^{\prime}$, $1\leq i\leq q$, $y_{i}$ is
adjacent to at least one vertex in $\\{w_{1},\ldots,w_{n}\\}\cap K$. Assume
without loss of generality that $y_{i}$ is adjacent to $w_{i},~{}1\leq i\leq
q\leq n$. We construct $S$ of $G$ for $R=I$ as follows; $S=(S^{\prime}\cap
V(G))\cup\\{w_{i}\mid\\{w_{i},y_{i}\\}\in
E(G)\land(N_{G^{\prime}}(y_{i})\cap(S^{\prime}\cap U)\neq\emptyset)\\}$.
Observe that $S\subseteq K$ and for each $z\in R$, $S\cap
N_{G}(z)\neq\emptyset$. Thus $S$ is a Steiner set of split graph $G$ for
$R=I$. Therefore, $(G,R,k)$ can be solved in time
$O(2^{(2d-1)k^{d-1}+k}n^{c})$, where $c$ is a constant.

##  5 Approximation algorithm for Domination on split graphs

From [22], the dominating set problem has $\log n$ approximation algorithm on
general graphs, and it does not admit $(1-\epsilon)\log n$-approximation
algorithm in polynomial time on general graphs, for any $\epsilon>0$, unless
NP $\subseteq$ DTIME $(n^{O(\log\log n)})$. Further, it is known [23], that
the dominating set problem is NP-complete on split graphs, and we are
interested in analyzing the approximation algorithm for the dominating set
problem on split graphs. In this section, we show that the dominating set
problem has a $2-\frac{1}{|I|}$ approximation algorithm in polynomial time for
split graphs. Further, it is important to highlight that in [2], it
incorrectly claimed that split graphs does not admit $(1-\epsilon)\log
n$-approximation algorithm in polynomial time, for any $\epsilon>0$, unless NP
$\subseteq$ DTIME $(n^{O(\log\log n)})$.

###### Lemma 18

The dominating set problem has $2-\frac{1}{|I|}$ approximation algorithm in
polynomial time for split graphs.

###### Proof

Since the Steiner set $S$ obtained for STREE of $G$ for $R=I$ is a subset of
$K$, $S$ is also a dominating set. We know that STREE has $2-\frac{1}{|R|}$
approximation algorithm in polynomial time, where $R=I$ for split graphs.
Hence we also have $2-\frac{1}{|I|}$ approximation algorithm in polynomial
time for split graphs. ∎

##  6 Other cases of STREE

Having seen STREE of $G$ for $R=I$, we now consider STREE of $G$ for other
cases of $R$. Interestingly for all other cases, the solution can be obtained
using the solution of STREE of $G$ for $R=I$ as a black box.
_Case 1:_ $R=K$ or $R\subset K$.
Observe that $G[R]$ is connected. Therefore, Steiner set $S$ is an empty set.
_Case 2:_ $R\subset I$.
For $R\subset I$, we transform the graph $G$ to $G^{\prime}$; $V(G^{\prime})$
with $K^{\prime}=K$, $I^{\prime}=I\cap R$, $E(G^{\prime})=\\{\\{u,v\\}\mid
u,v\in V(G^{\prime}),\\{u,v\\}\in E(G)\\}$, and $R^{\prime}=I^{\prime}$.
Observe that $R^{\prime}\setminus R=\emptyset$ and $R\setminus
R^{\prime}=\emptyset$. Thus, the solution of $(G^{\prime},R^{\prime})$ is
precisely the solution to $(G,R)$.
_Case 3:_ $R\cap K\neq\emptyset$ and $R\cap I\neq\emptyset$.
Similar to Case 2, we obtain the solution for this case using the following
transformation. Let $W=R\cap K$, and let $X=I\cap R$. Let $G^{\prime}$ be the
transformed graph $V(G^{\prime})$ with $K^{\prime}=K\setminus W$ and
$I^{\prime}=X\setminus(N^{I}_{G}(W))$, $E(G^{\prime})=\\{\\{u,v\\}\mid u,v\in
V(G^{\prime}),\\{u,v\\}\in E(G)\\}$, and $R^{\prime}=X$. We map the solution
of $(G^{\prime},R^{\prime})$ to the solution of $(G,R)$ as $S=S^{\prime}\cup
W$. Observe that $(S)\cap N_{G}(z)\neq\emptyset,~{}z\in I$. Thus for $(G,R)$,
$S$ is the Steiner set.

Conclusions and directions for further research:
We have proved the classical complexity of STREE, and domination and its
variants on tree-convex and circular-convex split graphs. The results
presented in this paper can be used as a framework for the Steiner tree
variants (Steiner path and cycle) and the domination problems (outer-connected
domination, Roman domination) restricted to split, and bipartite graphs.
We have given a $2-\frac{1}{|I|}$approximation algorithm for DS on split
graphs, and it would be interesting to explore whether
$c-\frac{1}{|I|}$-approximation algorithm, $1<c<2$ is possible for STREE and
DS on split graphs.
We proved that the parameterized version of Steiner tree problem on split
graphs with parameter being solution is W[2]-hard, and with respect to the
parameters such as (i) the treewidth and the solution size, and (ii) the
maximum degree of $I$ and the solution size, we have shown that their
corresponding parameterized version of the Steiner tree problem is FPT. One
can look into other parameters of the Steiner tree problem on a split graph
and analyze their parameterized complexity.
Furthermore, one can analyze the classical complexity for STREE and DS
restricted to split graphs with convexity properties other than path, triad,
star, comb, tree, and circular. This would open up some new subclasses of
split graphs having nice structural properties.

## References

  * [1] Kevin White, Martin Farber, and William Pulleyblank.  Steiner trees, connected domination and strongly chordal graphs.  Networks, 15(1):109–124, 1985.
  * [2] M. Chlebík and J. Chlebíková.  Approximation hardness of dominating set problems in bounded degree graphs.  Information and Computation, 206(11):1264–1275, 2008.
  * [3] Haiko Müller and Andreas Brandstädt.  The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs.  Theoretical Computer Science, 53(2-3):257–265, 1987.
  * [4] Joseph A Wald and Charles J Colbourn.  Steiner trees, partial 2–trees, and minimum IFI networks.  Networks, 13(2):159–167, 1983.
  * [5] Joseph A Wald and Charles J Colbourn.  Steiner trees in outerplanar graphs.  In Proc. 13th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, pages 15–22, 1982.
  * [6] A Mohanapriya, P Renjith, N Sadagopan, et al.  Steiner Tree in $k$-star Caterpillar Convex Bipartite Graphs–A Dichotomy.  arXiv preprint arXiv:2107.09382, 2021.
  * [7] Markus Chimani, Petra Mutzel, and Bernd Zey.  Improved Steiner tree algorithms for bounded treewidth.  Journal of Discrete Algorithms, 16:67–78, 2012.
  * [8] P Renjith and N Sadagopan.  The Steiner tree in $K_{1,r}$-free split graphs—A Dichotomy.  Discrete Applied Mathematics, 280:246–255, 2020.
  * [9] Peter Damaschke, Haiko Müller, and Dieter Kratsch.  Domination in convex and chordal bipartite graphs.  Information Processing Letters, 36(5):231–236, 1990.
  * [10] BS Panda and Juhi Chaudhary.  Dominating induced matching in some subclasses of bipartite graphs.  Theoretical Computer Science, 885:104–115, 2021.
  * [11] Hao Chen, Zihan Lei, Tian Liu, Ziyang Tang, Chaoyi Wang, and Ke Xu.  Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs.  Journal of Combinatorial Optimization, 32(1):95–110, 2016.
  * [12] Arti Pandey and BS Panda.  Domination in some subclasses of bipartite graphs.  Discrete Applied Mathematics, 252:51–66, 2019.
  * [13] Wei Jiang, Tian Liu, and Ke Xu.  Tractable feedback vertex sets in restricted bipartite graphs.  In International Conference on Combinatorial Optimization and Applications, pages 424–434. Springer, 2011.
  * [14] Wei Jiang, Tian Liu, Tienan Ren, and Ke Xu.  Two hardness results on feedback vertex sets.  In Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, pages 233–243. Springer, 2011.
  * [15] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  Introduction to algorithms.  MIT press, 2009.
  * [16] Venkatesh Raman and Saket Saurabh.  Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles.  Algorithmica, 52(2):203–225, 2008.
  * [17] Stuart E Dreyfus and Robert A Wagner.  The Steiner problem in graphs.  Networks, 1(3):195–207, 1971.
  * [18] Michael Dom, Daniel Lokshtanov, and Saket Saurabh.  Incompressibility through colors and ids.  In International Colloquium on Automata, Languages, and Programming, pages 378–389. Springer, 2009.
  * [19] Michael R Garey.  Computers and intractability: A Guide to the Theory of NP-Completeness.  WH Freeman & Co, 1979.
  * [20] Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, and Saket Saurabh.  Unique covering problems with geometric sets.  In International Computing and Combinatorics Conference, pages 548–558. Springer, 2015.
  * [21] Faisal N. Abu-Khzam.  A kernelization algorithm for d-hitting set.  Journal of Computer and System Sciences, 76(7):524–531, 2010.
  * [22] Vijay V Vazirani.  Approximation algorithms, volume 1.  Springer, 2001.
  * [23] Alan A. Bertossi.  Dominating sets for split and bipartite graphs.  Information Processing Letters, 19(1):37–40, 1984.