This work introduces three Quadratic Unconstrained Binary Optimization (QUBO) relaxations for the sparsest k-subgraph (SkS) problem: a quadratic penalty relaxation, a Lagrangian relaxation, and an augmented Lagrangian relaxation. We provide theoretical results identifying the ranges of penalty parameters that ensure exactness of the relaxations. Building on these results, we design three iterative algorithms that update penalty parameters dynamically and approximately solve the internal QUBO problems using simulated annealing and quantum processing units (QPUs). Numerical experiments confirm the theoretical guarantees and showcase the efficiency of the proposed algorithms in practice. The research work of the first three authors was partially supported by the project Quantum Solver for Hard Binary Quadratic Problems (QBIQ), ID J7-50186, funded by the Slovenian Research and Innovation Agency (ARIS), the project DIGITOP, co-funded by the Republic of Slovenia, the Ministry of Higher Education, Science and Innovation, ARIS, and the European Union – NextGenerationEU, and by ARIS through the annual work program of Rudolfovo. The fourth author was funded in part by the Austrian Science Fund (FWF) [10.55776/DOC78]