Dado un gráfico anfitrión conectado G , un límite superior para el grado d y un límite superior para el diámetro k , buscamos el subgrafo más grande S de G con grado máximo como máximo d y diámetro como máximo k .
Este problema también se conoce como problema de subgráfico de diámetro de grado, ya que contiene el problema de diámetro de grado como un caso especial (es decir, al tomar un gráfico completo suficientemente grande como gráfico anfitrión). A pesar de ser una generalización natural del Problema Grado-Diámetro , MaxDDBS solo comenzó a investigarse en 2011, mientras que la investigación en el Problema Grado-Diámetro ha estado activa desde la década de 1960. En cuanto a su complejidad computacional, el problema es NP-hard y no en APX (es decir, no se puede aproximar dentro de un factor constante en tiempo polinomial ).