Die Knotenüberdeckung verständlich erklärt

Auf einer Feier streiten einige Paare von Gästen miteinander. Wie wenige Gäste muss man ausladen, damit kein Streitpaar mehr am Tisch sitzt? Diese Seite zeigt zuerst ohne Formeln, dann für Fachleute, welche Rechenwege das schnell oder genau lösen.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Wen lädt man aus?

Stellen Sie sich eine Feier mit acht Gästen vor. Einige Paare vertragen sich nicht: Sitzen beide am Tisch, gibt es Streit. Sie wollen so wenige Gäste wie möglich ausladen, damit kein Streitpaar übrig bleibt.

Unser Beispiel: Anna streitet mit Ben, Cem, Dora und Emil. Emil streitet außerdem mit Fritz, Gabi und Hanna. Das sind sieben Streitpaare.

Laden Sie Anna und Emil aus, ist jedes Streitpaar getrennt, denn jedes enthält einen von beiden. Mit einem Gast allein geht es nicht, weil keiner in allen sieben Paaren steckt. Die übrigen sechs feiern friedlich.

Fachleute zeichnen die Gäste als Punkte (Knoten) und jeden Streit als Linie dazwischen. Eine Auswahl von Knoten, die jede Linie berührt, heißt Knotenüberdeckung. Gesucht ist die kleinste. Ausgeladene und Bleibende ergeben zusammen alle acht Gäste. Wer wenige ausladen will, sucht also zugleich die größte Runde ohne Streit.

Schnell, aber nicht ganz genau

Bei vielen Gästen ist die kleinste Auswahl schwer zu finden: Schon bei vierzig Gästen gibt es mehr als eine Billion mögliche Auswahlen. Deshalb nutzt man Faustregeln. Sie liefern schnell eine brauchbare, aber nicht immer die kleinste Auswahl.

Erste Faustregel. Gehen Sie die Streitpaare der Reihe nach durch. Ist von einem Paar noch niemand ausgeladen, laden Sie beide aus. Beginnt die Liste mit Anna und Ben, danach Emil und Fritz, fliegen diese vier raus statt der nötigen zwei. Alle anderen Paare sind damit erledigt, denn jedes enthält Anna oder Emil.

Diese Regel hat eine Garantie: höchstens doppelt so viele Ausladungen wie nötig, bei jeder Anordnung der Streitpaare. Der Grund, am Beispiel: Anna und Ben sowie Emil und Fritz haben keinen Gast gemeinsam. Aus dem ersten Paar muss jede Lösung einen ausladen, aus dem zweiten ebenfalls einen. Jede Lösung braucht also mindestens zwei Ausladungen, die Regel nimmt je Paar zwei, also höchstens doppelt so viele. Das gilt für jede Liste, denn es kommt nur darauf an, dass die gewählten Paare keinen Gast teilen.

Zweite Faustregel. Laden Sie immer den Gast aus, der noch die meisten Streits hat. Im Beispiel sind das zuerst Anna, dann Emil: genau die kleinste Auswahl. In den Messungen, auf die diese Seite sich stützt, lag diese Regel in allen getesteten Anordnungen von Streitpaaren höchstens gut ein Zehntel über der kleinsten Auswahl.

Eine Garantie hat sie nicht. Sie schaut nur auf die Zahl der Streits und kann deshalb die falschen Gäste wählen: Wer am lautesten streitet, muss nicht der sein, den die kleinste Auswahl braucht. Es gibt Anordnungen, in denen sie mehr als das Doppelte der nötigen Zahl auslädt, mehr, als die Garantie der ersten Regel zulässt.

Vorab entscheiden

Manches lässt sich klären, bevor man sucht. Zwei Regeln dafür:

• Nur ein Streit. Streitet Ben nur mit Anna, ist es nie schlechter, Anna statt Ben auszuladen, denn Anna löst Bens Streit und vielleicht noch weitere.
• Mehr Streits als erlaubte Ausladungen. Angenommen, es dürfen nur zwei Gäste gehen. Anna hat vier Streits. Bliebe sie, müssten alle vier Streitpartner gehen, mehr als erlaubt. Also muss Anna gehen. Dann darf nur noch ein Gast gehen, und Emil hat noch drei Streits. Also muss auch er gehen.

Was nach solchen Regeln noch offen ist, nennen Fachleute den Kern. Am meisten klärt sich, wenn wenige Gäste in sehr vielen Streits stecken: Mit jedem, der gehen muss, sind alle seine Streitpaare erledigt.

Sicher zur kleinsten Auswahl: durchprobieren

Für die sicher kleinste Auswahl kennt man kein schnelles Verfahren für alle Fälle. Man muss geschickt durchprobieren. Die Frage ist eine Ja-Nein-Frage: Reichen zwei Ausladungen? Man nimmt ein Streitpaar, etwa Anna und Ben. Einer von beiden muss gehen. Also probiert man erst Anna, dann Ben.

Geht Anna, bleibt nur Emil mit seinen drei Streits, und eine weitere Ausladung genügt: Ja. Geht Ben, bleiben Streits um Anna und um Emil, und eine weitere Ausladung reicht nicht: Dieser Weg scheitert. Jede Probe teilt sich so in zwei Wege, eine Gabelung. Mit jeder erlaubten Ausladung kommt eine Gabelung dazu, und bei vielen Ausladungen wächst die Zahl der Wege rasch über das Machbare.

Geschickter ist es, den Gast mit den meisten Streits zu nehmen. Entweder er geht, oder alle seine Streitpartner gehen. Hat er mindestens drei Streitpartner, verbraucht der zweite Weg mindestens drei Ausladungen auf einmal und endet schnell. So fallen viele Wege weg.

Häufige Missverständnisse

• „Die Regel mit Garantie ist die bessere.“ Nicht unbedingt. Die Garantie begrenzt nur den schlimmsten Fall. In den Messungen lag die erste Faustregel im typischen Fall weiter vom Besten entfernt als die zweite.
• „Je mehr Streitpaare, desto schwerer.“ Nicht allein. Stecken fast alle Streits in wenigen Gästen und dürfen nur wenige gehen, ist das Meiste schnell erledigt, weil diese Gäste mehr Streits haben als erlaubte Ausladungen. Ist der Streit gleichmäßig verteilt, hat niemand mehr Streits als erlaubte Ausladungen, und die Regel streicht nichts. So zeigen es die Messungen bei gleich vielen Streitpaaren.

Woran Sie das im Alltag erkennen

• Sie müssen etwas streichen, damit sich keine zwei Dinge in die Quere kommen, etwa so wenige Termine wie möglich, bis sich keine zwei überschneiden.
• Sie stellen Kameras an Kreuzungen auf; jeder Gang soll von mindestens einem Ende überwacht sein, mit möglichst wenigen Kameras.
• Sie suchen die größte Gruppe, in der niemand mit jemandem Probleme hat, etwa ein Team aus Leuten, die alle miteinander auskommen.

Wie ernst ist das Rechenbild zu nehmen?

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Es spielt die Aufgabe mit erfundenen Paketen für einen Lastwagen durch, in kleinen Fällen; alle Messungen dieser Seite stammen von dort. Ein vereinfachtes Rechenbild ersetzt keine echte Ladung. Zum Verstehen brauchen Sie die Demo nicht. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil für Fachleute.

Was Sie mitnehmen:

• Fragen Sie zuerst, wie viele Ausladungen Sie sich leisten wollen, und wer mehr Streits hat, als Sie Ausladungen erlauben.
• Sichern Sie sich mit einer Faustregel mit Garantie ab und prüfen Sie, ob eine zweite Regel Besseres findet.
• Suchen Sie zuerst die wenigen, die in fast allen Streits stecken.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Methodik der Demo zusammen.

• Problem: Gegeben ist ein ungerichteter Konfliktgraph \(G = (V, E)\) mit \(n = |V|\) Knoten (den Sendungen einer Sammelladung); eine Kante bedeutet „dürfen nicht zusammen verladen werden“. Eine Überdeckung ist eine Menge \(C \subseteq V\), die jede Kante berührt; \(\tau(G)\) ist ihre kleinste Größe. Eine unabhängige Menge enthält keine Kante; \(\alpha(G)\) ist ihre größte Größe. Die Entscheidungsfrage lautet: Gibt es eine Überdeckung der Größe höchstens \(k\)? Die Demo wählt \(k = \tau + \Delta\) mit \(\Delta\) von \(-3\) bis \(3\); \(\Delta = 0\) ist eine Ja-Instanz, \(\Delta < 0\) eine Nein-Instanz. Die Entscheidungsfrage ist NP-vollständig (Karp, siehe Quellen).
• Graphen: Zufallsregeln (jedes Paar unabhängig im Konflikt, mit dem eingestellten Anteil), Zeitfenster (Konflikt, wenn zwei Fenster überlappen: ein Intervallgraph), Klassenregeln (jede Sendung gehört zufällig zu einer von sechs Klassen; für jedes Klassenpaar, auch eine Klasse mit sich selbst, wird einmal mit dem eingestellten Anteil als Wahrscheinlichkeit entschieden, ob ihre Sendungen im Konflikt stehen) und wenige Verursacher (\(\lceil n/20 \rceil\) Knoten stehen mit dem eingestellten Anteil der übrigen im Konflikt, dazu ebenso viele Zufallskonflikte zwischen den übrigen). Feste Vergleichsgraphen sind Baum, Gitter, skalenfrei (jeder neue Knoten hängt sich an \(m\) frühere, mit Wahrscheinlichkeit proportional zum Grad), vollständig bipartit und eine Greedy-Falle. Alle Graphen sind erzeugt, keine echten Sendungsdaten.
• Voreinstellung und Bereiche: Voreingestellt sind 10 Sendungen mit einem Konfliktanteil von 30 % (Zufallsregeln). Die Hauptansicht geht bis \(n = 60\), die Messreihen bis \(n = 200\).
• Determinismus: Die Verfahren sind vollständig deterministisch (Gleichstand: kleinster Index); der Zufall steckt allein in der Erzeugung der Graphen aus festen Startwerten.
• Aufwandsmaß: Ein Knoten des Suchbaums ist ein Aufruf der Verzweigung; die Demo zählt diese Knoten, keine Laufzeit. Überschreitet ein Lauf das Budget, bricht er ab und wird als Abbruch gemeldet. Das Budget beträgt 200 000 Knoten je Regel in der Hauptansicht und im Vergleich der Verursacher 5 000 (Kantenregel 2 000, exakte Lösung 20 000).

Die Demo vergleicht acht Verfahren:

Verfahren	Idee
Matching-Verfahren	Die Kanten werden in fester Reihenfolge durchgegangen; eine Kante wird genommen, wenn beide Enden frei sind. Die Überdeckung besteht aus allen Endpunkten der genommenen Kanten.
Greedy nach Höchstgrad	Immer den Knoten mit den meisten offenen Konflikten aufnehmen (Gleichstand: kleinster Index).
LP-Rundung	Die LP-Relaxation (siehe unten) wird im bipartiten Doppelgraphen gelöst: Jeder Knoten \(v\) wird zu \(v_L\) und \(v_R\), jede Kante \(\{u, v\}\) zu \(\{u_L, v_R\}\) und \(\{v_L, u_R\}\). Ein größtes Matching und die Überdeckung nach König liefern eine optimale halbganzzahlige Lösung. Eine Sondierung zerlegt den Kern weiter: Bleibt der LP-Wert gleich, wenn ein Knoten auf 1 (oder auf 0 mit allen Nachbarn auf 1) gesetzt wird, ist das wieder eine optimale Lösung, und halbganzzahlig, weil nur 0, ½ und 1 vorkommen. Danach wird der Rest neu gelöst, bis kein Knoten mehr festgelegt werden kann. Gerundet wird die Menge „\(x = 1\)“ plus der verbleibende Kern.
Buss	Erzwingt Knoten mit mehr als \(k\) offenen Konflikten (\(k'\): der um die erzwungenen Knoten verminderte Parameter); siehe Formeln.
Grad-1-Regel	Hat ein Knoten nur einen Konflikt, gibt es eine kleinste Überdeckung mit dessen Partner.
Verzweigen auf einer Kante	\(u\) oder \(v\) hinein; gewählt wird die offene Kante mit kleinstem \(u\), dazu kleinstem \(v\); Suchbaum mit höchstens \(2^k\) Blättern.
Verzweigen auf dem Grad	Der Knoten höchsten Grades \(d \ge 3\): er hinein oder alle seine Partner hinein; bei Maximalgrad höchstens 2 (Pfade und Kreise) exakt in Polynomialzeit.
Exakt	LP-Kern, dann iterative Vertiefung über \(k\) ab der LP-Untergrenze, mit Gradregel und Grad-1-Regel. Der Buss-Kern wird einmal vorab angewendet, die Grad-1-Regel in jedem Suchknoten.

Die Formeln

Das Komplement einer Überdeckung ist eine unabhängige Menge und umgekehrt. Mit \(n = |V|\) gilt deshalb:

\[\tau(G) + \alpha(G) = n\]

Ein Matching \(M\) ist eine Kantenmenge ohne gemeinsame Endpunkte, maximal, wenn sich keine Kante hinzufügen lässt. Das Matching-Verfahren nimmt alle Endpunkte eines maximalen Matchings; für dessen Größe \(|M|\) gilt (Herleitung unten):

\[|M| \le \tau(G) \le 2|M|\]

Die LP-Relaxation gibt jedem Knoten \(v\) einen Wert \(x_v\) und minimiert \(\sum_v x_v\) unter

\[x_u + x_v \ge 1 \ \text{ für jede Kante } \{u, v\}, \qquad 0 \le x_v \le 1.\]

Jede Ecke des zulässigen Bereichs ist halbganzzahlig, \(x_v \in \{0, \tfrac12, 1\}\), und der LP-Wert ist eine Untergrenze für \(\tau\). Für eine optimale halbganzzahlige Lösung seien \(V_1 = \{v : x_v = 1\}\), \(V_0 = \{v : x_v = 0\}\) und \(K = \{v : x_v = \tfrac12\}\) der Kern. Nach Nemhauser und Trotter gibt es eine kleinste Überdeckung, die \(V_1\) enthält und \(V_0\) meidet, also mit dem von \(K\) induzierten Teilgraphen \(G[K]\):

\[\tau(G) = |V_1| + \tau(G[K])\]

Buss (Herleitung unten). Hat ein Knoten mehr als \(k\) Nachbarn, gehört er in jede Überdeckung der Größe höchstens \(k\). Nach dem Entfernen aller erzwungenen Knoten bleibt der Restparameter \(k'\); ein Ja-Kern hat höchstens

\[|E'| \le k'^2\]

Kanten; sonst ist die Antwort Nein. Verzweigen. Auf einer Kante \(\{u, v\}\) (\(u\) oder \(v\) hinein) entsteht ein Suchbaum mit höchstens \(2^k\) Blättern. Auf einem Knoten \(v\) mit Grad \(d \ge 3\) (\(v\) hinein oder alle \(d\) Nachbarn hinein) gilt für die Zahl \(T(k)\) der Blätter des Suchbaums bei Parameter \(k\):

\[T(k) \le T(k-1) + T(k-d), \qquad d \ge 3\]

Bei Maximalgrad höchstens 2 besteht der Rest aus Pfaden und Kreisen: Ein Pfad mit \(\ell\) Knoten braucht \(\lfloor \ell/2 \rfloor\), ein Kreis \(\lceil \ell/2 \rceil\) Knoten. Der schnellste bekannte Algorithmus in \(k\) (Harris und Narayanaswamy 2024) hat eine kleinere Wachstumsbasis als die Schranke, die aus der Rekursion oben folgt. Unter der Exponentialzeit-Hypothese gibt es keinen Algorithmus mit Laufzeit \(O^*(2^{o(k)})\) (\(O^*\) lässt polynomielle Faktoren weg).

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo. Wo die Demo dieselbe Aussage an Instanzen prüft, steht es dabei.

Komplement: \(\tau + \alpha = n\).

• Schritt 1: \(C\) ist eine Überdeckung genau dann, wenn jede Kante einen Endpunkt in \(C\) hat, also keine Kante ganz in \(V \setminus C\) liegt, also \(V \setminus C\) unabhängig ist.
• Schritt 2: Die Zuordnung \(C \mapsto V \setminus C\) ist eine Bijektion zwischen Überdeckungen und unabhängigen Mengen und macht aus der Größe \(|C|\) die Größe \(n - |C|\).
• Schritt 3: Die kleinste Überdeckung gehört damit zur größten unabhängigen Menge. Die Demo prüft das an einem kleinen Graphen gegen das Aufzählen aller Teilmengen.

Das Matching-Verfahren liefert höchstens das Doppelte des Optimums.

• Schritt 1: Die Kanten eines Matchings \(M\) haben keinen gemeinsamen Endpunkt. Eine Überdeckung braucht für jede Matchingkante einen eigenen Endpunkt. Also gilt \(|M| \le \tau\).
• Schritt 2: Sei \(M\) maximal. Eine Kante ohne Endpunkt unter den Endpunkten von \(M\) ließe sich zu \(M\) hinzufügen, im Widerspruch zur Maximalität. Die \(2|M|\) Endpunkte bilden also eine Überdeckung.
• Schritt 3: Mit Schritt 1 folgt \(2|M| \le 2\tau\). Die Schranke ist scharf: Auf dem vollständig bipartiten Graphen \(K_{r,r}\) mit je \(r\) Knoten pro Seite ist jedes maximale Matching perfekt, das Verfahren nimmt \(2r\) Knoten, und \(\tau = r\) (eine Seite genügt, und \(r\) disjunkte Kanten erzwingen \(r\) Knoten). Die Demo prüft \(2r\) auf \(K_{r,r}\).

Greedy hat keine konstante Garantie: die Falle. Die Falle hat \(a\) linke Knoten; für jedes \(j = 2, \dots, a\) gibt es \(\lfloor a/j \rfloor\) rechte Knoten, jeder mit \(j\) eigenen linken Nachbarn verbunden. Die linken Knoten bilden eine Überdeckung der Größe \(a\), die Demo bestätigt \(\tau = a\). Greedy nimmt in allen sechs gemessenen Größen alle rechten Knoten, das sind \(\sum_{j=2}^{a} \lfloor a/j \rfloor\). Das ergibt für \(a = 6, 12, 24\) die Größen 8, 23 und 60 und stimmt mit der Messung überein. Die Summe wächst wie \(a \ln a\), der Faktor also wie \(\ln a\), falls Greedy auch bei größerem \(a\) alle rechten Knoten nimmt; bestätigt ist das nur für die sechs gemessenen Größen.

Die LP-Rundung liefert höchstens das Doppelte des Optimums.

• Schritt 1: Ist \((p, q)\) eine Überdeckung des Doppelgraphen (mit \(p_v, q_v \in \{0, 1\}\) für \(v_L\) und \(v_R\)), dann gilt für jede Kante \(\{u, v\}\): \(p_u + q_v \ge 1\) und \(p_v + q_u \ge 1\). Mit \(x_v = (p_v + q_v)/2\) folgt \(x_u + x_v \ge 1\); die Lösung ist zulässig.
• Schritt 2: Ihr Wert ist die Hälfte der Größe der Überdeckung. Im bipartiten Doppelgraphen ist die kleinste Überdeckung so groß wie das größte Matching (Satz von König). Dass diese Lösung auch für den LP optimal ist, übernimmt diese Seite von Nemhauser und Trotter; der LP-Wert ist dann die Hälfte der Größe eines größten Matchings im Doppelgraphen.
• Schritt 3: Jede Überdeckung ist mit \(x_v \in \{0, 1\}\) zulässig, also ist der LP-Wert höchstens \(\tau\).
• Schritt 4: Die Rundung nimmt alle Knoten mit \(x_v \ge \tfrac12\). Jeder von ihnen trägt mindestens \(\tfrac12\) zur Summe bei, also nimmt die Rundung höchstens \(2\sum_v x_v \le 2\tau\) Knoten. Ist \(x\) überall \(\tfrac12\), nimmt sie alle \(n\) Knoten, genau das Doppelte des LP-Werts.

Die Grad-1-Regel ist sicher. Hat \(v\) genau einen Nachbarn \(u\), muss jede Überdeckung \(u\) oder \(v\) enthalten. Enthält sie \(v\) und nicht \(u\), ist der Tausch von \(v\) gegen \(u\) wieder eine Überdeckung derselben Größe, denn \(v\) deckt nur die Kante \(\{u, v\}\), \(u\) deckt sie auch. Es gibt also eine kleinste Überdeckung mit \(u\).

Buss: Kernbildung bei kleinem \(k\).

• Schritt 1: Hat \(v\) mehr als \(k\) Nachbarn und liegt nicht in der Überdeckung, müssten alle Nachbarn hinein, mehr als erlaubt. Also liegt \(v\) in jeder Überdeckung der Größe höchstens \(k\).
• Schritt 2: Das wiederholt man mit dem sinkenden Restparameter \(k'\), bis jeder Knoten höchstens \(k'\) Nachbarn hat.
• Schritt 3: Eine Überdeckung der Größe \(k'\) deckt dann höchstens \(k'^2\) Kanten. Bleiben mehr, ist die Antwort Nein.
• Folgerung (Rechnung dieser Seite): Hat kein Knoten mehr als \(k\) Nachbarn, erzwingt die Regel nichts. Die Kernbildung streicht also nur etwas, wo der Maximalgrad über \(k\) liegt; ist ein Knoten erzwungen, sinkt die Schwelle \(k'\) schon im selben Durchgang, und weitere Knoten können folgen. Danach löst die Kantenverzweigung den Rest in Zeit \(2^{k'}\) mal einem Polynom in der Größe des Kerns; insgesamt ist die Zeit polynomiell in \(n\) mal einer Funktion von \(k\).

Verzweigen. Auf einer Kante ist die Tiefe des Suchbaums höchstens \(k\), jeder Knoten hat zwei Kinder: höchstens \(2^k\) Blätter. Auf einem Knoten mit Grad \(d\) führt der Zweig „\(v\) hinein“ zu Parameter \(k-1\), der Zweig „alle Nachbarn hinein“ zu \(k-d\) (nur möglich, wenn \(k \ge d\)). Ist \(T(k)\) das Maximum der Blattzahl über alle Instanzen mit Parameter \(k\), nimmt \(T\) mit \(k\) nicht ab, und es folgt \(T(k) \le T(k-1) + T(k-3)\). Die Wachstumsbasis ist die positive Lösung von \(x^3 = x^2 + 1\). Sobald der Maximalgrad höchstens 2 beträgt, endet die Verzweigung: Jeder zweite Knoten eines Pfades oder Kreises genügt.

Durchgerechnet: acht Gäste, sieben Streitpaare

Rechnung dieser Seite, keine Messung der Demo: Die Werte stammen aus dem Rechenteil der Demo, aufgerufen auf diesem Graphen. Er hat acht Knoten (Anna, Ben, Cem, Dora, Emil, Fritz, Gabi, Hanna) und die sieben Kanten Anna–Ben, Anna–Cem, Anna–Dora, Anna–Emil, Emil–Fritz, Emil–Gabi und Emil–Hanna in dieser Reihenfolge.

Verfahren	Ergebnis	Größe
Kleinste Überdeckung	Anna und Emil; \(\alpha = 6\) (alle übrigen)	2
Matching-Verfahren	nimmt Anna–Ben, dann Emil–Fritz (alle anderen Kanten sind dann berührt): Anna, Ben, Emil, Fritz; Faktor 2	4
Greedy	Anna (Grad 4, Gleichstand mit Emil, kleinster Index), dann Emil	2
LP	\(x = 1\) für Anna und Emil, sonst \(x = 0\); LP-Wert 2, Kern leer	2

Entscheidungsfrage für \(k = 2\): Buss nimmt Anna (Grad 4 > 2) und danach Emil (Grad 3 > 1), der Restparameter ist 0 und es bleibt keine Kante: Ja, ohne Verzweigen. Für \(k = 1\) wird Anna erzwungen (4 > 1), der Restparameter fällt auf 0, Emil hat noch 3 Nachbarn und wird ebenfalls erzwungen: Der Restparameter wird negativ, die Antwort ist Nein. Die Zahl der Suchknoten, vom Rechenteil der Demo ausgezählt:

Frage	Kantenregel	Gradregel	Grad + Grad-1-Regel	Buss-Kern, dann Grad + Grad-1-Regel
\(k = 2\) (Ja)	3	3	1	1
\(k = 1\) (Nein)	3	2	1	0

Befunde

Alle Zahlen stammen aus der Auswertung der Demo. Zählwerte (Knoten, Kanten, Sendungen) sind ganzzahlig; Faktoren sind die Größe der Überdeckung geteilt durch \(\tau\). Die Strukturzeilen sind Mediane über drei feste Graphen je Struktur; die elf Strukturen sind Zufall (40 Sendungen mit 20 % und 50 %, 60 mit 5 %, 100 mit 3 %), Zeitfenster (60), Klassenregeln (60), Baum (100), Gitter 10 × 10, skalenfrei (200 mit \(m = 2\) und \(m = 4\)) und wenige Verursacher (200). Der Standardfall und die benannten Verzweigungsfälle sind je ein einzelner Graph, kein Median.

Frage	Befund
Standardfall: 10 Sendungen, Konfliktanteil 30 %, Zufallsregeln	\(\tau = 4\). Matching-Verfahren 6 (Faktor 1,50), Greedy 4, LP-Rundung 4. LP-Kern: 4 hinein, 6 heraus, kein Kern. Für \(k = 4\): Kantenregel 9 Suchknoten, Grad 3, Grad + Grad-1-Regel 1, Buss 1.
Wie nah kommt das Matching-Verfahren dem Optimum? (elf Strukturen)	Median-Faktor 1,15 bis 2,00. Genau 2,00 auf dem Gitter 10 × 10, im ungünstigsten der drei Graphen auch bei Klassenregeln (60 Sendungen) und wenigen Verursachern (200 Sendungen); darüber liegt es nie, wie die Herleitung verlangt. Zufall, 60 Sendungen, 5 %: 1,67; Baum: 1,64.
Und Greedy nach Höchstgrad? (elf Strukturen)	Faktor höchstens 1,11 in allen elf Strukturen, Median 1,00 bis 1,04.
Greedy-Falle mit \(\tau = a\)	Faktor 1,00 (\(a = 4\)), 1,33 (6), 1,50 (8), 1,92 (12), 2,13 (16), 2,50 (24). Das Matching-Verfahren bleibt dort bei genau 2,00; ab \(a = 16\) liegt Greedy über dessen Garantie.
Und die LP-Rundung? (elf Strukturen)	Faktor 1,00 dort, wo der LP ganzzahlig ist: Baum, Gitter, skalenfrei mit \(m = 2\), wenige Verursacher. Bis 1,89 im ungünstigsten der drei Graphen bei skalenfrei, 200 Sendungen, \(m = 4\): Dort ist überall \(x = \tfrac12\); im Graphen mit dem mittleren Faktor nimmt die Rundung alle 200 Sendungen gegen \(\tau = 108\) (200 durch 108, Rechnung dieser Seite). Das ist schlechter als das Matching-Verfahren (1,46). LP-Wert / \(\tau\): 0,58 (Zeitfenster) bis 1,00.
Wie viel entscheidet der LP-Kern?	Bipartit (Baum, Gitter): kein Kern, und \(\tau\) ist gleich der Größe eines größten Matchings (Satz von König, an den Messgraphen bestätigt). Teilkern: Zufall, 60 Sendungen, 5 %: 19 von 60; Klassenregeln: 6 von 60; Zufall, 100 Sendungen, 3 %: 48 von 100. Der ganze Graph bleibt Kern bei Zufall mit 40 Sendungen (20 % und 50 %), Zeitfenster mit 60 Sendungen und skalenfrei mit \(m = 4\). Wenige Verursacher: 20 hinein, 180 heraus, kein Kern.
Verzweigen, dichter Fall: 40 Sendungen, 50 %, \(k = \tau = 33\)	Kantenregel über 200 000 Knoten (abgebrochen), Grad 47, Grad + Grad-1-Regel 33, Buss 33.
Verzweigen, dünner Fall: 60 Sendungen, 5 %, \(k = \tau = 27\)	Kantenregel über 200 000, Grad 17, Grad + Grad-1-Regel und Buss je 1 Knoten.
Verzweigen, Zeitfenster: \(k = \tau - 1 = 31\) (Nein-Instanz)	Kantenregel über 200 000, Grad 3 929, Grad + Grad-1-Regel und Buss 2 887: Hier muss die Verzweigung die Nichtexistenz beweisen. Zeitfenster-Graphen sind Intervallgraphen und damit perfekt; dort ist die kleinste Überdeckung auch in Polynomialzeit berechenbar, die Zahl misst also die Verzweigungsregeln und keine Härte der Instanz.
Wann hilft die Kernbildung nach Buss?	Nur bei kleinem \(k\). Dicht (oben): \(k' = 33\), alle 412 Kanten und alle 40 Sendungen bleiben. Wenige Verursacher (60 Sendungen, \(k = 5\), Nein-Instanz): \(k' = 2\), 3 Kanten, 6 Sendungen; die Antwort fällt mit 1 Suchknoten.
Wenige Verursacher gegen Zufall mit gleicher Kantenzahl (100 Sendungen, Zahl der Verursacher auf 2 bis 16 gesetzt, \(k = \tau - 1\))	Bei 16 Verursachern bleiben von 541 Kanten 16 im Buss-Kern, im Zufallsgraphen alle 541. Suchknoten je Regel: zweite Tabelle. Der Zufallsgraph wird mit der Grad-1-Regel ebenfalls schnell; der Gewinn von Buss liegt im Kern, nicht allein in der Knotenzahl.
Gilt \(\tau = n - \alpha\)?	Ja, mit den Standardeinstellungen, aber 14 Sendungen: \(\tau = 7 = 14 - 7\), geprüft gegen das Aufzählen aller Knotenteilmengen, die im Komplementgraphen eine Clique bilden (ohne Verzweigen).
Stimmen die Verfahren?	\(\tau\) aus dem exakten Verfahren ist gleich dem Ergebnis des gemischt-ganzzahligen Lösers HiGHS und gleich \(n - \alpha\) mit \(\alpha\) aus der Cliquensuche im Komplement (networkx), auf über 300 festen Instanzen; gleich Brute Force bei \(n \le 14\). Auf bipartiten Graphen ist \(\tau\) gleich der Größe des größten Matchings, und der LP-Kern ist leer. Alle vier Verzweigungsregeln antworten für \(k = \tau - 1\) und \(k = \tau\) wie HiGHS.

Suchknoten im Vergleich der Verursacher (100 Sendungen, \(k = \tau - 1\), Median über drei Graphen; „über“: mindestens ein Lauf hat das Budget erreicht). Beim Zufallsgraphen mit 8, 12 und 16 Verursachern steht \(k\) für Greedy minus 1 (siehe nächster Abschnitt).

Verursacher	Grad + Grad-1-Regel (Verursacher / Zufall)	Grad ohne Grad-1-Regel (Verursacher / Zufall)	Kantenregel (Verursacher)
2	1 / 1	3 / 2 067	15
4	1 / 8	5 / über 5 000	255
8	1 / 24	9 / über 5 000	über 2 000
12	1 / 37	13 / 54	über 2 000
16	4 / 50	19 / 85	über 2 000

Was die Messung zeigt und wo sie endet

Was sie belegt:

• Die hergeleiteten Zusammenhänge (Komplement, Faktor 2 des Matching-Verfahrens und der LP-Rundung, Grad-1-Regel, Buss, Rekursion) gelten für jeden Graphen. Die Messung bestätigt sie nur an den erzeugten Graphen.
• Zählwerte sind für eine gegebene Instanz deterministisch, und das exakte Verfahren stimmt auf über 300 Instanzen mit unabhängigen Lösern überein. Die Instanzen stammen aus dem Zufallsgenerator der Python-Standardbibliothek; ob dieselben Graphen über Python-Versionen entstehen, ist nicht geprüft.
• Die Vergleiche der Verfahren auf demselben Graphen: Alle Verfahren sehen dieselbe Instanz.

Was sie nicht belegt:

• Kleine Stichproben: Die Strukturzeilen sind Mediane über drei Graphen. Der Greedy-Faktor von höchstens 1,11 gilt für diese elf Strukturen, nicht allgemein; die Falle zeigt, dass es keine konstante Garantie gibt. In der Falle sind nur sechs Größen gemessen; ob der Faktor dort ohne Schranke wächst, zeigt die Messung nicht (aus der Literatur bekannt: logarithmisch, siehe Quellen).
• Einzelfälle: Die Verzweigungsfälle (dicht, dünn, Zeitfenster) sind je ein Graph. Mehr als eine Instanz je Zahl der Verursacher steht nur in der Reihe zu wenigen Verursachern (drei Graphen).
• Knoten statt Laufzeit: Jeder Suchknoten kostet je nach Regel verschieden viel; die Knotenzahlen sagen nicht, welche Regel schneller läuft.
• Der Kern ist nicht eindeutig: Die Sondierung findet eine von meist vielen optimalen Lösungen, nicht die mit dem kleinsten Kern. Eine Vormessung mit der Ecke von HiGHS ergab andere Kerne: Zufall, 100 Sendungen, 3 %: 38 von 100 in der Vormessung gegen 48 mit Sondierung; Zufall, 60 Sendungen, 5 %: 36 von 60 gegen 19.
• Bezugsgröße im Verursacher-Vergleich: Die exakte Lösung war dort auf 20 000 Knoten begrenzt. Beim Zufallsgraphen mit 8, 12 und 16 Verursachern (in 2, 3 und 3 von 3 Graphen) steht für \(\tau\) die Greedy-Größe und \(k\) ist Greedy minus 1. Ist Greedy dort nicht optimal, ist es keine Nein-Instanz mehr (Folgerung dieser Seite). Außerdem unterscheiden sich beide Graphen bei gleicher Kantenzahl in \(\tau\) und in der Gradverteilung; der Vergleich trennt „kleines \(k\)“ nicht von „ungleiche Grade“.
• Modellgrenzen: Die Demo ist ungewichtet (mit Kosten je Sendung ändern sich Matching-Verfahren und Greedy). Konflikte sind Paare; Regeln für Dreiergruppen sind eine Mengenüberdeckung im Hypergraphen; dort gelten die Argumente für Faktor 2 und Halbganzzahligkeit nicht (für Dreiermengen gibt es eigene Näherungen und Kerne). Die Graphen sind klein und erzeugt. Reale Löser nutzen Branch-and-Reduce mit vielen weiteren Regeln und Lokalsuche und lösen Graphen mit Millionen Kanten.

Erweiterungen und Verweise

Zwei verwandte Demos dieser Website:

• Dieselbe Aufgabe im Komplement: Die Demo „Größte Clique: Färbungsschranke und Kernzahl“ sucht die größte verträgliche Fuhre. Eine unabhängige Menge des Konfliktgraphen ist eine Clique in seinem Komplement, dem Verträglichkeitsgraphen; wegen \(\tau + \alpha = n\) gehören beide Aufgaben zusammen.
• Große Graphen: Die Demo „Unabhängige Menge im großen Maßstab: Reduktionen und Lokalsuche“ verkleinert große Konfliktgraphen mit Reduktionsregeln und sucht danach lokal weiter. Sie setzt dort an, wo die hier beschriebene Demo wegen der kleinen Graphen endet.

Quellen

• Nemhauser, G. L., & Trotter, L. E. (1975). Vertex packings: structural properties and algorithms. Mathematical Programming 8, 232–248.
• Buss, J. F., & Goldsmith, J. (1993). Nondeterminism within P. SIAM Journal on Computing 22(3), 560–572.
• Harris, D. G., & Narayanaswamy, N. S. (2024). A faster algorithm for vertex cover parameterized by solution size. STACS 2024, arXiv:2205.08022.
• Karp, R. M. (1972). Reducibility among combinatorial problems. In: Miller, Thatcher (Hrsg.), Complexity of Computer Computations, Plenum Press (NP-Vollständigkeit der Knotenüberdeckung).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/vertex-cover-demo.

Die drei erstgenannten Arbeiten stammen aus der README und dem Expander der Demo und wurden für diese Seite nicht nachgeschlagen. Karp (1972) und die Angabe zum logarithmischen Wachstum des Greedy-Faktors stehen nicht in der README und sind aus dem Gedächtnis, nicht geprüft. Das Gästebeispiel ist erdacht und stammt nicht aus der Demo; die Herleitungen und das durchgerechnete Beispiel sind Rechnungen dieser Seite und keine Messungen.