Straßen/Städte/Knotenüberdeckung/Beispiel

In einem Landkreis sind Städte durch Straßen verbunden. Da es im Winter häufig schneit, sollen in gewissen Städten Räumdienste eingerichtet werden. Da man die Straßen schnell räumen möchte, sollen die Räumdienste nur für direkt an die Stadt anliegende Straßen zuständig sein. Man möchte dabei sicherstellen, dass jede Straße durch mindestens einen Räumdienst abgedeckt wird. Gleichzeitig möchte man möglichst wenige Räumdienste aufbauen. In welchen Städten sollen Räumdienste eingerichtet werden?