Campus Event Calendar

Event Entry

What and Who

Counting Patterns in Strings and Graphs

Philip Wellnitz
Max-Planck-Institut fรผr Informatik - D1
AG 1, INET, AG 5, RG1, SWS, AG 2, AG 4, D6, AG 3  
MPI Audience

Date, Time and Location

Thursday, 2 December 2021
60 Minutes
Virtual talk
Virtual talk


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(โ„‹_๐‘ƒ โ†’ ๐’ข_๐‘ƒ).


Philip Wellnitz
+49 681 9325 1124
--email hidden

Virtual Meeting Details

987 0294 1574
passcode not visible
logged in users only

Philip Wellnitz, 11/29/2021 13:22 -- Created document.