The complexity of finding optimal subgraphs to represent spatial correlation.

Lee, Meeks and Pettersson recently demonstrated that improved inference for areal unit count data can be achieved by carrying out modifications to a graph representing spatial correlations; specifically, they delete edges of the planar graph derived from border-sharing between geographic regions in order to maximise a specific objective function. In this paper we address the computational complexity of the associated graph optimisation problem, demonstrating that it cannot be solved in polynomial time unless P = NP; we further show intractability for a related but simpler problem.