10.1016/j.ipl.2017.02.003
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Osang, Georg F
Georg F
Osang
Pushdown reachability with constant treewidth
Elsevier
2017
2018-12-11T11:49:57Z
2020-01-21T13:16:32Z
journal_article
/record/1065
/record/1065.json
00200190
247657 bytes
application/pdf
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.