---
_id: '1065'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Georg F
  full_name: Osang, Georg F
  id: 464B40D6-F248-11E8-B48F-1D18A9856A87
  last_name: Osang
  orcid: 0000-0002-8882-5116
citation:
  ama: Chatterjee K, Osang GF. Pushdown reachability with constant treewidth. <i>Information
    Processing Letters</i>. 2017;122:25-29. doi:<a href="https://doi.org/10.1016/j.ipl.2017.02.003">10.1016/j.ipl.2017.02.003</a>
  apa: Chatterjee, K., &#38; Osang, G. F. (2017). Pushdown reachability with constant
    treewidth. <i>Information Processing Letters</i>. Elsevier. <a href="https://doi.org/10.1016/j.ipl.2017.02.003">https://doi.org/10.1016/j.ipl.2017.02.003</a>
  chicago: Chatterjee, Krishnendu, and Georg F Osang. “Pushdown Reachability with
    Constant Treewidth.” <i>Information Processing Letters</i>. Elsevier, 2017. <a
    href="https://doi.org/10.1016/j.ipl.2017.02.003">https://doi.org/10.1016/j.ipl.2017.02.003</a>.
  ieee: K. Chatterjee and G. F. Osang, “Pushdown reachability with constant treewidth,”
    <i>Information Processing Letters</i>, vol. 122. Elsevier, pp. 25–29, 2017.
  ista: Chatterjee K, Osang GF. 2017. Pushdown reachability with constant treewidth.
    Information Processing Letters. 122, 25–29.
  mla: Chatterjee, Krishnendu, and Georg F. Osang. “Pushdown Reachability with Constant
    Treewidth.” <i>Information Processing Letters</i>, vol. 122, Elsevier, 2017, pp.
    25–29, doi:<a href="https://doi.org/10.1016/j.ipl.2017.02.003">10.1016/j.ipl.2017.02.003</a>.
  short: K. Chatterjee, G.F. Osang, Information Processing Letters 122 (2017) 25–29.
date_created: 2018-12-11T11:49:57Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-09-20T12:08:18Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: HeEd
doi: 10.1016/j.ipl.2017.02.003
ec_funded: 1
external_id:
  isi:
  - '000399506600005'
file:
- access_level: open_access
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:13:17Z
  date_updated: 2019-10-15T07:44:51Z
  file_id: '4998'
  file_name: IST-2018-991-v1+2_2018_Chatterjee_Pushdown_PREPRINT.pdf
  file_size: 247657
  relation: main_file
file_date_updated: 2019-10-15T07:44:51Z
has_accepted_license: '1'
intvolume: '       122'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 25 - 29
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: Information Processing Letters
publication_identifier:
  issn:
  - '00200190'
publication_status: published
publisher: Elsevier
publist_id: '6323'
pubrep_id: '991'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Pushdown reachability with constant treewidth
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 122
year: '2017'
...