A methodology for algorithmic construction of Lyapunov functions for problems concerning the stability of an equilibrium with respect to part of the system variables is proposed. This methodology utilizes the previously developed sum of squares technique to determine Lyapunov certificates. Conditions for stability with respect to part of the variables are developed that allow for Lyapunov functions to be determined in terms of a sum of squares. Asymptotic stability conditions in terms of sum of squares polynomials are developed for autonomous and non-autonomous systems. An example is presented which demonstrates the methodology and gives insight into the new stability conditions. (C) 2008 Elsevier Ltd. All rights reserved.