A solution to the power flow problem is imperative for many power system applications and several iterative approaches are employed to achieve this objective. However, the chance of finding a solution is dependent on the choice of the initial point because of the non-convex feasibility region of this problem. In this paper, a non-iterative approach that leverages a convexified relaxed power flow problem is employed to verify the existence of a feasible solution. To ensure the scalability of the proposed convex relaxation, the problem is formulated as a sparse semi-definite programming problem. The variables associated with each maximal clique within the network form several positive semidefinite matrices. Perturbation and network reconfiguration schemes are employed to improve the tightness of the proposed convex relaxation in order to validate the existence of a feasible solution for the original non-convex problem. Multiple case studies including an ill-conditioned power flow problem are examined to show the effectiveness of the proposed approach to find a feasible solution.