Julius Albert Gregor Lagodzinski

• Homomorphisms are a fundamental concept in mathematics expressing the similarity of structures. They provide a framework that captures many of the central problems of computer science with close ties to various other fields of science. Thus, many studies over the last four decades have been devoted to the algorithmic complexity of homomorphism problems. Despite their generality, it has been found that non-uniform homomorphism problems, where the target structure is fixed, frequently feature complexity dichotomies. Exploring the limits of these dichotomies represents the common goal of this line of research. We investigate the problem of counting homomorphisms to a fixed structure over a finite field of prime order and its algorithmic complexity. Our emphasis is on graph homomorphisms and the resulting problem #_{p}Hom[H] for a graph H and a prime p. The main research question is how counting over a finite field of prime order affects the complexity. In the first part of this thesis, we tackle the research question in itsHomomorphisms are a fundamental concept in mathematics expressing the similarity of structures. They provide a framework that captures many of the central problems of computer science with close ties to various other fields of science. Thus, many studies over the last four decades have been devoted to the algorithmic complexity of homomorphism problems. Despite their generality, it has been found that non-uniform homomorphism problems, where the target structure is fixed, frequently feature complexity dichotomies. Exploring the limits of these dichotomies represents the common goal of this line of research. We investigate the problem of counting homomorphisms to a fixed structure over a finite field of prime order and its algorithmic complexity. Our emphasis is on graph homomorphisms and the resulting problem #_{p}Hom[H] for a graph H and a prime p. The main research question is how counting over a finite field of prime order affects the complexity. In the first part of this thesis, we tackle the research question in its generality and develop a framework for studying the complexity of counting problems based on category theory. In the absence of problem-specific details, results in the language of category theory provide a clear picture of the properties needed and highlight common ground between different branches of science. The proposed problem #Mor^{C}[B] of counting the number of morphisms to a fixed object B of C is abstract in nature and encompasses important problems like constraint satisfaction problems, which serve as a leading example for all our results. We find explanations and generalizations for a plethora of results in counting complexity. Our main technical result is that specific matrices of morphism counts are non-singular. The strength of this result lies in its algebraic nature. First, our proofs rely on carefully constructed systems of linear equations, which we know to be uniquely solvable. Second, by exchanging the field that the matrix is defined by to a finite field of order p, we obtain analogous results for modular counting. For the latter, cancellations are implied by automorphisms of order p, but intriguingly we find that these present the only obstacle to translating our results from exact counting to modular counting. If we restrict our attention to reduced objects without automorphisms of order p, we obtain results analogue to those for exact counting. This is underscored by a confluent reduction that allows this restriction by constructing a reduced object for any given object. We emphasize the strength of the categorial perspective by applying the duality principle, which yields immediate consequences for the dual problem of counting the number of morphisms from a fixed object. In the second part of this thesis, we focus on graphs and the problem #_{p}Hom[H]. We conjecture that automorphisms of order p capture all possible cancellations and that, for a reduced graph H, the problem #_{p}Hom[H] features the complexity dichotomy analogue to the one given for exact counting by Dyer and Greenhill. This serves as a generalization of the conjecture by Faben and Jerrum for the modulus 2. The criterion for tractability is that H is a collection of complete bipartite and reflexive complete graphs. From the findings of part one, we show that the conjectured dichotomy implies dichotomies for all quantum homomorphism problems, in particular counting vertex surjective homomorphisms and compactions modulo p. Since the tractable cases in the dichotomy are solved by trivial computations, the study of the intractable cases remains. As an initial problem in a series of reductions capable of implying hardness, we employ the problem of counting weighted independent sets in a bipartite graph modulo prime p. A dichotomy for this problem is shown, stating that the trivial cases occurring when a weight is congruent modulo p to 0 are the only tractable cases. We reduce the possible structure of H to the bipartite case by a reduction to the restricted homomorphism problem #_{p}Hom^{bip}[H] of counting modulo p the number of homomorphisms between bipartite graphs that maintain a given order of bipartition. This reduction does not have an impact on the accessibility of the technical results, thanks to the generality of the findings of part one. In order to prove the conjecture, it suffices to show that for a connected bipartite graph that is not complete, #_{p}Hom^{bip}[H] is #_{p}P-hard. Through a rigorous structural study of bipartite graphs, we establish this result for the rich class of bipartite graphs that are (K_{3,3}\{e}, domino)-free. This overcomes in particular the substantial hurdle imposed by squares, which leads us to explore the global structure of H and prove the existence of explicit structures that imply hardness.…
• Homomorphismen sind ein grundlegendes Konzept der Mathematik, das die Ähnlichkeit von Strukturen ausdrückt. Sie bieten einen Rahmen, der viele der zentralen Probleme der Informatik umfasst und enge Verbindungen zu verschiedenen Wissenschaftsbereichen aufweist. Aus diesem Grund haben sich in den letzten vier Jahrzehnten viele Studien mit der algorithmischen Komplexität von Homomorphismusproblemen beschäftigt. Trotz ihrer Allgemeingültigkeit wurden Komplexitätsdichotomien häufig für nicht-uniforme Homomorphismusprobleme nachgewiesen, bei denen die Zielstruktur fixiert ist. Die Grenzen dieser Dichotomien zu erforschen, ist das gemeinsame Ziel dieses Forschungskalküls. Wir untersuchen das Problem und seine algorithmische Komplexität, Homomorphismen zu einer festen Struktur über einem endlichen Körper mit Primzahlordnung zu zählen. Wir konzentrieren uns auf Graphenhomomorphismen und das daraus resultierende Problem #_{p}Hom[H] für einen Graphen H und eine Primzahl p. Die Hauptforschungsfrage ist, wie das Zählen über einem endlichenHomomorphismen sind ein grundlegendes Konzept der Mathematik, das die Ähnlichkeit von Strukturen ausdrückt. Sie bieten einen Rahmen, der viele der zentralen Probleme der Informatik umfasst und enge Verbindungen zu verschiedenen Wissenschaftsbereichen aufweist. Aus diesem Grund haben sich in den letzten vier Jahrzehnten viele Studien mit der algorithmischen Komplexität von Homomorphismusproblemen beschäftigt. Trotz ihrer Allgemeingültigkeit wurden Komplexitätsdichotomien häufig für nicht-uniforme Homomorphismusprobleme nachgewiesen, bei denen die Zielstruktur fixiert ist. Die Grenzen dieser Dichotomien zu erforschen, ist das gemeinsame Ziel dieses Forschungskalküls. Wir untersuchen das Problem und seine algorithmische Komplexität, Homomorphismen zu einer festen Struktur über einem endlichen Körper mit Primzahlordnung zu zählen. Wir konzentrieren uns auf Graphenhomomorphismen und das daraus resultierende Problem #_{p}Hom[H] für einen Graphen H und eine Primzahl p. Die Hauptforschungsfrage ist, wie das Zählen über einem endlichen Körper mit Primzahlordnung die Komplexität beeinflusst. Im ersten Teil wird die Forschungsfrage in ihrer Allgemeinheit behandelt und ein Rahmen für die Untersuchung der Komplexität von Zählproblemen auf der Grundlage der Kategorientheorie entwickelt. Losgelöst von problemspezifischen Details liefern die Ergebnisse in der Sprache der Kategorientheorie ein klares Bild der benötigten Eigenschaften und zeigen Gemeinsamkeiten zwischen verschiedenen Wissenschaftsgebieten auf. Das vorgeschlagene Problem #Mor^{C}[B] des Zählens der Anzahl von Morphismen zu einem festen Objekt B von C ist abstrakter Natur und umfasst wichtige Probleme wie Constraint Satisfaction Problems, die als leitendes Beispiel für alle unsere Ergebnisse dienen. Wir finden Erklärungen und Verallgemeinerungen für eine Vielzahl von Ergebnissen in der Komplexitätstheorie von Zählproblemen. Unser wichtigstes technisches Ergebnis ist, dass bestimmte Matrizen von Morphismenzahlen nicht singulär sind. Die Stärke dieses Ergebnisses liegt in seiner algebraischen Natur. Erstens basieren unsere Beweise auf sorgfältig konstruierten linearen Gleichungssystemen, von denen wir wissen, dass sie eindeutig lösbar sind. Zweitens, indem wir den Körper, über dem die Matrix definiert ist, durch einen endlichen Körper der Ordnung p ersetzen, erhalten wir analoge Ergebnisse für das modulare Zählen. Für letztere sind Annullierungen durch Automorphismen der Ordnung p impliziert, aber faszinierenderweise stellen diese das einzige Hindernis für die Übertragung unserer Ergebnisse von der exakten auf die modulare Zählung dar. Wenn wir unsere Aufmerksamkeit auf reduzierte Objekte ohne Automorphismen der Ordnung p beschränken, erhalten wir Ergebnisse, die zu denen des exakten Zählens analog sind. Dies wird durch eine konfluente Reduktion unterstrichen, die für jedes beliebige Objekt ein reduziertes Objekt konstruiert. Wir heben die Stärke der kategorialen Perspektive durch die Anwendung des Dualitätsprinzips hervor, das direkte Konsequenzen für das duale Problem des Zählens der Anzahl der Morphismen von einem fixen Objekts aus liefert. Im zweiten Teil konzentrieren wir uns auf Graphen und das Problem #_{p}Hom[H]. Wir stellen die Vermutung auf, dass Automorphismen der Ordnung p alle möglichen Annullierungen erklären und dass das Problem #_{p}Hom[H] für einen reduzierten Graphen H eine Komplexitätsdichotomie analog zu der aufweist, die von Dyer und Greenhill für das exakte Zählen bewiesen wurde. Dies stellt eine Verallgemeinerung der Vermutung von Faben und Jerrum für den Modulus 2 dar. Das Kriterium für die effiziente Lösbarkeit ist, dass H lediglich aus vollständigen bipartiten und reflexiven vollständigen Graphen besteht. Basierend auf den Ergebnisse des ersten Teils zeigen wir, dass die Vermutung Dichotomien für alle Quantenhomomorphismenprobleme impliziert, insbesondere für das Zählen modulo p von Homomorphismen surjektiv auf Knoten und von Verdichtungen. Da die effizient lösbaren Fälle in der Dichotomie durch triviale Berechnungen gelöst werden, bleibt es, die unlösbaren Fälle zu untersuchen. Als erstes Problem in einer Reihe von Reduktionen, deren Ziel es ist, Härte zu implizieren, verwenden wir das Problem des Zählens gewichteter unabhängiger Mengen in einem bipartiten Graphen modulo p. Für dieses Problem beweisen wir eine Dichotomie, die besagt, dass nur die trivialen Fälle effizient lösbar sind. Diese treten auf, wenn ein Gewicht kongruent modulo p zu 0 ist. Durch eine Reduktion auf das eingeschränkte Homomorphismusproblem #_{p}Hom^{bip}[H] reduzieren wir die mögliche Struktur von H auf den bipartiten Fall. Hierbei handelt es sich um das Problem des Zählens modulo p der Homomorphismen zwischen bipartiten Graphen, die eine gegebene Ordnung der Bipartition erhalten. Dank der Allgemeingültigkeit der Ergebnisse des ersten Teils hat diese Reduktion keinen Einfluss auf die Verfügbarkeit der technischen Ergebnisse. Für einen Beweis der Vermutung genügt es zu zeigen, dass #_{p}Hom^{bip}[H] für einen zusammenhängenden und nicht vollständigen bipartiten Graphen #_{p}P-schwer ist. Durch eine rigorose Untersuchung der Struktur von bipartiten Graphen beweisen wir dieses Ergebnis für die umfangreiche Klasse von bipartiten Graphen, die (K_{3,3}\{e}, domino)-frei sind. Dies überwindet insbesondere die substantielle Hürde, die durch Quadrate gegeben ist und uns dazu veranlasst, die globale Struktur von H zu untersuchen und die Existenz expliziter Strukturen zu beweisen, die Härte implizieren.…