Graphs can be succinctly indexed for pattern matching in $O(|E{|}^2+|V{|}^{5/2})$ time

Abstract

For the first time we provide a succinct pattern matching index for arbitrary graphs that can be built in polynomial time, which requires less space and answers queries more efficiently than the one in [SODA 2021]. We show that, given an edge-labeled graph $G=(V,E)$, there exists a data structures of $|E{/}_{{\le }_G}|(\lceil \log |\Sigma |\rceil +\lceil \log q\rceil +2)\cdot (1+o(1))+|V{/}_{{\le }_G}|\cdot (1+o(1))$ bits which can be built in $O(|E{|}^2+|V{/}_{{\le }_G}{|}^{5/2})$ time and supports pattern matching on $G$ in $O(|P|\cdot q^2\cdot \log (q\cdot |\Sigma |))$ time, where $G{/}_{{\le }_G}=(V{/}_{{\le }_G},E{/}_{{\le }_G})$ is a quotient graph obtained by collapsing some nodes in $G$ (so $|V{/}_{{\le }_G}|\le |V|$ and $|E{/}_{{\le }_G}|\le |E|$) and $q$ is the width of the maximum co-lex relation on $G$. Our results have relevant applications in automata theory. First, we can build a succinct data structure to decide whether a string is accepted by a given automaton. Second, starting from an automaton $\mathcal{A}$, one can define a relation ${⪯}_{\mathcal{A}}$ and a quotient automaton that capture the nondeterminism of $\mathcal{A}$, improving the results in [SODA 2021].