In this paper we explore the general conditions in order that a two-dimensional natural Hamiltonian system possess a second invariant which is a polynomial in the momenta and is therefore Liouville integrable. We examine the possibility that the invariant is preserved by the Hamiltonian flow on a given energy hypersurface only (weak integrability) and derive the additional requirement necessary to have conservation at arbitrary energy (strong integrability). Using null complex coordinates, we show that the leading order coefficient of the polynomial is an arbitrary holomorphic function in the case of weak integrability and a polynomial in the coordinates in the strongly integrable one. We review the results obtained so far with strong invariants up to degree four and provide some new examples of weakly integrable systems with linear and quadratic invariants. (C) 2005 American Institute of Physics.