Problemkern

Ein Problemkern ist ein Teil der Eingabe für einen Algorithmus, der für seine Abarbeitung sehr viel Rechenzeit benötigt. Alles was nicht zum Problemkern gehört, kann, falls sich das Ergebnis des Programmes nicht ändert, eliminiert werden und stellt für die Verarbeitung im Anschluss keinen Ballast mehr dar.

Beispiele

Gegeben sei eine Instanz des Entscheidungsproblems 3-COLORING durch einen Graphen G und einen Parameter k > 1. Nun wäre es denkbar, dass im Graphen sehr viele Bäume enthalten sind. Da diese stets zwei-färbbar sind, können sie aus dem Graphen gelöscht werden. Der von den verbleibenden Knoten induzierte Teilgraph ist eine Art "Problemkern". Da 3-COLORING NP-vollständig ist, geht die Anzahl der Knoten exponentiell in die Gesamtlaufzeit des Algorithmus ein. Somit ist die Laufzeit des Programmes auf dem Problemkern im Vergleich zum kompletten Graphen signifikant.

Da allerdings nicht für jeden Graphen garantiert werden kann, dass er einen Baum als Teilgraph enthält, ist die Macht dieser Vorverarbeitung gering (im schlimmsten Fall kann man keinen Knoten löschen). Die Anforderungen an einen Algorithmus zur Extraktion des Problemkernes im Sinne der Fixed Parameter Algorithmen sind daher, wie im folgenden ausgeführt, etwas schärfer, als dass sie eine als Funktion von k darstellbare Verkleinerung des Ausgangsproblemes fordern.

Formale Definition

Gegeben sei ein rekursives Entscheidungsproblem L der theoretischen Informatik durch dessen Input (I, k). Ein Problemkern ist ein neuer Input (I', k'), für den gilt:

• Läuft der Algorithmus auf dem Problemkern, erhält man das selbe Resultat: $(I,k)\in L\Longleftrightarrow (I',k')\in L$
• Das Problem wird nicht aufgeweicht: $k'\leq k$
• Die Länge bzw. Größe des Problemkerns hängt nur von k ab: $|I'|\leq g(k)$
• Berechenbarkeit von (I', k') in Polynomialzeit

Die Berechnung von ('I, k') aus der Eingabe (I, k) wird von einem Problemreduktionsalgorithmus vorgenommen.

Verwendung

Existiert ein solcher Algorithmus für L, kann das Wortproblem der Sprache L effizienter gelöst werden:

Eingabe: (I, k)

Das Wortproblem für L wird nun wie folgt berechnet:

1. Berechne den Problemkern (I', k') mittels des Problemreduktionsalgorithmus
2. Lasse den Entscheidungsalgorithmus für L auf (I', k') laufen
3. Akzeptiere genau dann, falls $(I',k')\in L$

Typischer Weise verwendet man solche Verfahren für NP-vollständige Probleme $L\in NPC$.

Bedeutung

Erst seit kurzem wird aktiv an Problemreduktionsalgorithmen geforscht. Da besonders die Herleitung der oberen Größenschranke für den Problemkern g sehr mathematisch anspruchsvoll ist, wurden erst für sehr wenige Probleme L brauchbare Algorithmen gefunden. Dazu zählen z.B. MAX-SAT, Cluster-Editing oder Dominating Set in Planar Graphs.

In Abgrenzung zu Randomisierungs- oder Approximationsalgorithmen weisen sich Problemreduktionsalgorithmen jedoch als sehr praktische Helfer zur exakten (wenn auch nach wie vor nur in exponentieller Laufzeit ermittelbaren) Lösung NP-vollständiger Entscheidungsprobleme aus.

Literatur

• Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31, 2006, 0-19-856607-7