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?V v ? V has an integer valued demand d(v)?0 d ( 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-S v ? V - S . In this paper, we show that the problem with d(v)?3 d ( v ) ? 3 , v?V v ? V can be solved in linear time. Moreover, we show that in the case where d(v)?4 d ( v ) ? 4 for some vertex v?V v ? V , the problem is NP-hard.
source location problem undirected graph local vertex-connectivity deficient set