The pooling problem is a network flow problem with applications in oil refining, petrochemical, and food industry. Resembling the traditional minimum cost flow problem, the objective is to assign flow to the arcs in a network in such a way that the total cost is minimized, and such that supply, demand and capacity bounds are respected. Input data for the pooling problem includes, besides the input required for the minimum cost flow problem, flow qualities for each network source and quality bounds for each network terminal. Quality is typically specified in terms of one or more contaminating component, such as CO2, SO2, etc. When flow streams meet at any network node, the resulting quality becomes the weighted mean value of the qualities of the entering flow streams, where the flow values constitute the weights, and consequently, the problem is naturally formulated as a bilinear program. This extension from the minimum cost flow problem makes the pooling problem strongly NP-hard. In this work, we demonstrate that the strong NP-hardness of the pooling problem persists even when quality is measured in terms of a single parameter. We then suggest some novel lower and upper bounding techniques. The lower bounds are developed through strengthening of certain linear relaxations available in the literature, and the upper bounds are provided by devising fast but not necessarily exact procedures for identifying and improving feasible solutions. Computational experiments are reported.