Pushdown reachability with constant treewidth
Download
Journal Article
| Published
| English
Scopus indexed
Department
Grant
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.
Publishing Year
Date Published
2017-06-01
Journal Title
Information Processing Letters
Publisher
Elsevier
Volume
122
Page
25 - 29
ISSN
IST-REx-ID
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
Open Access
Date Uploaded
2018-12-12
Export
Marked PublicationsOpen Data ISTA Research Explorer
Google Scholar