Graphenalgorithmik

Matching in einem Baum

Ein Matching in einem Graphen \(G=(V,E)\) ist eine Kantenmenge \(M \subseteq E\), sodass zwei Kanten aus \(M\) nie einen adjazenten Knoten teilen. Für zwei Kanten \(e,e' \in M\) gilt also \(e \cap e' = \emptyset\).

Finde einen Linearzeit-Algorithmus, der ein maximales Matching in einem Baum findet.

Feedback Edge Set

Sei \(G=(V, E)\) ein ungerichteter Graph. Wir nennen eine Kantenmenge \(F \subseteq E\) ein Feedback Edge Set, wenn jeder Kreis in \(G\) mindestens eine Kante in \(F\) hat.

Finden einen effizienten Algorithmus, der ein Feedback Arc Set minimaler Größe findet.

Online MST

Sei \(G\) ein ungerichteter Graph, zu dem der MST bereits berechnet wurde. Nun fügen wir eine neue Kante (aber keinen neuen Knoten) in \(G\) ein. Finde einen \(O(|V|)\) Algorithmus, der den MST akutalisiert, sodass er ein MST des vergrößerten Graphen ist.

Transitive Hülle

Sei \(G=(V, E)\) ein gerichteter Graph. Die Transitive Hülle \([G]\) hat nun die gleichen Kanten wie \(G\) und genau dann eine Kante \(v_1 \rightarrow v_2\), wenn es einen Pfad \(v_1 \rightsquigarrow v_2\) in \(G\) gibt.

Finde einen effizienten Algorithmus, um \([G]\) zu berechnen.

Unabhängiges Vertex-Cover

Zur Erinnerung: Wir nennen eine Knotenmenge \(I \subseteq V\) unabhängig, wenn es zwischen zwei Knoten aus \(I\) nie eine Kante gibt. Wir nennen eine Menge \(C \subseteq V\) eine Knotenüberdeckung, wenn zu jeder Kante \(e \in E\) mindestens einer der adjazenten Knoten in \(C\) liegt.

Finde einen effizienten Algorithmus, der feststellt, ob es in einem gegebenen Graphen eine unabhängiges Knotenüberdeckung gibt.

Ausdruckspunkte

Sei \(G=(V,E)\) ein ungerichteter, zusammenhängender Graph. Finde einen effizienten Algorithmus, der die Knoten von \(G\) so sortiert, dass die Löschung aus dem Graphen in dieser Reihenfolge nie dazu führt, dass der Graph nicht zusammenhängend ist.

Formale Sprachen und Automaten

\(L^R\)

Zeige, dass die Umkehrung einer regulären Sprache wieder eine reguläre Sprache ist. Dabei definieren wir die Umkehrung einer Sprache als die Umkehrung jedes Wortes in der Sprache.

Addition

Sei \(\Sigma=\{0,1, +, =\}\). Wir definieren die Sprache \(ADD = \{a+b=z \mid a, b, z \text{ sind Binärzahlen und die Gleichung gilt}\}\), die korrekte Additionsausdrücke beinhaltet. Zeige, dass \(ADD\) nicht regulär ist.

Durchschnitt von regulären und kontextfreien Sprachen

Sei \(L_1\) kontextfrei und \(L_2\) regulär. Zeige, dass \(L_1 \cap L_2\) kontextfrei ist.

Klammer-Regeln

Formalisiere die folgende Sprache und zeige dann, dass sie nicht regulär ist.

Wir betrachten Ausdrücke aus Klammern, also aus ( und ). Ein Wort ist in unserer Sprache, wenn die zugehörigen Klammen so in einem validen arithmetischen Ausdruck vorkommen könnten, sprich, wenn sie sich nicht kreuzen.

Pump it Up!

Zeige, dass die folgende Sprache nicht regulär ist: \(\{0^n 1 0^n \mid n \ge 1\}\).

P vs NP

Pfade

Sei \(G\) ein ungerichteter Graph. Wir definieren die Sprachen

\[ SPATH = \{(G, a, b, k) \mid \text{es gibt einen Pfad der Länge maximal } k \text{ von } a \text{ nach } b\} \\ LPATH = \{(G, a, b, k) \mid \text{es gibt einen Pfad der Länge mindestens } k \text{ von } a \text{ nach } b\} \\ \]

Zeige \(SPATH \in P\) und \(LPATH \in NPC\).

Double-SAT

Sei \(\varphi\) eine aussagenlogische Formel. Dann sei \(\varphi \in DOUBLESAT\) genau dann, wenn \(\varphi\) mindestens zwei verschiedene erfüllende Belegungen hat. Zeige, dass \(DOUBLESAT\) NP-vollständig ist.

Matching

Sei \(G\) ein ungerichteter Graph. Wir nennen eine Kantemenge \(M \subseteq E(G)\) ein Matching, wenn zwei unterschiedliche Kanten nie einen gemeisamen Knoten haben. Also für alle \(e \ne e'\) gilt auch \(e \cap e' = \{\}\).

Das Problem, folgende Frage für einen ungerichteten Graphen \(G\) zu entscheiden, ist in polynomieller Zeit lösbar: Hat \(G\) ein Matching der Größe \(k\).

Set-Splitting

Das \(SET-SPLITTING\) Problem beinhaltet Tupel \((S, C)\), wobei \(S\) eine endliche Menge ist und \(C = \{C_1, \dots, C_n\}\) eine Menge von Teilmengen von \(S\). Diese Tupel sind nun genau dann in \(SET-SPLITTING\), wenn die Elemente von \(S\) so rot oder blau gefärbt werden können, dass keine der Mengen \(C_i\) nur Elemente einer Farbe enthält.

Zeige, dass \(SET-SPLITTING \in NPC\).

Minesweeper

Wir wollen einen ungerichteten Graphen betrachten und so tun, als ob er ein Minesweeper Feld wäre. Nun seien einige der Knoten mit einer natürlichen Zahl beschriftet. Wir fragen uns, ob wir einen Teil der unbeschrifteten Knoten so verminen können, dass jeder beschriftete Knoten genau so viele benachbarte Minen-Knoten hat, wie seine Beschriftung angibt.

Zeige, dass dieses Problem NP-vollständig ist.

Ich habe hierzu einen Blog-Post geschrieben.

\(\text{MAX-}k\text{-SAT}\)

Wir definieren die Problem \(\text{MAX-}k\text{-SAT}\). Dabei ist die Eingabe ein Tupel \((\varphi, l)\). Dabei ist \(\varphi\) eine Aussgenform in \(k-\text{KNF}\) und \(l\) eine natürliche Zahl. Wir fragen nun, ob es eine Belegung gibt, die mindestens \(l\) Klauseln erfüllt.

Einfach: Zeige \(\text{MAX-}3\text{-SAT} \in NPC\). Schwer: Zeige \(\text{MAX-}2\text{-SAT} \in NPC\).