Graphs can be succinctly indexed for pattern matching in $O(\vert E\vert ^{2}+\vert V\vert ^{5/2})$ time
Nicola Cotumaccio
Abstract
For the first time we provide a succinct pattern matching index for arbitrary graphs that can be built in polynomial time, while improving both space and query time bounds from [SODA 2021]. We show that, given an edge-labeled graph <tex>$G=(V, E)$</tex>, there exists a data structure of <tex>$\vert E/_{\leq G}\vert (\lceil\log\vert \Sigma\vert \rceil+\lceil\log q\rceil+2)\cdot(1+o(1))+\vert V/_{\leq G}\vert \cdot(1+o(1))$</tex> bits which supports pattern matching on <tex>$G$</tex> in <tex>$O(\vert P\vert \cdot q^{2}\cdot\log(q\cdot\vert \Sigma\vert))$</tex> time, where <tex>$G/_{\leq G}=(V/_{\leq G}, E/_{\leq G})$</tex> is a quotient graph obtained by collapsing some nodes in <tex>$G$</tex> and <tex>$q$</tex> is the width of the maximum co-lex relation on <tex>$G$</tex>. Our results have relevant applications in automata theory: we can use our data structure to decide whether a string belongs to the language recognized by a given automaton, and we can capture the degree of nondeterminism of an NFA.