The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E)G=(V,E) be a simple undirected graph with a set V of vertices and a set E   of edges. Each vertex v∈Vv∈V has an integer valued demand d(v)⩾0d(v)⩾0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S   of vertices with the minimum cardinality such that there are at least d(v)d(v) vertex-disjoint paths between S   and each vertex v∈V-Sv∈V-S. In this paper, we show that the problem with d(v)⩽3d(v)⩽3, v∈Vv∈V can be solved in linear time. Moreover, we show that in the case where d(v)⩾4d(v)⩾4 for some vertex v∈Vv∈V, the problem is NP-hard.