  NP-hard problems such as the maximum clique or minimum vertex cover problems,
two of Karp's 21 NP-hard problems, have several applications in computational
chemistry, biochemistry and computer network security. Adiabatic quantum
annealers can search for the optimum value of such NP-hard optimization
problems, given the problem can be embedded on their hardware. However, this is
often not possible due to certain limitations of the hardware connectivity
structure of the annealer. This paper studies a general framework for a
decomposition algorithm for NP-hard graph problems aiming to identify an
optimal set of vertices. Our generic algorithm allows us to recursively divide
an instance until the generated subproblems can be embedded on the quantum
annealer hardware and subsequently solved. The framework is applied to the
maximum clique and minimum vertex cover problems, and we propose several
pruning and reduction techniques to speed up the recursive decomposition. The
performance of both algorithms is assessed in a detailed simulation study.
