Hallo Forum,

ich bin Nichtmathematiker und ein Anfänger auf dem Gebiet der Graphentheorie und suche eine konkrete Problembeschreibung/den Namen zu meinem Problem (wie z. B. eines von Karps 21 NP-schweren Problemen).
Z. B. aus diesen Kategorien: graph theory

a) geg.: ist eine Gesamtmenge an Knoten (N) sowie eine fix definierte Untermenge (U) an konkreten Knoten
Zwischen den Knoten bestehen untereinander ausnahmslos ungerichtete Kanten
b) ges.: Minimum der Knotenmenge (M) aus N, welche durch mindestens eine Kante alle U abdeckt
c) Hinweis: zur Menge der infrage kommenden Ergebnisknoten M können sowohl die Knoten aus N als auch U selbst gehören (da diese eine ungerichtete Kante zu sich selbst haben)


Als Skizze:


Gelb markiert ist die Untermenge an Knoten (U), welche per Kante (oder sich selbst) abgedeckt werden soll.

Als beste Lösungsmenge käme für das Beispiel nun Knoten 3 & 10 & 8 oder 3 & 10 & 13 in Betracht (wobei Knoten 8 aus Optimierungssicht bzw. Mehrwert dem Knoten 13 sicher vorzuziehen wäre, was in dem Problem allerdings vorerst keine Rolle spielt).

Ich denke nicht, dass es sich um ein reines Minimum Domination Set-Problem handelt (weil da alle Knoten eines Netzwerkes betrachtet werden und überdeckt werden müssen), sondern entweder eine "Unterart" des Set Covers oder eine Kombination mit einem anderen Graphenproblem oder ein ganz anderes Graphenthema.
Eventuell ein Minimum Hitting Set?

Über jeden Hinweis wäre ich dankbar, mit welchem grundsätzlichen Graphenlösungsansatz man da arbeiten muss.

Viele Grüße
Efrel