In this thesis, we investigate graphs and hypergraphs that have (relaxed) product structures. In the class of graphs, we discuss in detail \\emph{RSP-relations}, a relaxation of relations fulfilling the square property and therefore of the product relation $\\sigma$, that identifies the copies of the prime factors of a graph w.r.t. the Cartesian product. For $K_{2,3}$-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially. Explicit constructions of such relations in complete and complete bipartite graphs are given. Furthermore, we establish the close connection of (\\emph{well-behaved}) RSP-relations to \\mbox{(quasi-)covers} of graphs and equitable partitions. Thereby, we characterize the existence of non-trivial RSP-relations by means of the existence of spanning subgraphs that yield quasi-covers of the graph under investigation. We show, how equitable partitions on the vertex set of a graph $G$ arise in a natural way from well-behaved RSP-relations on $E(G)$. These partitions in turn give rise to quotient graphs that have rich product structure even if $G$ itself is prime. This product structure of the quotient graph is still retained even for RSP-relations that are not well-behaved. Furthermore, we will see that a (finest) RSP-relation of a product graph can be obtained easily from (finest) RSP-relations on the prime factors w.r.t. certain products and in what manner the quotient graphs of the product w.r.t. such an RSP-relation result from the quotient graphs of the factors and the respective product. In addition, we examine relations on the edge sets of \\emph{hyper}graphs that satisfy the grid property, the hypergraph analog of the square property. We introduce the \\emph{strong} and the \\emph{relaxed} grid property as variations of the grid property, the latter generalizing the relaxed square property. We thereby show, that many, although not all results for graphs and the (relaxed) square property can be transferred to hypergraphs. Similar to the graph case, any equivalence relation $R$ on the edge set of a hypergraph $H$ that satisfies the relaxed grid property induces a partition of the vertex set of $H$ which in turn determines quotient hypergraphs that have non-trivial product structures. Besides, we introduce the notion of \\emph{(Cartesian) hypergraph bundles}, the analog of (Cartesian) graph bundles and point out the connection between the grid property and hypergraph bundles. Finally, we show that every connected thin hypergraph $H$ has a unique prime factorization with respect to the normal and strong (hypergraph) product. Both products coincide with the usual strong \\emph{graph} product whenever $H$ is a graph. We introduce the notion of the Cartesian skeleton of hypergraphs as a natural generalization of the Cartesian skeleton of graphs and prove that it is uniquely defined for thin hypergraphs. Moreover, we show that the Cartesian skeleton of thin hypergraphs and its PFD w.r.t. the strong and the normal product can be computed in polynomial time.

In this thesis, we investigate graphs and hypergraphs that have (relaxed) product structures. In the class of graphs, we discuss in detail \\emph{RSP-relations}, a relaxation of relations fulfilling the square property and therefore of the product relation $\\sigma$, that identifies the copies of the prime factors of a graph w.r.t. the Cartesian product. For $K_{2,3}$-free graphs finest RSP-relations can be computed in polynomial-time. In general, however, they are not unique and their number may even grow exponentially. Explicit constructions of such relations in complete and complete bipartite graphs are given. Furthermore, we establish the close connection of (\\emph{well-behaved}) RSP-relations to \\mbox{(quasi-)covers} of graphs and equitable partitions. Thereby, we characterize the existence of non-trivial RSP-relations by means of the existence of spanning subgraphs that yield quasi-covers of the graph under investigation. We show, how equitable partitions on the vertex set of a graph $G$ arise in a natural way from well-behaved RSP-relations on $E(G)$. These partitions in turn give rise to quotient graphs that have rich product structure even if $G$ itself is prime. This product structure of the quotient graph is still retained even for RSP-relations that are not well-behaved. Furthermore, we will see that a (finest) RSP-relation of a product graph can be obtained easily from (finest) RSP-relations on the prime factors w.r.t. certain products and in what manner the quotient graphs of the product w.r.t. such an RSP-relation result from the quotient graphs of the factors and the respective product. In addition, we examine relations on the edge sets of \\emph{hyper}graphs that satisfy the grid property, the hypergraph analog of the square property. We introduce the \\emph{strong} and the \\emph{relaxed} grid property as variations of the grid property, the latter generalizing the relaxed square property. We thereby show, that many, although not all results for graphs and the (relaxed) square property can be transferred to hypergraphs. Similar to the graph case, any equivalence relation $R$ on the edge set of a hypergraph $H$ that satisfies the relaxed grid property induces a partition of the vertex set of $H$ which in turn determines quotient hypergraphs that have non-trivial product structures. Besides, we introduce the notion of \\emph{(Cartesian) hypergraph bundles}, the analog of (Cartesian) graph bundles and point out the connection between the grid property and hypergraph bundles. Finally, we show that every connected thin hypergraph $H$ has a unique prime factorization with respect to the normal and strong (hypergraph) product. Both products coincide with the usual strong \\emph{graph} product whenever $H$ is a graph. We introduce the notion of the Cartesian skeleton of hypergraphs as a natural generalization of the Cartesian skeleton of graphs and prove that it is uniquely defined for thin hypergraphs. Moreover, we show that the Cartesian skeleton of thin hypergraphs and its PFD w.r.t. the strong and the normal product can be computed in polynomial time.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \'komprimiertes Wortproblem\' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.

Wir beschäftigen uns mit Problemen der algorithmischen Gruppentheorie und untersuchen dabei die Komplexität von komprimierten Versionen des Wortproblems und des Konjugationsproblems für endlich erzeugte Gruppen. Das Wortproblem fragt für eine feste, endlich erzeugte Gruppe ob ein gegebenes Wort über der Erzeugermenge das neutrale Element der Gruppe repräsentiert. Wir betrachten das gegebene Wort jedoch in einer komprimierten Form, als Straight-line Program (SLP) und untersuchen die Komplexität dieses Problems, das wir \''komprimiertes Wortproblem\'' nennen. SLPs sind kontextfreie Grammatiken, die genau einen String erzeugen. Die Eingabegröße ist dabei stets die Größe des gegebenen SLPs. Eine Hauptmotivation ist dabei, dass für eine feste endlich erzeugte Gruppe das Wortproblem ihrer Automorphismengruppe durch eine Turingmaschine in Polynomialzeit auf das komprimierte Wortproblem der Gruppe selbst reduzierbar ist. Wir untersuchen das komprimierte Wortproblem für die verbreiteten Gruppenerweiterungen HNN-Erweiterungen (amalgamierte Produkte und Graphprodukte) und können zeigen, dass sich Instanzen des komprimierten Wortproblems von einer Turingmaschine in Polynomialzeit auf Instanzen des komprimierten Wortproblems der Basisgruppe (respektive Basisgruppen und Knotengruppen) reduzieren lassen. Weiterhin zeigen wir, dass das komprimierte Wortproblem für endlich erzeugte nilpotente Gruppen von einer Turingmaschine in Polynomialzeit entscheidbar ist. Wir betrachten außerdem eine komprimierte Variante des Konjugationsproblems. Das unkomprimierte Konjugationsproblem fragt für zwei gegebene Wörter über den Erzeugern einer festen endlich erzeugten Gruppe, ob sie in dieser Gruppe konjugiert sind. Beim komprimierten Konjugationsproblem besteht die Eingabe aus zwei SLPs und es wird gefragt, ob die beiden Wörter die von den SLPs erzeugt werden in der Gruppe konjugierte Elemente präsentieren. Wir konnten zeigen, dass sich das komprimierte Konjugationsproblem für Graphgruppen in Polynomialzeit entscheiden lässt. Weiterhin haben wir das Wortproblem der äußeren Automorphismengruppen von Graphprodukten endlich erzeugter Gruppen untersucht. Durch den engen Zusammenhang des komprimierten Konjugationsproblems einer Gruppe mit dem Wortproblem der äußeren Automorphismengruppe konnten wir zeigen, dass sich das Wortproblem der äußeren Automorphismengruppe eines Graphprodukts von endlich erzeugten Gruppen durch eine Turingmaschine in Polynomialzeit auf Instanzen von simultanen komprimierten Konjugationsproblemen der Knotengruppen und Instanzen von komprimierten Wortproblemen der Knotengruppen reduzieren lässt. Als Anwendung gelten obige Resultate auch für right-angled Coxetergruppen und Graphgruppen, da beide spezielle Graphprodukte sind. So folgt beispielsweise, dass das komprimierte Wortproblem einer right-angled Coxetergruppe in Polynomialzeit entscheidbar ist.