The source location problem with local 3-vertex-connectivity requirements (Q2462389)

Given an undirected graph \((V,E)\) and an integer \(d(v)\geq 0\) for each vertex \(v\in V\) the source location problem with vertex-connectivity asks for a subset \(S\subset V\) of minimal cardinality such that for each \(v\in V\setminus S\) at least \(d(v)\) vertex-disjoint paths exist from \(S\) to \(v\). The paper develops a linear time algorithm to solve this problem when \(d(v)\leq 3\) for all \(v\in V\) and proves NP-hardness when \(d\) is surjective \(V\rightarrow \{0,3,4\}\), by reduction from a special type of vertex cover problem.