A fast and automatic method, using machine learning and min-cuts on a sparse graph, for segmenting Liver from CT Contrast enhanced (CTCE) datasets is proposed. The method first localizes the liver by estimating its centroid using a machine learnt model with features that capture global contextual information. Individual ‘N’ rapid segmentations are carried out by running a min-cut on a sparse 3D rectilinear graph placed at the estimated liver centroid with fractional offsets. Edges of the graph are assigned a cost that is a function of a conditional probability, predicted using a second machine learnt model, which encodes relative location along with a local context. The costs represent the likelihood of the edge crossing the liver boundary. Finally, 3D ensembles of ‘N’ such low resolution, high variance sparse segmentations gives a final high resolution, low variance semantic segmentation. The proposed method is tested on three publically available challenge databases (SLIVER07, 3Dircadb1 and Anatomy3) with M-fold cross validation. On the most popular database: SLIVER07 alone, consisting of 20 datasets we obtained a mean dice score of 0.961 with 4-fold cross validation and an average run-time of 6.22s on a commodity hardware (Intel 3.6GHz dual core, with no GPU). On a combined database of 60 datasets from all three, we obtained a mean dice score of 0.934 with 6-fold cross validation.