Galaxy cutsets in graphs (Q975761)

Given a network \(G=(V(G),E(G))\), a subset of vertices \(S\) of \(V(G)\) that is spanned by a tree of depth at most\( \)r is called to have radius \(r\). The authors discus graphs \(G\) where \(G\) has a cutset that can be written as the union of \(k\) sets of radius \(r\). A cutset which is the union of \(k\) stars is called a galaxy The main result of this paper is the following: It is NP-hard to determine whether a given network contains a galaxy cutset of order \(k\), if k is part of the input.