Counting patterns in strings and graphs

Abstract

We study problems related to finding and counting patterns in strings and graphs. In the string-regime, we are interested in counting how many substring of a text 𝑇 are at Hamming (or edit) distance at most 𝑘 to a pattern 𝑃. Among others, we are interested in the fully-compressed setting, where both 𝑇 and 𝑃 are given in a compressed representation. For both distance measures, we give the first algorithm that runs in (almost) linear time in the size of the compressed representations. We obtain the algorithms by new and tight structural insights into the solution structure of the problems. In the graph-regime, we study problems related to counting homomorphisms between graphs. In particular, we study the parameterized complexity of the problem #IndSub(𝛷), where we are to count all 𝑘-vertex induced subgraphs of a graph that satisfy the property 𝛷. Based on a theory of Lovász, Curticapean et al., we express #IndSub(𝛷) as a linear combination of graph homomorphism numbers to obtain #W[1]-hardness and almost tight conditional lower bounds for properties 𝛷 that are monotone or that depend only on the number of edges of a graph. Thereby, we prove a conjecture by Jerrum and Meeks. In addition, we investigate the parameterized complexity of the problem #Hom(ℋ → 𝒢) for graph classes ℋ and 𝒢. In particular, we show that for any problem 𝑃 in the class #W[1], there are classes ℋ_𝑃 and 𝒢_𝑃 such that 𝑃 is equivalent to #Hom(ℋ_𝑃 → 𝒢_𝑃 ).

Wir untersuchen Probleme im Zusammenhang mit dem Finden und Zählen von Mustern in Strings und Graphen. Im Stringbereich ist die Aufgabe, alle Teilstrings eines Strings 𝑇 zu bestimmen, die eine Hamming- (oder Editier-)Distanz von höchstens 𝑘 zu einem Pattern 𝑃 haben. Unter anderem sind wir am voll-komprimierten Setting interessiert, in dem sowohl 𝑇, als auch 𝑃 in komprimierter Form gegeben sind. Für beide Abstandsbegriffe entwickeln wir die ersten Algorithmen mit einer (fast) linearen Laufzeit in der Größe der komprimierten Darstellungen. Die Algorithmen nutzen neue strukturelle Einsichten in die Lösungsstruktur der Probleme. Im Graphenbereich betrachten wir Probleme im Zusammenhang mit dem Zählen von Homomorphismen zwischen Graphen. Im Besonderen betrachten wir das Problem #IndSub(𝛷), bei dem alle induzierten Subgraphen mit 𝑘 Knoten zu zählen sind, die die Eigenschaft 𝛷 haben. Basierend auf einer Theorie von Lovász, Curticapean, Dell, and Marx drücken wir #IndSub(𝛷) als Linearkombination von Homomorphismen-Zahlen aus um #W[1]-Härte und fast scharfe konditionale untere Laufzeitschranken zu erhalten für 𝛷, die monoton sind oder nur auf der Kantenanzahl der Graphen basieren. Somit beweisen wir eine Vermutung von Jerrum and Meeks. Weiterhin beschäftigen wir uns mit der Komplexität des Problems #Hom(ℋ → 𝒢) für Graphklassen ℋ und 𝒢. Im Besonderen zeigen wir, dass es für jedes Problem 𝑃 in #W[1] Graphklassen ℋ_𝑃 und 𝒢_𝑃 gibt, sodass 𝑃 äquivalent zu #Hom(ℋ_𝑃 → 𝒢_𝑃 ) ist.