Graph Generators: State of the Art and Open Challenges - Archive ouverte HAL Access content directly
Journal Articles ACM Computing Surveys Year : 2020

Graph Generators: State of the Art and Open Challenges

(1, 2) , (3) , (4) , (5)
1
2
3
4
5

Abstract

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.

Keywords

Fichier principal
Vignette du fichier
2001.07906 (3).pdf (321.52 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02435371 , version 1 (25-09-2020)

Identifiers

Cite

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⟩
163 View
479 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More