Graphs can be succinctly indexed for pattern matching in $O(\vert E\vert ^{2}+\vert V\vert ^{5/2})$ time
Nicola Cotumaccio · 2022
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$G=(V, E)$, there exists a data structure of$\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))$bits which supports pattern matching on$G$in$O(\vert P\vert \cdot q^{2}\cdot\log(q\cdot\vert \Sigma\vert))$time, where$G/_{\leq G}=(V/_{\leq G}, E/_{\leq G})$is a quotient graph obtained by collapsing some nodes in$G$and$q$is the width of the maximum co-lex relation on$G$. 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.