Dichotomy study of the Steiner tree problem in split-like graphs
May 28, 2026
Abstract
Given a connected graph \(G\) and a terminal set \(R \subseteq V(G)\), the minimum Steiner tree problem (ST) asks for a tree that spans all of \(R\) with at most \(r\) vertices from \(V(G)\backslash R\), for some integer \(r\geq 0\). A split graph is a graph which can be partitioned into a clique and an independent set. It is known from (Garey et al.,1977 [1]) that ST is NP-complete, even for split graphs [2]. We introduce the class of split-like graphs which unifies several known graph classes like bipartite graphs, split graphs, and bisplit graphs [3], allowing for a cohesive study across multiple structural constraints.
We investigate the computational complexity of the Steiner tree problem under structural constraints, specifically \(K_{1,r}\)-free, bounded diameter, chordality and star-convexity. Through reductions (primarily from Exact-3-Cover and its variants), the paper establishes a series of dichotomy results.
It precisely gives the boundary for \(K_{1,r}\)-free bipartite graphs: ST is in P for \(r \le 3\) and NP-complete for \(r \ge 4\); whereas on \(K_{1,r}\)-free bisplit graphs, ST is in P for any fixed \(r\geq 3\). On bisplit graphs, the Steiner tree problem admits a polynomial-time solution when the diameter is 2. In contrast, for diameters 3 and 4, the problem is NP-complete. The problem is NP-complete under star convexity constraints on the independent set. When star convexity is imposed on the \(k\)-clique side, the problem is solvable in polynomial time. The problem is NP-complete on chordal bipartite graphs and chordal split graphs (i.e., split graphs themselves), while polynomial-time algorithms exist for other subclasses of split-like graphs.
1 Introduction↩︎
The Steiner tree problem is one of the most important combinatorial optimization problems, which can be used as a model in many fields, such as global routing, network routing, VLSI design, optical and wireless communication systems, transportation and distribution networks, and phylogenetic tree reconstruction. It is one among 21 NP-complete problems listed by Karp [4].The Steiner tree problem is a common term for a class of combinatorial optimization problems defined in various settings. Generally speaking, this problem requires an optimum interconnect for a given set of points under a predefined objective function.
Given a connected edge-weighted graph \(G\) and a subset of vertices \(R \subseteq V(G)\) called terminals, the objective is to find a tree \(T\) that spans all vertices in \(R\) while minimizing the total weight of the edges in \(T\). In the unweighted setting, the goal becomes minimizing either the number of edges in the Steiner tree or the number of additional vertices \(Q \subseteq V(G) \setminus R\) (called Steiner vertices) used to connect the terminals. ST generalizes two well-known problems: the Minimum Spanning Tree when \(R = V(G)\), and the Shortest Path problem when \(|R| = 2\). In this paper, we shall work with the unweighted version of the problem. All graphs in this paper are assumed to be simple unweighted connected unless explicitly mentioned otherwise.
Since ST is a hard problem for general graphs, it has been studied in different graph classes as well as for approximation results. ST remains NP- complete even on graph classes like Planar [5], Bipartite [4], Split [2] and Chordal bipartite graphs [6]. While the problem is solvable in polynomial time for certain graph classes, such as Series Parallel [7], Strongly Chordal [2], Permutation [8] and Circle graph [9].
A Split graph is a graph that can be partitioned into a clique and an independent set. A star \(K_{1,r}\) is a complete bipartite graph with one of the partition contains only one vertex and other contains \(r\) vertices. ST in \(K_{1,4}\)-free split graphs is polynomial-time solvable and NP-complete in \(K_{1,5}\)-free split graphs [10]. We are trying to extend this dichotomy to more general graph class namely split-like graphs. We define a split-like graph as a graph \(G\) which can be partitioned into two sets \(K\) and \(I\), where \(I\) is an independent set and the induced subgraph of \(K\) is a complete graph or complete \(k\)-partite graph, for some \(k\geq 1\). For each \(k = 1, 2, \dots\), the instances are distinct; one is not contained in another. Split-like graph is perfect, which is a popular graph class, for every induced sub graph, chromatic number is same as clique number.
We study the classical complexity of ST on split-like graphs subject to four structural parameters: the exclusion of the star \(K_{1,r}\) as a forbidden induced subgraph for some \(r\geq 3\), a bounded diameter \(d\geq 2\), chordality and star-convexity. The dichotomy results are presented explicitly in Table [tab:dichotomy1], Table [tab:dichotomy2] and Table [tab:dichotomy3] .
| Chordal | Triangle free | Bipartite | Split | Bisplit | Trisplit | |
| (T1) | [10] | (T2) | (T5) | |||
| \(r=3\) | Open | NPC[11] | P | P | P | P |
| \(r=4\) | NPC (C2) | NPC | NPC | P | P | P |
| \(r=5\) | NPC | NPC | NPC | NPC | P | P |
| Bipartite | Split | Bisplit | Bipartite Bisplit | Trisplit | |
| [3] | |||||
| \(d=2\) | P | P | P | P | P |
| \(d=3\) | Open | NPC[2] | NPC (P6) | P | NPC(P8) |
| \(d=4\) | NPC[4] | - | NPC | NPC | NPC(P7) |
| \(d=5\) | Open | - | - | - | - |
| Bipartite | Split | Bisplit | Bipartite Bisplit | Trisplit | |
|---|---|---|---|---|---|
| chordal | NPC[6] | NPC | P[3] | P[3] | P(T9) |
| star convex | NPC(T13) | NPC[12] | NPC (T15) | Open | NPC |
| (I/K) | P | P (T14) | P | P |
1.1 Preliminaries↩︎
In this paper, we work with connected, simple, unweighted graphs. For a graph \(G\), the vertex set is \(V(G)\) and the edge set is \(E(G) = \{(u,v) | u,v \in V(G)\) and \(u\) is adjacent to \(v \in G\) and \(u\neq v\}\). The neighborhood of a vertex \(v\) denoted by \(N_G(v)=\{u|\{u,v\}\in E(G)\}\). The degree of a vertex \(v\) is \(deg_G(v)=|N_G(v)|\). For a graph \(G\) and \(S\subseteq V(G)\), \(G[S]\) represents the subgraph of \(G\) induced on the vertex set \(S\). The diameter of a graph is the farthest distance between any two of its vertices.
A bipartite graph \(G=A\cup B\) is such that \(V(G)\) can be partitioned into two independent sets \(A\) and \(B\). \(K_{m,n}\) is a complete bipartite graph with \(|A|=m\) and \(|B|=n\). A split graph \(G=K+ I\) is such that \(V(G)\) can be partitioned into a clique \(K\) and an independent set \(I\). A bisplit graph \(G=[A\cup B]+ I\) is such that \(V(G)\) can be partitioned into three independent sets \(A\),\(B\) and \(I\), such that \(G[A\cup B]\) is a complete bipartite graph.
We define split-like graph as a graph \(G\) which can be partitioned into two sets \(K\) and \(I\), where \(I\) is an independent set and the induced subgraph \(G[K]\) is a complete graph or complete \(k\)-partite graph, for some \(k\geq 1\). For a complete graph or \(k=1,2\), \(G\) is a split graph, a bipartite graph and a bisplit graph, respectively. For all other values of \(k\), the graph is referred to as a \(k\)-split graph (in particular, when \(k=3\), we refer to the graph as a Trisplit graph for convenience).
A \(H\)-free graph is a graph that does not contain \(H\) as an induced subgraph. A graph is chordal if every cycle of length greater than 3 has a chord. A graph \(G\) is a chordal bipartite graph if \(G\) is bipartite and every cycle of length greater than 4 has a chord.
A split-like graph \(G(K,I)\) is called a \(\pi\)-convex graph with convexity on \(K\) if there exists an associated structure \(\pi = (K, F)\) such that for each \(v \in I\), its neighborhood \(N^K_G(v)\) induces a connected subgraph in \(\pi\). Similarly,
we define \(\pi\)-convex graph with convexity on \(I\). \(\pi\) can be structures like tree, star, path, cycle,
etc.
We now formally define the minimum Steiner tree problem.
2 Steiner tree problem in split-like graphs↩︎
2.1 \(K_{1,r}\)-free split-like graphs↩︎
ST in \(K_{1,4}\)-free split graphs is polynomial-time solvable and NP-complete in \(K_{1,5}\)-free split graphs[10]. We are trying to extend this study to other split-like graphs. First we are restricting our study to \(K_{1,r}\)-free bipartite graphs, for a fixed \(r \geq 3\). Our dichotomy result establishes that the presence of the claw \(K_{1,3}\) makes the ST computationally hard in bipartite graphs. We start with bipartite graphs, then bisplit and extend to k-split graphs.
Lemma 1. If \(G\) is a \(K_{1,3}\)- free bipartite graph, then \(G\) is either an even cycle or a path.
ST in cycles and paths are polynomial-time solvable, which gives the following result.
Proposition 1. ST in a \(K_{1,3}\)- free bipartite graph is polynomial time solvable.
We now consider the following constrained variant of the Exact-3-Cover problem, which serves as the basis for our reduction showing that ST in a \(K_{1,5}\)- free bipartite graph is NP-Complete.
This problem, abbreviated as \(X3C-3\), is known to be NP-complete [1].
Proposition 2. ST on \(K_{1,5}\)- free bipartite graphs is NP-complete.
Proof. ST is in NP : Given a certificate S, we show that there exists a deterministic polynomial-time algorithm for verifying the validity of the certificate S. Note that the standard Breadth First Search algorithm can be used
to check whether \(S \cup R\) is connected. It is easy to check whether \(|S| \leq k\). Therefore, the certificate verification can be done in \(O(|V(G)| +
|E(G)|)\). Thus, we conclude that the Steiner tree problem is in NP.
ST is NP-Hard: An instance of \(X3C\)-\(3(X,C)\) is reduced to an instance of \(ST(G,R,k)\) as follows: \(A=X,B=\{v_i|c_i\in C\}\) . \(E(G(A \cup B))=\{(v_i,u) | v_i\in B ,u\in A \text{ and } u\in c_i\}\). Now, create a binary tree with \(B\) as leaf nodes: pair two
vertices in \(B\) and introduce a common neighbour. If \(|B|\) is odd, the remaining vertex is made adjacent to a new node. Repeat this process to the new set of nodes until they become
connected. Let \(T\) be the new set of nodes (Figure 2).
\(G(A\cup B\cup T)\) is a \(K_{1,5}-\) free connected bipartite graph: \(G(B\cup T)\) is a binary tree. Therefore, it is a \(K_{1,4}\)- free connected bipartite graph. Now we introduce \(A\) (an independent set) and corresponding edges to \(G(B\cup T)\), which is again a connected
bipartite graph, because each \(u\in A\) is adjacent to at least one \(v_i\in B\). Since each \(u\in B\) is adjacent to exactly three \(v_i\in A\), the maximum degree of a vertex in \(B\) is 4. Also, the degree of a vertex in \(A\) is at most 3. Thus \(G(A\cup B\cup
T)\) is a \(K_{1,5}\)- free connected bipartite graph.
Claim: \(X3C-3(X,C)\) if and only if \(ST(G,R,k)\).
Proof.Necessity: If there exists \(C'\subseteq C\),\(|C'|=\frac{|X|}{3}\) which covers all the elements of \(X\), then the
set of vertices \(S=\{v_i \in B|c_i \in C' \}\) forms a Steiner set in \(G\) with \(R=A\cup T\), where \(|S|=\frac{|X|}{3}\).
Sufficiency: If there exists a Steiner set \(S\subseteq B\) in \(G\) on at most \(k=\frac{|X|}{3}\) Steiner vertices, then \(\forall v\in S, d^{A}(v)=3, |S|=\frac{|X|}{3} \text{ and } N^{A}(S)=X\), which implies that there does not exist \(u,v \in S\) such that \(N^{A}(u)\cap N^{A}(v)\neq
\emptyset\). Therefore the set \(C'=\{c_i\in C|v_i \in S \}\) forms an exact-3-cover of \(X\). ◻
Particularly, ST is NP-complete for a \(K_{1,5}\)- free bipartite graph \(G\) with \(S \subseteq \{v\in G: deg(v)=4\}\). Can be named as ST-P.
Now we reduce this particular version of ST on \(K_{1,5}\)- free bipartite graphs to ST on \(K_{1,4}\)- free bipartite graphs.
Proposition 3. ST on \(K_{1,4}\)- free bipartite graphs is NP-complete.
Proof. An instance of \(ST-P(G,R,k)\) is reduced to an instance of
\(ST(G',R',k')\) as follows: Consider the graph \(G\). Let \(v \in G\) be a vertex of degree 4. We split \(v\)
into two vertices \(v_1\) and \(v_2\) of degree 2. Then add one extra vertex \(u\) and edges \((v_1,u), (w,v_2)\) .
\(G'\) is a \(K_{1,4}\)- free connected bipartite graph:
Since each degree 4 vertex is replaced with a \(P_3\) by splitting the neighbours, \(G'\) is again connected bipartite, and the maximum degree becomes 3 (Figure 3).
Claim: \(ST-P(G,R,k)\) if and only if \(ST(G',R'=R,k'=3k)\).
Necessity: Suppose \(v\) is a vertex in the steiner set \(S\) for \(ST-P(G,R,k)\) then the steiner set \(S'\)
corresponding to \(ST(G',R',k')\) contains the vertices \(v_1,u,v_2\). So for each vertex in \(S\), there will be 3 vertices in \(S'\).
Sufficiency: Only two possibilities for each non-terminal vertices - either all three of \(\{v_1,u,v_2\}\) are in \(S'\) (for each \(v\)) or
none of the vertex are in \(S'\). In first case include the corresponding \(v\) in \(S\) and in second case exclude the corresponding \(v\) from \(S\) . ◻
Combining all these results, we get the following dichotomy
Theorem 1. ST in a \(K_{1,r}\)- free bipartite graph is polynomial time solvable for \(1\leq r\leq3\) and NP- complete for \(r\geq4\).
Now we extend this study to other \(k\)-split graphs. ST was proved to be NP-complete on bisplit graphs [3]. We will show that the problem is NP‑complete on trisplit graphs, and likewise for other \(k\)-split graphs.
Lemma 2. If \(r\) is fixed , the class of \(K_{1,{r}}\)-free bisplit graphs is finite.
Proof. Consider a \(K_{1,{r}}\)-free bisplit graph \(G=A\cup B \cup I\), where \(A\cup B\) forms the biclique. Then \(|A| \leq r-1\) and \(|B| \leq r-1\). If \(|A|= r\), a vertex from \(B\) forms a \(K_{1,{r}}\) with all the vertices of \(A\). Therefore \(|A\cup B| \leq 2(r-1)\). Now suppose \(|I|=2(r-1)^2+1\). Then by the Pigeon Hole Principle, there is a vertex \(v\) in \(A\cup B\) which is adjacent to \(r\) vertices in \(I\), which induces a \(K_{1,{r}}\). So \(|I|\leq 2(r-1)^2\). Thus \(|V(G)| \leq 2(r-1)+2(r-1)^2=2r(r-1)\). Hence, we can conclude that the class of \(K_{1,{r}}\)-free bisplit graphs is finite. ◻
This is an interesting property because for a fixed \(r\), both \(K_{1,{r}}\) -free split graph and \(K_{1,{r}}\) -free bipartite graph are infinite classes.
Theorem 2. If \(r\) is fixed, ST is polynomial time solvable for \(K_{1,{r}}\)-free bisplit graphs.
Now we need to prove that the problem is NP-complete when \(r\) is a variable.
For \(l\geq 3\), often abbreviated as \(XlC\), is known to be NP-complete [5].
Theorem 3. If \(r\) is a variable, then ST is NP-Complete for \(K_{1,{r}}\)-free bisplit graphs.
Proof. An instance of \(XlC(X,C)\) is reduced to an instance of \(ST(G,R,k)\) in \(K_{1,{r}}\)-free bisplit graphs as follows:\(V(G)=A\cup B\cup I \cup I'\) where \(A=\{v_i:c_i \in C\}\), \(B=\{v'_i:c_i \in C\}\), \(I=\{u_i:x_i \in X\}\) and \(I'=\{u'_i:x_i \in X\}\). We construct a biclique on the vertex sets \(A\cup B\). \(E(A\cup I)=\{(v_i,u_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i
\}\) and \(E(B\cup I')=\{(v'_i,u'_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\). Let \(R=I\cup I'\).
\(G\) is a \(K_{1,r}-\) free bisplit graph, where \(r=f(l)\): \(G\) is bisplit with \(A\cup B\) forms a biclique and \(I\cup I'\) forms an independent set. A star with its centre in the independent set has maximum degree \(|C|\) and a star
with its centre in the biclique has maximum degree \(|C|+l\). Therefore \(G\) is \(K_{1,{r}}\)-free, where \(r=|C|+l+1\)
.
Claim:\(XlC(X,C)\) if and only if \(ST(G,R,k)\).
Proof.Necessity: If there exists \(C'\subseteq C\),\(|C'|=\frac{|X|}{l}\) which covers all the elements of \(X\), then the
set of vertices \(S=\{v_i \in A,v'_i \in B |c_i \in C' \}\) forms a Steiner set in \(G\) with \(R=I\cup I'\), where \(|S|=2\frac{|X|}{l}\).
Sufficiency: If there exists a Steiner set \(S\subseteq A\cup B\) in \(G\) on at most \(k=2\frac{|X|}{l}\) Steiner vertices, then \(\forall v\in S, d^{I\cup I'}(v)=l, |S|=2\frac{|X|}{l} \text{ and } N^{A\cup B}(S)=I \cup I'\), which implies that there does not exist \(u,v \in S\) such that \(N^{A\cup B}(u)\cap N^{A\cup B}(v)\neq \emptyset\). Therefore the set \(C'=\{c_i\in C|v_i \in S \}\) forms an exact-l -cover of \(X\).
◻
Now we extend this study to trisplit graphs.
Theorem 4. ST is NP-complete for Trisplit graphs.
Proof. An instance of \(X3C(X,C)\) is reduced to an instance of \(ST(G,R,k)\) in trisplit graphs as follows:\(V(G)=A\cup B\cup D\cup I \cup I'\cup
I''\) where \(A=\{v_i:c_i \in C\}\), \(B=\{v'_i:c_i \in C\}\), \(D=\{v''_i:c_i \in C\}\) \(I=\{u_i:x_i
\in X\}\) ,\(I'=\{u'_i:x_i \in X\}\)and \(I''=\{u''_i:x_i \in X\}\). We construct a triclique on the vertex sets \(A\cup B\cup
D\). \(E(A\cup I)=\{(v_i,u_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\), \(E(B\cup I')=\{(v'_i,u'_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\) and \(E(D\cup I'')=\{(v''_i,u''_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\). \(R=I\cup I'\cup I''\).
\(G\) is a trisplit with independent set \(I\cup I'\cup I''\).
Claim::\(X3C(X,C)\) if and only if \(ST(G,R,k)\).
Proof.Necessity: If there exists \(C'\subseteq C\),\(|C'|=\frac{|X|}{3}\) which covers all the elements of \(X\), then the
set of vertices \(S=\{v_i \in A,v'_i \in B,v''_i \in D |c_i \in C' \}\) forms a Steiner set in \(G\) with \(R=I\cup I'\cup I''\),
where \(|S|=\frac{|X|}{3}\).
Sufficiency: If there exists a Steiner set \(S\subseteq A\cup B\cup D\) in \(G\) on at most \(k=|X|\) Steiner vertices, then \(\forall v\in S, d^{I\cup I'\cup I''}(v)=3, |S|=|X| \text{ and } N^{A\cup B\cup D}(S)=I \cup I'\cup I''\), which implies that there does not exist \(u,v \in S\) such that
\(N^{A\cup B \cup D}(u)\cap N^{A\cup B\cup D}(v)\neq \emptyset\). Therefore the set \(C'=\{c_i\in C|v_i \in S \}\) forms an exact-3 -cover of \(X\). ◻
We are going to explore forbidden subgraphs of Trisplit graphs. We present a result that generalises Lemma 2.
Lemma 3. If \(r\) is fixed , the class of \(K_{1,{r+1}}\)-free trisplit graphs is finite.
Theorem 5. If \(r\) is fixed, ST is polynomial time solvable for \(K_{1,{r}}\)-free trisplit graphs.
Proof. Consider a \(K_{1,{r}}\)-free trisplit graph \(G=A\cup B \cup C \cup I\), where \(A\cup B\cup C\) forms the triclique. Then \(|A| \leq r-1\), \(|B| \leq r-1\) and \(|C| \leq r-1\). If \(|A|= r\), a vertex from \(B\) forms a \(K_{1,{r}}\) with all the vertices of \(A\). Therefore \(|A\cup B\cup C| \leq 3(r-1)\). Now suppose \(|I|=3(r-1)^2+1\). Then by Pigeon Hole Principle, there is a vertex \(v\) in \(A\cup B\cup C\) which is adjacent to \(r\) vertices in \(I\), which induces a \(K_{1,{r}}\). So \(|I|\leq 3(r-1)^2+1\). Thus \(|V(G)| \leq 3(r-1)+3(r-1)^2=3r(r-1)\). Hence, we can conclude that the class of \(K_{1,{r}}\)-free trisplit graphs is finite. ◻
By a similar reduction used for bisplit in Theorem 3, we get the following hardness result.
Theorem 6. ST is NP-complete for \(K_{1,{r}}\)-free Trisplit graphs for a variable \(r\).
2.2 Chordal split-like graphs↩︎
It is known that ST on chordal graphs is NP-complete [2]. Hence, a natural interest is to analyse the complexity of ST on chordal split-like graphs. Since split graphs constitute a proper subclass of chordal graphs, the class of chordal split graphs coincides precisely with the class of split graphs, ST is NP-complete.
Theorem 7. ST on Chordal Bipartite graphs is NP-complete [6].
Theorem 8. ST on Chordal Bisplit graphs is solvable in polynomial time [3].
Lemma 4. A graph \(G\) is a Chordal Trisplit graph if and only if the following properties are satisfied
The triclique in \(G\) is \(K_{1,1,m}\), for some \(m\geq 0\).
For each vertex \(u \in I\), \(deg(u)\leq 3\) and no \(u\in I\) is adjacent to two vertices in a single partition of triclique.
Proof. Necessity: Let \(G=A\cup B \cup C\cup I\) is a Chordal Trisplit graph with \(G[A\cup B \cup C]\) forms a triclique and \(I\) an independent set.
Suppose the triclique has two partitions with at least 2 vertices. Then \(G\) has \(C_4\) as an induced subgraph, which contradicts the fact that \(G\) is a chordal graph.
If \(deg(u)\geq 4\) for some \(u\in I\) , then by the Pigeon Hole Principle \(u\) contains two neighbors in exactly one of the partition \(A, B\text{ or }C\), let it be \(x,y \in B\). Now,both \(x\) and \(y\) are adjacent to an \(z\in A\). Vertices \(u,x,y,z\) induce a \(C_4\) in \(G\), which contradicts that \(G\) is chordal. The same contradiction occurs even if \(deg(u)=2 \text{ or } 3\), but both neighbours are in exactly one of the partitions.
Sufficiency: Suppose \(G\) is a graph satisfying (1) and (2). Clearly, \(G\) is a trisplit graph. Let \(|C|=m\) and having an induced \(C_4=\{a,b,c,d\}\).
Case 1: \(a,c\in I\). Then \(b \text{ and } d\) should be in different partitions of the triclique, by (2). This will induce a chord between \(b \text{ and }
d\), a contradiction.
Case 2: \(a,c\in C\). By (2) \(b, d \notin I\). Then the only possibility is \(b \in B\) and \(d \in A\) (or vice-versa).
But \(b \text{ and } d\) are adjacent, a contradiction. ◻
From this property, we derive the Algorithm 4 to solve ST.
Theorem 9. Finding a minimum Steiner tree on chordal trisplit graphs is solvable in polynomial time.
Proof. For a pendent vertex, its only neighbour should be added to the \(S\). This is ensured by steps 3 and 4. For every other vertex, at least one neighbour must be \(a\) or \(b\). So one of the \(\{S,S\cup \{a\},S\cup \{b\},S\cup \{a,b\}\}\) is the minimum Steiner set. Since we check for the presence of pendant vertices in \(G\), the check can be done in linear time. Thus the time complexity of Algorithm is \(O(n)\), where \(n\) is the number of vertices in \(G\). ◻
We can extend this algorithm for chordal k-split graphs, so:
Theorem 10. Finding a minimum Steiner tree on chordal \(k\)-split graphs is solvable in polynomial time, \(k\geq 2\) is fixed.
The Steiner tree problem in an arbitrary Split graph is NP-complete. Consider a split graph \(G=K+I\) with \(|K|\leq k\). Then, \(G\) can be represented as a \(k\)-split graph in which each partition consists of a single vertex. Also, since a split graph is a chordal graph, \(G\) is a chordal \(k\)-split graph. Then the following result
Theorem 11. ST is NP-complete for chordal \(k\)-split graphs for a variable \(k\).
2.3 ST with diameter as a parameter↩︎
Diameter of a split graph is at most 3, while the diameter of a bisplit graph is known to be at most 4 [3]. But there is no such bound possible for the class of bipartite graphs. Here, we will show that the diameter of a trisplit graph is also at most 4. Then we will study the complexity of ST on such graph classes with diameter as a parameter.
The split graphs instance generated from [2] are split graphs of diameter three. Therefore, for a split graph of diameter three, ST is NP-complete. Also, split graphs of diameter two have a universal vertex. So it is trivial that ST is polynomial-time solvable.
The bipartite graph instance generated from Theorem 13 is of diameter four. Therefore, for a bipartite graph of diameter four, ST is NP-complete. By simple reduction from this problem recursively, it is possible to show that ST is NP-complete for bipartite graph, if the diameter is restricted to 6,8, etc. Bipartite graphs of diameter two are nothing but a complete bipartite graph, for which ST is polynomial-time solvable. The computational complexity of ST on bipartite graphs of diameter 3,5,…remains unsolved.
Lemma 5. A trisplit graph has a diameter of at most four.
Proof. Suppose \(G=A\cup B\cup C + I\) is a trisplit graph with diameter five. Then there exist two vertices \(x,y \in V(G)\) such that \(d(x,y)=5\). If both are from triclique, their distance is at most two. For \(x\in I\) and \(y\in A\cup B\cup C\), \(d(x,y)\leq 3\). Therefore, the only option that remains is \(x,y \in I\). Consider the path \((x,a,b,u,v,y)\) in \(G\). Clearly \(a,v \in A\cup B\cup C\), which contradicts the fact that \(d(a,v)\leq 2\). ◻
Proposition 4. For a bisplit graph of diameter at most four, ST is NP-complete [3].
Proposition 5. A graph \(G=A\cup B\cup I\) is a bisplit graph of diameter at most three, if and only if for any \(x,y \in I\), one of the following properties is satisfied
\(N(x)\cap N(y)\neq \phi\)
\(N(x)\cup N(y) \not\subset A\) and \(N(x)\cup N(y)\not\subset B\)
Proof. Suppose \(G\) is a bisplit graph of diameter at most three. If \(x,y \in I\) such that \(N(x)\cap N(y)= \phi\). Therefore \(d(x,y)\geq 3\). Assume that \(N(x)\cup N(y) \subset A\). Since the distance between any two vertices in \(A\) is two, \(d(x,y)=
4\), a contradiction. Similarly in case of \(B\).
Conversely, assume the given two conditions. Without loss of generality, we consider the following remaining cases
\(N(x)\subseteq A\) and \(N(y)\subseteq B\): then \(d(x,y)= 3\).
\(N(x)\cap A \neq \phi\), \(N(x)\cap B \neq \phi\) and \(N(y)\subseteq B\): then \(d(x,y)= 3\).
\(N(x)\cap A \neq \phi\), \(N(x)\cap B \neq \phi\) and \(N(y)\cap A \neq \phi\), \(N(y)\cap B \neq \phi\) : then \(d(x,y)= 3\).
If both \(x\) and \(y\) are from a biclique, their distance is at most two. For \(x\in I\) and \(y\in A\cup B\), \(d(x,y)\leq 3\). Thus \(G\) is a bisplit graph having a diameter at most three. ◻
In a bisplit graph of diameter two, the presence of a universal vertex directly implies that
Corollary 1. Let \(G\) be a bisplit graph of diameter two, then ST is polynomial-time solvable.
Proposition 6. For a bisplit graph of diameter three, ST is NP-complete.
Proof. An instance of \(X3C(X,C)\) is reduced to an instance of \(ST(G,R,k)\) in bisplit graphs as follows:\(V(G)=A\cup B\cup I\) where \(A=\{v_i:c_i \in C\}\), \(B=\{v'_i:c_i \in C\}\) and \(I=\{u_i:x_i \in X\}\). We construct a biclique on the vertex sets \(A\cup
B\). \(E(A\cup I)=\{(v_i,u_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\), \(E(B\cup I)=\{(v'_i,u_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\). \(R=I\).
By Proposition 5, \(G\) is a bisplit graph of diameter three.
Claim::\(X3C(X,C)\) if and only if \(ST(G,R,k)\).
Proof.Necessity: If there exists \(C'\subseteq C\),\(|C'|=\frac{|X|}{3}\) which covers all the elements of \(X\), then the
set of vertices \(S'=\{v_i \in A|c_i \in C' \}\) covers \(R\), but the induced graph need not be connected. So remove any one vertex \(v_j\) from
\(S'\) and replaced with corresponding \(v'_j\), forms a Steiner set \(S\) in \(G\) for \(R=I\), where \(|S|=\frac{|X|}{3}\).
Sufficiency: If there exists a Steiner set \(S\subseteq A\cup B\) in \(G\) on at most \(k=\frac{|X|}{3}\) steiner vertices, then \(\forall v\in S, d^{I}(v)=3, |S|=|X| \text{ and } N^{A\cup B}(S)=I\), which implies that there does not exist \(u,v \in S\) such that \(N^{A\cup B }(u)\cap N^{A\cup
B}(v)\neq \emptyset\). Therefore the set \(C'=\{c_i\in C|v_i \in S \}\) forms an exact-3 -cover of \(X\).
◻
Since the trisplit graphs instance generated from Theorem 4 are trisplit graphs of diameter at most four, the following result:
Proposition 7. For a trisplit graph of diameter four, ST is NP-complete.
Proposition 5 admits an extension to trisplit graphs, and through the analogous reduction employed in Proposition 6, we can show that
Proposition 8. For a trisplit graph of diameter three, ST is NP-complete.
2.4 Star convex split-like graphs↩︎
If we introduce convex ordering on one of the partitions of a split graph, ST is polynomial-time solvable for tree-convex split graphs with convexity on the clique, whereas ST is NP-complete on tree-convex split graphs with convexity on the independent set [12]. Here, we are going to introduce convex ordering on one of the partitions of a bipartite graph- Star convexity. ST on the Triad convex bipartite graph and circular convex bipartite graph are still open.
Theorem 12. A bipartite graph \(G=X\cup Y\) is a star convex bipartite graph if and only if there exists a vertex \(x\in X\) such that every \(y\in Y\) is either a pendant vertex or is adjacent to \(x\) [13].
Theorem 13. For a star convex bipartite graph, ST is NP-complete.
Proof. An instance of \(X3C(X,C)\) is reduced to an instance of \(ST(G,R,k)\) in star convex bipartite as follows: \(V(G)=A\cup B\cup\{v\}\)
where \(A=\{v_i:c_i \in C\}\) and \(B=\{u_i:x_i \in X\}\). \(E_1=\{(v_i,u_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\) and \(E_2=\{(v,v_i):c_i\in C\}\). \(R=B\cup \{v\}\).
\(G\) is a bipartite graph with partitions \(Z=B\cup \{v\}\) and \(Y=A\). Since every vertex in \(Y\) is adjacent to the
vertex \(v\) in \(Z\), by Proposition 12, \(G\) is a star convex bipartite graph.
Claim: \(X3C(X,C)\) if and only if \(ST(G,R,k)\).
Proof.Necessity: If there exists \(C'\subseteq C\),\(|C'|=\frac{|X|}{3}\) which covers all the elements of \(X\), then the
set of vertices \(S=\{v_i \in A|c_i \in C' \}\) covers \(R\). Since the induced graph is connected \(S\) forms a steiner set \(G\) for \(R=B\), where \(|S|=\frac{|X|}{3}\).
Sufficiency: If there exists a steiner set \(S\subset A\) in \(G\) on at most \(k\) steiner vertices, then \(\forall v\in
S, d^{B}(v)=3 (\text{since } d^{Z}(v)=4), |S|=\frac{|X|}{3} \text{ and } N^{B}(S)=B (\text{since } N^{Z}(S)=R)\), which implies that there does not exist \(u,v \in S\) such that \(N^{ B
}(u)\cap N^{ B}(v)\neq \emptyset\). Therefore the set \(C'=\{c_i\in C|v_i \in S \}\) forms an exact-3 -cover of \(X\).
◻
An analogous result to Theorem 12 holds for bisplit graphs (convexity on biclique and independent side), and more generally for k‑split graphs.
Proposition 9. A bisplit graph \(G=(A\cup B)+ I\) is a star convex bisplit graph (convexity on biclique) if and only if there exists a vertex \(x\in A\cup B\) such that every \(y\in I\) is either a pendant vertex or is adjacent to \(x\).
Consider the Steiner Tree problem on star‑convex bisplit graphs, with convexity defined on the biclique. By the preceding result, for any terminal set \(T\) contained in the independent side (all remaining cases can be reduced to this one), there exists a vertex \(x\) in the biclique such that every non‑pendant vertex is adjacent to \(x\). So the initial Steiner set \(S'\) for the given \(T\) can be formed by collecting all neighbours of pendant vertices, and for non-pendent vertices, add \(x\) to the set. But the induced graph \(G[T\cup S']\) may not be connected. This is because \(S'\) lies entirely within one partition of the biclique. So adding any vertex from the other partition to \(S'\) solves the problem. All this procedure can be done in polynomial time.
Theorem 14. ST on star‑convex bisplit graphs, with convexity defined on the biclique, is polynomial-time solvable.
Theorem 15. ST on star‑convex bisplit graphs, with convexity defined on the independent side, is NP-complete.
Proof. An instance of \(X3C(X, C)\) is reduced to an instance of \(ST(G,R,k)\) in star‑convex bisplit graphs, with convexity defined on the independent side, as follows:\(V(G)=A\cup B\cup I' \cup I'' \cup \{u\}\) where \(A=\{v_i:c_i \in C\}\), \(B=\{v'_i:c_i \in C\}\), \(I'=\{u_i:x_i
\in X\}\) and \(I''=\{u'_i:x_i \in X\}\). We construct a biclique on the vertex sets \(A\cup B\). \(E(A\cup I')=\{(v_i,u_j):c_i\in C, x_j\in
X \text{ and } x_j \in c_i \}\) and \(E(B\cup I'')=\{(v'_i,u'_j):c_i\in C, x_j\in X \text{ and } x_j \in c_i \}\). \(u\) is made universal to all vertices in \(A\cup B\). Let \(R=I\cup I'\cup \{u\}\).
\(G\) is a star‑convex bisplit graph, with convexity defined on the independent side,: \(G\) is bisplit with \(A\cup B\) forms a biclique
and \(I'\cup I''\cup \{u\}\) forms an independent set. Since every vertex of \(A\cup B\) is adjacent to \(u\), by Proposition 9, \(G\) is a star‑convex bisplit graph, with convexity defined on the independent side.
Claim:\(X3C(X,C)\) if and only if \(ST(G,R,k)\).
Proof.Necessity: If there exists \(C'\subseteq C\),\(|C'|=\frac{|X|}{3}\) which covers all the elements of \(X\), then the
set of vertices \(S=\{v_i \in A,v'_i \in B |c_i \in C' \}\) forms a Steiner set in \(G\) with \(R=I'\cup I''\cup\{u\}\), where \(|S|=2\frac{|X|}{3}\).
Sufficiency: If there exists a Steiner set \(S\subseteq A\cup B\) in \(G\) on at most \(k=2\frac{|X|}{3}\) Steiner vertices, then \(\forall v\in S, d^{I'\cup I''}(v)=3, |S|=2\frac{|X|}{3} \text{ and } N^{A\cup B}(S)=R\), which implies that there does not exist \(u,v \in S\) such that \(N^{A\cup B}(u)\cap N^{A\cup B}(v)\neq \emptyset\). Therefore the set \(C'=\{c_i\in C|v_i \in S \}\) forms an exact-3 -cover of \(X\).
◻
Both results can be extended naturally to k-split graphs, \(k\geq 3\).
3 ST in \(K_{1,r}\)-free Chordal graphs↩︎
In Splits graphs, a notable subclass of Chordal graphs, computational hardness starts from \(K_{1,5}\)-free graphs. Consequently, ST is NP-complete even within \(K_{1,5}\)-free chordal graphs. Furthermore, undirected path graphs, which form another strict subclass of chordal graphs, also exhibit NP-completeness for ST [9]. By the prescribed construction, the graph obtained by reduction is \(K_{1,4}\)-free. This will help us to update the dichotomy status of \(K_{1,r}\)-free chordal graphs.
Theorem 16. ST on \(K_{1,4}\)- free undirected path graphs is NP-complete.
Proof. Let \(P = \{p_1, \ldots, p_n\}\), \(Q = \{q_1, \ldots, q_n\}\), and \(R = \{r_1, \ldots, r_n\}\) be disjoint sets, each of cardinality
\(n\), for some positive integer \(n\). Let \(S = \{s_1, \ldots, s_m\} \subseteq P \times Q \times R\) be a subset of cardinality \(m\), for some positive integer \(m\). Define the instance of 3D-Matching as \(I = (P, Q, R, S)\), constituted by the sets \(P, Q,
R\), and \(S\). Construct a graph \(G\) from the instance \(I\) as follows:
For each \(s_j \in S\), define the set \[V_j = \{a_j, b_j, c_j, x_j, y_j, z_j^1, z_j^2, z_j^3\}.\] Define the vertex set of the graph \(G\) as \[V(G) = \bigcup_{j=1}^m V_j \cup P \cup Q \cup R.\]
Let \[K = \bigcup_{s_j \in S} \{a_j, b_j, c_j, x_j\}\] be a clique in \(G\).
For each \(s_j \in S\), the following subsets are cliques in \(G\): \[\{a_j, b_j, x_j, y_j\}, \quad \{a_j, y_j, z_j^1\}, \quad \{b_j, y_j, z_j^2\}, \quad \{c_j, x_j, z_j^3\}.\]
Additionally, for each element:
- \(p_i \in P\), the set \(\{p_i\} \cup \{a_j : p_i \in s_j, s_j \in S\}\) is a clique in \(G\);
- \(q_i \in Q\), the set \(\{q_i\} \cup \{b_j : q_i \in s_j, s_j \in S\}\) is a clique in \(G\);
- \(r_i \in R\), the set \(\{r_i\} \cup \{c_j : r_i \in s_j, s_j \in S\}\) is a clique in \(G\).
It is enough to show that the graph \(G\) obtained by the reduction in [9] is \(K_{1,4}\)-free.
A star with \(p_i\) as center: Maximum induced star is \(K_{1,1}\), because it’s only neighbors \(a_j\) forms a clique in \(G\). Similarly, for a star with \(q_i\) or \(r_i\) as the centre.
A star with \(a_j\) as centre: Since it’s a part of the clique \(K\), at most one neighbour can be taken from that clique set. Each \(a_j\) is adjacent to exactly one \(p_i\), which is non adjacent to \(\cup \{b_j,c_j,x_j\}\). Now take one neighbor from each set \(\{b_j,x_j,y_j\}\) and \(\{z^1_j,y_j\}\). Maximum size independent sets are of size 2: \(\{b_j,z^1_j\}\text{ and }\{x_j,z^1_j\}\). Along with \(p_i\) it induces a \(K_{1,3}\). So the maximum induced star is \(K_{1,3}\). Similarly, for a star with \(b_j\) or \(c_j\) as the centre.
A star with \(x_j\) as centre: Since it’s a part of the clique \(K\), at most one neighbour can be taken from that clique set. Now take one neighbor from each set \(\{a_j,b_j,y_j\}\) and \(\{z^3_j,c_j\}\). Maximum size independent sets are of size 2: are \(\{a_j,z^3_j\},\{y_j,c_j\},\{y_j,z^3_j\}\text{ and }\{b_j,z^3_j\}\), which forms a \(K_{1,2}\). Only for the set \(\{y_j,z^3_j\}\) along with a vertex from \(K\), which is non adjacent to \(y_j\) (i.e. \(y_k\) such that \(k\neq j\)) forms a \(K_{1,3}\). So the maximum induced star is \(K_{1,3}\).
A star with \(y_j\) as center: Take one neighbor from each set \(\{a_j,b_j,x_j\}\) \(\{a_j,z^1_j\}\) and \(\{z^2_j,b_j\}\). Maximum size independent sets are of size 3: \(\{a_j,z^1_j,z^2_j\}\) and \(\{x_j,z^1_j,z^2_j\}\). So the maximum induced star is \(K_{1,3}\).
A star with \(z^1_j\) as centre: Maximum induced star is \(K_{1,1}\), because it’s a part of a single triangle only. Similarly, for a star with \(z^2_j\) or \(z^3_j\) as the centre.
So in all possible cases the maximum induced star in \(G\) is \(K_{1,3}\). ◻
Corollary 2. ST on \(K_{1,4}\)- free chordal graphs is NP-complete.
4 Conclusion↩︎
In this paper, we studied the Steiner tree problem on split-like graphs under the structural constraints - star-free, bounded diameter, chordality and star convexity, which provide several dichotomy results. Beyond star convexity, the problem can also be studied under other convexity frameworks such as triad convexity, tree convexity, comb convexity, etc. All NP-completeness results extend naturally to the weighted version of the Steiner tree problem, whereas the polynomial-time solvable cases must be analyzed separately. The Steiner tree problem remains open for diameter-three bipartite graphs and claw-free chordal graphs. Also we can extend this study to other variants of Steiner tree problem. Furthermore, fixed-parameter tractability (FPT) and approximation algorithms for different graph classes provide promising direction.