Pushdown reachability with constant treewidth Journal Article


Author(s): Chatterjee, Krishnendu; Osang, Georg
Article Title: Pushdown reachability with constant treewidth
Affiliation IST Austria
Abstract: We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs.
Keywords: Algorithms; reachability; Graph algorithms; Constant tree-width graphs; Pushdown systems
Journal Title: Information Processing Letters
Volume: 122
ISSN: 0020-0190
Publisher: Elsevier  
Date Published: 2017-02-22
Start Page: 25
End Page: 29
Sponsor: The research was partially supported by the Austrian Science Fund (FWF): P23499-N23, S11407-N23 (RiSE/SHiNE), and an ERC Start Grant (279307: Graph Games).
DOI: 10.1016/j.ipl.2017.02.003
Open access: no