Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Kernel für k-Vertex Cover + Verständnisfrage
Druckversion
Druckversion
Autor
Universität/Hochschule J Kernel für k-Vertex Cover + Verständnisfrage
yggdrasill
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-05-05


Hallo, ich versuche gerade die Kernbildung für parametrisierte Probleme am Beispiel  \(k\)-Vᴇʀᴛᴇx Cᴏᴠᴇʀ zu verstehen.

Für \(k\)-Vᴇʀᴛᴇx Cᴏᴠᴇʀ gibt es ja die klassische Kernbildung nach Buss, die für eine Ja-Instanz immer zu einem Graphen mit maximaler Knotenanzahl \(k\cdot (k+1)\) führt, in dem die folgenden beiden Reduktionsregeln so oft wie möglich angewandt werden:

1. Wenn es einen Knoten \(v\) mit Grad 0 gibt, lösche ihn \((G,k) \rightarrow (G \setminus \{ v \},k)\).
2. Wenn es einen Knoten \(v\) mit Grad > \(k\) gibt, lösche ihn und verringere k um 1 \((G,k) \rightarrow (G \setminus \{ v \},k-1)\).

Soweit, so einleuchtend - wobei ich noch eine Verständnisfrage hätte: In der Literatur steht immer, man solle die Regeln so lange anwenden, bis kein entsprechender Knoten mehr existiert. Was mache ich wenn $k=0$ und ich einen Knoten mit Grad $1$ habe? Breche ich dann ab?

Jetzt mein eigentliches Problem: Man hat mir folgende weitere Regel vorgestellt, die angeblich richtig (in dem Sinne, dass sie zu einer äquivalenten Instanz führt) sein soll:


3. Wenn es zwei Knoten \(u\) und \(v\) gibt, für die gilt \(N[v]\subseteq N[u]\), dann lösche \(v\) \((G,k) \rightarrow (G\setminus\{v\},k)\).

Intuitiv scheint das sinnvoll zu sein, denn wenn die Geschlossene Nachbarschaft von \(v\) vollständig Teil der geschlossenen Nachbarschaft von \(u\) ist, muss ich ja nur \(u\) in meinen Vertex Cover reinnehmen und könnte \(v\) dementsprechend entfernen, da ich diesen Knoten eh nie in mein Cover nehmen würde.

Wenn ich die Regel dann aber tatsächlich anwende, "frisst" sie meinen Graphen aber immer auf, d.h. am Ende bleibt ein leerer Graph übrig (was dazu führt, dass aus Nein-Instanzen plötzlich Ja-Instanzen werden).

Beispiel für $k = 1$:

<math>
\begin{tikzpicture}
\node[draw,circle] (A) {a};
\node[draw, circle, right=of A] (B) {b};
\node [draw, circle, below=of A] (C) {c}
\draw (A) -- (B);
\draw (A) -- (C);
\draw (B) -- (C);
\end{tikzpicture}
</math>

Dies ist klar eine Nein-Instanz. Wenn ich jetzt allerdigns Regel 3 anwende, kann ich einen der Knoten löschen (z.B. $c$), lasse $k$ unverändert und erhalte dann:

<math>
\begin{tikzpicture}
\node[draw,circle] (A) {a};
\node[draw, circle, right=of A] (B) {b};
\draw (A) -- (B);
\end{tikzpicture}
</math>

Was plötzlich eine Ja-Instanz ist?  Ist die Regel falsch oder stehe ich auf dem Schlauch?

Beste Grüße und vielen Dank im Vorraus!





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2009
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-05-05


Hallo yggdrasill, und herzlich willkommen auf dem Matheplaneten! 🙂

yggdrasill schreibt:
In der Literatur steht immer, man solle die Regeln so lange anwenden, bis kein entsprechender Knoten mehr existiert. Was mache ich wenn k=0 und ich einen Knoten mit Grad 1 habe? Breche ich dann ab?

Ja, das solltest Du, da es ja dann keinen Sinn mehr ergibt, weiterzumachen.

yggdrasill schreibt:
Intuitiv scheint das sinnvoll zu sein, denn wenn die Geschlossene Nachbarschaft von v vollständig Teil der geschlossenen Nachbarschaft von u ist, muss ich ja nur u in meinen Vertex Cover reinnehmen und könnte v dementsprechend entfernen, da ich diesen Knoten eh nie in mein Cover nehmen würde.

Mir erscheint diese Begründung nicht richtig. Die Nachbarschafts-Beziehung erstreckt sich ja nur auf die Knoten; aber innerhalb der Nachbarschaft kann es natürlich Kanten geben, die mit v, aber nicht mit u inzident sind. Für diese Kanten nützt es also gar nichts, u in dein Vertex Cover aufzunehmen.
Genau das zeigt ja auch Dein Beispiel.

Woher kommt diese angebliche Regel denn?

Viele Grüße
Thorsten


-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
yggdrasill
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-05


Hi Torsten, danke für deine Antwort!

Ich folge Übungsmaterialien zu denen es leider keine Lösungen gibt. Die Aufgabe lautet sinngemäß "zeigen Sie, dass diese Regel (ebenso wie die beiden vorgenannten) korrekt ist". Für mich impliziert das, dass diese Regel in der Tat korrekt ist.
 
Die Regel lautet ganz genau:

Wenn $G$ zwei Knoten $u$ und $v$ besitzt, so dass $N[v]\subseteq N[u]$, ersetze $(G,k)$ mit $(G\setminus\{v\},k)$.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
yggdrasill
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2021-05-06


Das Problem mit der Regel hat sich geklärt - war tatsächlich ein Fehler! Danke für die Hilfe!

(2021-05-05 14:41 - Bilbo in <a href=viewtopic.php?
yggdrasill schreibt:
In der Literatur steht immer, man solle die Regeln so lange anwenden, bis kein entsprechender Knoten mehr existiert. Was mache ich wenn k=0 und ich einen Knoten mit Grad 1 habe? Breche ich dann ab?

Ja, das solltest Du, da es ja dann keinen Sinn mehr ergibt, weiterzumachen.


Ich entnehme daraus, dass es durchaus zulässig ist, k = 0 und einen leeren Graphen zurückzugeben? Und das das dann eine Ja-Instanz wäre?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bilbo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.01.2005
Mitteilungen: 2009
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-05-06


Hallo Yggradsill,

2021-05-06 12:12 - yggdrasill in Beitrag No. 3 schreibt:
Ich entnehme daraus, dass es durchaus zulässig ist, k = 0 und einen leeren Graphen zurückzugeben? Und das das dann eine Ja-Instanz wäre?

Genau, für den leeren Graphen ist die leere Menge nach Definition eine Knotenüberdeckung, also ist das eine Ja-Instanz.

Viele Grüße
Thorsten



-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
yggdrasill
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.05.2021
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-10


Sehr schön, danke!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
yggdrasill hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]