Hypergraph-Parameter: Struktur und Algorithmische Anwendung

Die meisten grundlegenden Probleme, die in verschiedenen Bereichen der Informatik und darüber hinaus auftreten, wie z. B. die Erfüllung von Einschränkungen, die Ressourcenzuweisung, das Zeichnen von Graphen, das Lernen neuronaler Netze und viele andere, können nicht effizient gelöst werden: Basierend auf gängigen komplexitätstheoretischen Annahmen lassen diese Probleme keine Algorithmen mit polynomialen Laufzeiten zu. Trotz ihrer Unterschiede haben alle diese Probleme ein gemeinsames Merkmal: Ihre Komplexität ergibt sich aus einem exponentiellen Suchraum, auch wenn die Struktur einer potenziellen Lösung relativ einfach ist. Die parametrisierte Komplexität bietet einen leistungsstarken Satz von Werkzeugen, um die Unlösbarkeit solcher Probleme zu überwinden, indem effiziente Algorithmen für bestimmte Klassen von Instanzen entworfen werden. Dieser Prozess erfolgt oft schrittweise, wenn auf die Identifizierung einer grundlegenden Eigenschaft (eines Parameters), die einen schnellen Algorithmus ermöglicht, sequenzielle Lockerungen folgen, die zu möglichst allgemeinen Einschränkungen führen. Viele Probleme lassen eine natürliche Graphdarstellung zu, was zur Entwicklung einer reichen Hierarchie struktureller Graphparameter geführt hat. Es wurden zahlreiche Arbeiten zur parametrisierten Komplexität durchgeführt, bei denen die Grenzen der Handhabbarkeit in Bezug auf diese Parameter untersucht wurden. Graphen eignen sich gut zum Ausdrücken von Problemen, die sich mit Elementen einer Menge (die zu Knoten werden) und binären Funktionen oder Relationen auf dieser Menge (kodiert als Kanten, möglicherweise gewichtet) befassen. Im Vergleich zu ihnen bieten Hypergraphen zusätzliche Ausdruckskraft, indem sie es ermöglichen, Funktionen und Relationen beliebiger Komplexität darzustellen, indem sie als Hyperkanten kodiert werden. Obwohl es Bemühungen gab, Hypergraphenanaloga für gut etablierte Graphenparameter zu entwickeln, ist der Werkzeugkasten für den Umgang mit Hypergraphen immer noch viel eingeschränkter als der für Graphen. Das Ziel dieses Projekts ist es, das Verständnis bestehender Hypergraphenparameter zu vertiefen und neue Parameter zu entdecken, um die Lücken in der parametrisierten Komplexität von Hypergraphenproblemen zu schließen.