--- res: bibo_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.@eng' bibo_authorlist: - foaf_Person: foaf_givenName: Krishnendu foaf_name: Chatterjee, Krishnendu foaf_surname: Chatterjee foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-4561-241X - foaf_Person: foaf_givenName: Georg F foaf_name: Osang, Georg F foaf_surname: Osang foaf_workInfoHomepage: http://www.librecat.org/personId=464B40D6-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-8882-5116 bibo_doi: 10.1016/j.ipl.2017.02.003 bibo_volume: 122 dct_date: 2017^xs_gYear dct_identifier: - UT:000399506600005 dct_isPartOf: - http://id.crossref.org/issn/00200190 dct_language: eng dct_publisher: Elsevier@ dct_title: Pushdown reachability with constant treewidth@ ...