---
_id: '9293'
abstract:
- lang: eng
  text: 'We consider planning problems for graphs, Markov Decision Processes (MDPs),
    and games on graphs in an explicit state space. While graphs represent the most
    basic planning model, MDPs represent interaction with nature and games on graphs
    represent interaction with an adversarial environment. We consider two planning
    problems with k different target sets: (a) the coverage problem asks whether there
    is a plan for each individual target set; and (b) the sequential target reachability
    problem asks whether the targets can be reached in a given sequence. For the coverage
    problem, we present a linear-time algorithm for graphs, and quadratic conditional
    lower bound for MDPs and games on graphs. For the sequential target problem, we
    present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs,
    and a quadratic conditional lower bound for games on graphs. Our results with
    conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture
    and strong exponential time hypothesis (SETH), establish (i) model-separation
    results showing that for the coverage problem MDPs and games on graphs are harder
    than graphs, and for the sequential reachability problem games on graphs are harder
    than MDPs and graphs; and (ii) problem-separation results showing that for MDPs
    the coverage problem is harder than the sequential target problem.'
article_number: '103499'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Alexander
  full_name: Svozil, Alexander
  last_name: Svozil
citation:
  ama: Chatterjee K, Dvořák W, Henzinger MH, Svozil A. Algorithms and conditional
    lower bounds for planning problems. <i>Artificial Intelligence</i>. 2021;297(8).
    doi:<a href="https://doi.org/10.1016/j.artint.2021.103499">10.1016/j.artint.2021.103499</a>
  apa: Chatterjee, K., Dvořák, W., Henzinger, M. H., &#38; Svozil, A. (2021). Algorithms
    and conditional lower bounds for planning problems. <i>Artificial Intelligence</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.artint.2021.103499">https://doi.org/10.1016/j.artint.2021.103499</a>
  chicago: Chatterjee, Krishnendu, Wolfgang Dvořák, Monika H Henzinger, and Alexander
    Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” <i>Artificial
    Intelligence</i>. Elsevier, 2021. <a href="https://doi.org/10.1016/j.artint.2021.103499">https://doi.org/10.1016/j.artint.2021.103499</a>.
  ieee: K. Chatterjee, W. Dvořák, M. H. Henzinger, and A. Svozil, “Algorithms and
    conditional lower bounds for planning problems,” <i>Artificial Intelligence</i>,
    vol. 297, no. 8. Elsevier, 2021.
  ista: Chatterjee K, Dvořák W, Henzinger MH, Svozil A. 2021. Algorithms and conditional
    lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
  mla: Chatterjee, Krishnendu, et al. “Algorithms and Conditional Lower Bounds for
    Planning Problems.” <i>Artificial Intelligence</i>, vol. 297, no. 8, 103499, Elsevier,
    2021, doi:<a href="https://doi.org/10.1016/j.artint.2021.103499">10.1016/j.artint.2021.103499</a>.
  short: K. Chatterjee, W. Dvořák, M.H. Henzinger, A. Svozil, Artificial Intelligence
    297 (2021).
date_created: 2021-03-28T22:01:40Z
date_published: 2021-03-16T00:00:00Z
date_updated: 2023-09-26T10:41:42Z
day: '16'
department:
- _id: KrCh
doi: 10.1016/j.artint.2021.103499
external_id:
  arxiv:
  - '1804.07031'
  isi:
  - '000657537500003'
intvolume: '       297'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.07031
month: '03'
oa: 1
oa_version: Preprint
publication: Artificial Intelligence
publication_identifier:
  issn:
  - 0004-3702
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '35'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Algorithms and conditional lower bounds for planning problems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 297
year: '2021'
...