Sampling and decision problems with connectivity constraints