Transformations to and from MAXIMUM CLIQUE.
Variation in which the degree of the graphs
is bounded by
the constant B is APX-hard and is approximable within B+1.
If the induced subgraph is restricted to be connected the problem is
NPO PB-complete and not approximable within