On the max min vertex cover problem