Retrait des bords d'un graphique pondéré entièrement connecté

Question

Étant donné un graphique entièrement connecté $ g (v, e) $ avec des poids de bord associés et un ensemble de contraintes spécifiant la distance $ d (v_i, v_j) <m_ {ij} $, où $ Left {v_ {i..j } droite } ⊂ v $, comment puis-je trouver le plus petit graphique de sous-ensemble $ g '(v', e ') $ tel qu'aucune des contraintes n'est violée?

En d'autres termes, trouvez le plus petit sous-ensemble du graphique de telle sorte que la distance entre un ensemble donné de sommets ne dépasse pas une constante.