Problemkern

In der theoretischen Informatik bezeichnet der Problemkern (engl. problemkernel) den algorithmisch „schwierig“ entscheidbaren Teil einer Instanz eines NP-Schweren Problems. Viele Instanzen NP-schwerer Probleme enthalten Teilprobleme, die leicht entscheidbar sind. Zum Beispiel in vielen Instanzen von Problemen, bei denen eine Teilmenge S von einer Menge M gewählt werden soll, haben Elemente x von M gewisse Eigenschaften, durch die man effizient entscheiden kann, dass x in S sein muss oder nicht in S sein kann.

Die Methode, solche Elemente zu suchen und aus der Instanz zu entfernen, bezeichnet man als Problemkern-Reduktion (engl. kernelization). Die Elemente, die solche Eigenschaften nicht haben und nach Problemkern-Reduktionen übrig sind, bilden den Problemkern der Instanz.

Beispiele

Bei Instanzen G des q-Färbungsproblems können sukzessive Knoten x entfernt werden, deren Grad kleiner als q ist, weil in einer q-Färbung des Restgraphen die Nachbarschaft von x höchstens q-1 Farben enthält, womit mindestens eine Farbe für x übrig ist. Dadurch ist G genau dann q-färbbar, wenn der Graph G’, der sich aus G nach Entfernung des Knotens x ergibt, q-färbbar ist.

Bei Instanzen (G,k) des parametrisierten Knotenüberdeckungsproblems (d. h. bei der Suche nach einer Knotenüberdeckung der Größe k) kann man sukzessive Knoten x auswählen, deren Grad größer als k ist. Diese müssen Teil der Knotenüberdeckung sein, weil die zu x inzidenten Kanten überdeckt werden müssen, wofür anderenfalls nur noch die gesamte Nachbarschaft von x in Frage käme. Dies wären aber mehr als k Knoten, womit sofort das Limit für die Größe der Knotenüberdeckung überschritten wäre. Dadurch besitzt G genau dann eine Knotenüberdeckung der Größe $\leq k$ , wenn G-x eine Knotenüberdeckung der Größe $\leq k-1$ besitzt.

Bei Instanzen G des q-Cliquenproblems können sukzessive Knoten x entfernt werden, deren Grad kleiner als q-1 ist, weil die Knoten einer q-Clique mit den anderen q-1 Knoten der Clique benachbart sind, woraus für diese Knoten ein Grad von mindestens q-1 folgt. Dadurch besitzt G genau dann eine q-Clique, wenn G-x eine q-Clique besitzt.

Das vorausgesetzte Problem muss nicht notwendig entscheidbar oder semi-entscheidbar sein. Zum Beispiel entspricht auch die Entfernung von unerreichbaren Zuständen einer Turingmaschine der Definition einer Problemkern-Reduktion für die (nicht semi-entscheidbare) Frage, ob die Turingmaschine eine partielle Funktion berechnet.

Formale Definition

Sei $P\subseteq M\times \mathbb {N}$ ein parametrisiertes Problem mit einer Norm $|.|$ auf $M$ .

Eine Problemkern-Reduktion ist eine Funktion $f\colon M\times \mathbb {N} \rightarrow M\times \mathbb {N}$ mit den Eigenschaften

$(I,k)\in P\Leftrightarrow (I^{\prime },k^{\prime }):=f(I,k)\in P$ (Äquivalenz)
$|I^{\prime }|\leq |I|$ und $k^{\prime }\leq k$ (Simplifikation)
f ist in Polynomialzeit berechenbar

Problemkern-Reduktionen definieren je eine transitive, wohlfundierte Ordnungsrelation R auf $M\times \mathbb {N}$ . Ein Problemkern einer Instanz (I,k) ist eine R-Normalform von (I,k) bezüglich einer Problemkern-Reduktionsrelation R. Problemkern-Reduktionen sind häufig konfluent, wodurch ihre Normalformen dann eindeutig sind. Daher spricht man oft auch von „dem“ Problemkern einer Instanz, wobei man aber außer Acht lässt, dass andere (möglicherweise noch unbekannte) Problemkern-Reduktionen zu noch kleineren Instanzen führen könnten.

Obere Schranken für die Größe

Jedes entscheidbare, parametrisierte Problem, für das man garantieren kann, dass die Größe des Problemkerns jeder Instanz (I,k) beschränkt ist durch g(k), für eine beliebige Funktion g, ist fixed parameter tractable, da man nach einer Problemkern-Reduktion einen Algorithmus mit beliebiger (endlicher) Laufzeit h auf den Problemkern anwenden kann, womit sich eine Laufzeit von $poly(n)+h(g(k))$ ergibt.

Umgekehrt hat jede Instanz (I,k) eines Problems, das fixed parameter tractable ist, einen Problemkern, der in Polynomialzeit berechenbar ist und dessen Größe durch g(k) beschränkt ist, für eine Funktion g. Beweisskizze: Gegeben sei ein parametrisiertes Problem, das fixed parameter tractable ist, für das also ein Algorithmus existiert, der jede Instanz (I,k) mit einer Laufzeit von $f(k)|I|^{c}$ löst. Eine Problemkern-Reduktion ist nun: wenn |I|<f(k) ist, dann ist (I,k) selbst ein geeigneter Problemkern (dessen Größe durch f(k) beschränkt ist). Anderenfalls kann man den FPT-Algorithmus benutzen, um zu ermitteln ob $(I,k)\in P$ ist. Darauf basierend wählt man als Problemkern eine beliebige (aber fest gewählte) Instanz $I_{\text{ja}}\in P$ oder $I_{\text{nein}}\not \in P$ , womit die Größe jedes Problemkerns beschränkt ist durch $g(k):=\max\{f(k),|I_{\text{ja}}|,|I_{\text{nein}}|\}$ . Entscheidend ist hierbei: Im Fall, dass f(k)<|I| ist, ist die Laufzeit des Algorithmus $f(k)|I|^{c}\leq |I|^{c+1}$ , womit die polynomielle Laufzeit folgt.

Damit stellt sich heraus, dass die Komplexitätsklasse FPT genau der Klasse von parametrisierten Problemen entspricht, deren Problemkerne durch eine Funktion des Parameters beschränkt sind.

Trotzdem ist es auch bei Problemen, die nicht fixed parameter tractable sind, wo also nicht garantiert werden kann, dass der Problemkern relativ klein ist, sinnvoll, Problemkern-Reduktionen am Anfang jedes Rekursionsaufrufs anzuwenden, da sie in der Praxis auch dort große Verbesserungen der Laufzeiten bringen.

Feinere Abstufung von FPT

Die unterschiedlichen Schranken für die Größe des Problemkerns liefern eine feinere Abstufung der Komplexitätsklasse FPT. Zum Beispiel ist das Knotenüberdeckungsproblem „leichter“ als das Min-Multicut Problem auf Bäumen, obwohl beide in FPT sind, weil der Problemkern einer Instanz des Knotenüberdeckungsproblems (nach Nemhauser und Trotter) höchstens Größe 2k hat, wogegen die beste bekannte Problemkern-Reduktion für Min-Multicut auf Bäumen Problemkerne liefert, deren Größe durch $k^{6}$ beschränkt ist. Beide befinden sich aber in der wichtigen Klasse POLYKERNEL, welche die Probleme enthält, deren Instanzen Problemkerne haben, deren Größe durch ein Polynom in k beschränkt ist.

Literatur

Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford 2006, ISBN 0-19-856607-7, (Oxford Lecture Series in Mathematics and its Applications 31).