Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v@?V has an integer valued demand 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) vertex-disjoint paths between S and each vertex v@?V-S. In this paper, we show that the problem with d(v)= =4 for some vertex v@?V, the problem is NP-hard.
['Toshimasa Ishii', 'Hitoshi Fujita', 'Hiroshi Nagamochi']
The source location problem with local 3-vertex-connectivity requirements