Hardness results on generalized connectivity

Let $G$ be a nontrivial connected graph of order $n$ and let $k$ be an integer with $2\le k\le n$. For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$denotethemaximumnumber$\ell$ofedge-disjointtrees$T_1,T_2,…,T_\ell$in$G$suchthat$V(T_i)\cap V(T_j)=S$foreverypair$i,j$ofdistinctintegerswith$1\leq i,j\leq \ell$\mathrm{.}Acollection${T_1,T_2,…,T_\ell}$oftreesin$G$ with this property is called an internally disjoint set of trees connecting $S$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by ${\kappa }_k(G)$, of $G$ is defined by ${\kappa }_k(G)=$min$\{\kappa (S)\}$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus ${\kappa }_2(G)=\kappa (G)$, where $\kappa (G)$ is the connectivity of $G$, for which there are polynomial-time algorithms to solve it. This paper mainly focus on the complexity of the generalized connectivity. At first, we obtain that for two fixed positive integers $k_1$ and $k_2$, given a graph $G$ and a $k_1$-subset $S$ of $V(G)$, the problem of deciding whether $G$ contains $k_2$ internally disjoint trees connecting $S$ can be solved by a polynomial-time algorithm. Then, we show that when $k_1$ is a fixed integer of at least 4, but $k_2$ is not a fixed integer, the problem turns out to be NP-complete. On the other hand, when $k_2$ is a fixed integer of at least 2, but $k_1$ is not a fixed integer, we show that the problem also becomes NP-complete. Finally we give some open problems.