Let G = (V,E) be the given graph and GR = (VR,E R) and GC = (VC,EC) be the sub graphs of G such that VR ∩ VC = Φ and V R ∪ VC = V . GC is referred to as the cops region and GR is called as the robber region. Initially a robber is placed at some vertex of VR and the cops are placed at some vertices of V C. The robber and cops may move from their current vertices to one of their neighbours. While a cop can move only within the cops region, the robber may move to any neighbour. The robber and cops move alternatively. A vertex v ∈ VC is said to be attacked if the current turn is the robber's turn, the robber is at vertex u where u ∈ VR, (u, v) ∈ E and no cop is present at v. The guarding problem is to find the minimum number of cops required to guard the graph GC from the robber's attack. We first prove that the decision version of this problem when GR is an arbitrary undirected graph is PSPACE-hard.We also prove that the complexity of the decision version of the guarding problem when GR is a wheel graph is NP-hard. We then present approximation algorithms if GR is a star graph, a clique and a wheel graph with approximation ratios H(n1), 2H(n1) and (H(n1) + 3/2 ) respectively, where H(n1) = 1+ 1/ 2 + ... + 1/ n1 and n1 = |VR|. © Springer-Verlag Berlin Heidelberg 2009.