Graph Generators: State of the Art and Open Challenges

Angela Bonifati (1, 2) , Irena Holubovà (3) , Arnau Prat-Pérez (4) , Sherif Sakr (5)

1 BD - Base de Données
2 TYREX - Types and Reasoning for the Web
3 Faculty of Mathematics and Physics [Praha/Prague]
4 UPC - Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]
5 Institute of Computer Science [University of Tartu, Estonie]

We focus on the computational complexity of regular simple path queries (RSPQs). We consider the following problem RSPQ(L) for a regular language L: given an edge-labeled digraph Gand two nodes xand y, is there a simple path from x to y that forms a word belonging to L? We fully characterize the frontier between tractability and intractability for RSPQ(L). More precisely, we prove RSPQ(L)is either AC0, NL-complete or NP-complete depending on the language L. We also provide a simple characterization of the tractable fragment in terms of regular expressions. Finally, we also discuss the complexity of deciding whether a language L belongs to the fragment above. We consider several alternative representations of L: DFAs, NFAs or regular expressions, and prove that this problem is NL-complete for the first representation and PSpace-complete for the other two.

Mots clés: Graph Generators; Graphs

Domaines: Web

Angela Bonifati, Irena Holubovà, Arnau Prat-Pérez, Sherif Sakr. Graph Generators: State of the Art and Open Challenges. ACM Computing Surveys, 2020, 53 (2), ⟨10.1145/3379445⟩. ⟨hal-02435371⟩