Note on the hardness of generalized connectivity

Note on the hardness of generalized connectivity

0.00 Avg rating0 Votes
Article ID: iaor20125713
Volume: 24
Issue: 3
Start Page Number: 389
End Page Number: 396
Publication Date: Oct 2012
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: graphs
Abstract:

Let G be a nontrivial connected graph of order n and let k be an integer with 2≤kn. For a set S of k vertices of G, let κ(S) denote the maximum number 𝓁 of edge‐disjoint trees T 1,T 2,…,T 𝓁 in G such that V(T i )⋂V(T j )=S for every pair i,j of distinct integers with 1≤i,j𝓁. Chartrand et al. generalized the concept of connectivity as follows: The kconnectivity, denoted by κ k (G), of G is defined by κ k (G)=min{κ(S)}, where the minimum is taken over all k‐subsets S of V(G). Thus κ 2(G)=κ(G), where κ(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.

Reviews

Required fields are marked *. Your email address will not be published.