Kernelisierung für H-Färbung

Für einen festen Graphen H fragt das H-Färbungsproblem, ob ein gegebener Graph eine kantenbewahrende Funktion von seiner Menge an Knoten auf die von H zulässt. Ein grundlegender Satz von Hell und Nešetřil besagt, dass das H-Färbungsproblem NP-schwer ist, wann immer H schleifenfrei und nicht bipartit ist. Ein Ergebnis von Jansen und Pieterse impliziert, dass für jeden Graph H das H-Färbungsproblem, parametriert durch die Größe der Knotenüberdeckung k, einen Kern mit O(k^{Δ(H)}) Knoten und einer Bitgröße, die durch O(k^{Δ(H)} k) beschränkt ist, zulässt, wobei Δ(H) den maximalen Grad in H bezeichnet. Im Fall, dass H ein vollständiger Graph mit mindestens drei Knoten ist, entspricht diese Kerngröße nahezu den bedingten unteren Schranken, die von Jansen und Kratsch sowie von Jansen und Pieterse festgelegt wurden. Dieses Papier präsentiert neue obere und untere Schranken für die Kerngröße von H-Färbungsproblemen, die nach der Knotenüberdeckungszahl parametriert sind. Die oberen Schranken ergeben sich aus zwei Kernelisierungsalgorithmen. Der erste ist rein kombinatorisch und seine Größe wird durch eine strukturelle Größe des Graphen H, genannt die Anzahl der Nicht-Nachbarn, bestimmt. Als Anwendungen erhalten wir Kerne, deren Größe durch ein fixes Polynom für natürliche Klassen von Graphen H mit unbegrenzt maximalem Grad beschränkt ist. Auffallender ist, dass wir zeigen, dass für fast jeden Graphen H der Grad des Polynoms, das die Größe unseres kombinatorischen Kerns beschränkt, nur logarithmisch in Δ(H) wächst. Unser zweiter Kern nutzt linear-algebraische Werkzeuge und bezieht sich auf die Vorstellung von treuen unabhängigen Darstellungen von Graphen. Er verstärkt die allgemeine Schranke aus früheren Arbeiten und liefert unter anderem nahezu optimale Kerne für Probleme bezüglich der Dimension orthogonaler Graphdarstellungen über endlichen Körpern. Wir ergänzen diese Ergebnisse mit bedingten unteren Schranken, wodurch wir die Kernkomplexität des Problems für verschiedene Zielgraphen H nahezu klären.