  The independent set problem, ISP for short, asks for the maximal number of
vertices in a (large) graph which can be occupied such that none of them are
neighbors. We address the question from a statistical mechanics perspective, in
the case of Erdoes-Renyi random graphs. We thereby introduce a Hamiltonian
penalizing configurations which do not satisfy the non-neighboring constraint:
the ground state of the ensuing disordered system corresponds to the solution
of the ISP. Identifying the ground state amounts, in turns, to control the
phase where replica symmetry is broken, which is way beyond our current
understanding. By means of Talagrand's cavity method, we rigorously establish
the existence of a replica symmetry phase, computing, in particular, the free
energy in the limit of large graphs. A conjectural formula for the ground
state, hence for the solution of the ISP, is also derived. Being based on the
Parisi theory, the emerging picture is that of a staggering complexity.
