Note on the hardness of generalized connectivity

作者：Li Shasha; Li Xueliang

来源：Journal of Combinatorial Optimization, 2012, 24(3): 389-396.

DOI：10.1007/s10878-011-9399-x

• k-connectivity
• Internally disjoint trees
• Complexity
• Polynomial-time
• NP-complete

Let G be a nontrivial connected graph of order n and let k be an integer with 2a parts per thousand currency signka parts per thousand currency signn. For a set S of k vertices of G, let kappa(S) denote the maximum number a"" of edge-disjoint trees T (1),T (2),aEuro broken vertical bar,T (a"") in G such that V(T (i) )a (c) V(T (j) )=S for every pair i,j of distinct integers with 1a parts per thousand currency signi,ja parts per thousand currency signa"". 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 determining the generalized connectivity of a graph. 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.

• 出版日期2012-10
• 单位南开大学