---
_id: '12102'
abstract:
- lang: eng
  text: 'Given a Markov chain M = (V, v_0, δ), with state space V and a starting state
    v_0, and a probability threshold ε, an ε-core is a subset C of states that is
    left with probability at most ε. More formally, C ⊆ V is an ε-core, iff ℙ[reach
    (V\C)] ≤ ε. Cores have been applied in a wide variety of verification problems
    over Markov chains, Markov decision processes, and probabilistic programs, as
    a means of discarding uninteresting and low-probability parts of a probabilistic
    system and instead being able to focus on the states that are likely to be encountered
    in a real-world run. In this work, we focus on the problem of computing a minimal
    ε-core in a Markov chain. Our contributions include both negative and positive
    results: (i) We show that the decision problem on the existence of an ε-core of
    a given size is NP-complete. This solves an open problem posed in [Jan Kretínský
    and Tobias Meggendorfer, 2020]. We additionally show that the problem remains
    NP-complete even when limited to acyclic Markov chains with bounded maximal vertex
    degree; (ii) We provide a polynomial time algorithm for computing a minimal ε-core
    on Markov chains over control-flow graphs of structured programs. A straightforward
    combination of our algorithm with standard branch prediction techniques allows
    one to apply the idea of cores to find a subset of program lines that are left
    with low probability and then focus any desired static analysis on this core subset.'
acknowledgement: "The research was partially supported by the Hong Kong Research Grants
  Council ECS\r\nProject No. 26208122, ERC CoG 863818 (FoRM-SMArt), the European Union’s
  Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie
  Grant Agreement No. 665385, HKUST– Kaisa Joint Research Institute Project Grant
  HKJRI3A-055 and HKUST Startup Grant R9272. Ali Ahmadi and Roodabeh Safavi were interns
  at HKUST."
article_number: '29'
article_processing_charge: No
author:
- first_name: Ali
  full_name: Ahmadi, Ali
  last_name: Ahmadi
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Amir Kafshdar
  full_name: Goharshady, Amir Kafshdar
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
- first_name: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Roodabeh
  full_name: Safavi Hemami, Roodabeh
  id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
  last_name: Safavi Hemami
- first_name: Dorde
  full_name: Zikelic, Dorde
  id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
  last_name: Zikelic
  orcid: 0000-0002-4681-1699
citation:
  ama: 'Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic
    D. Algorithms and hardness results for computing cores of Markov chains. In: <i>42nd
    IARCS Annual Conference on Foundations of Software Technology and Theoretical
    Computer Science</i>. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2022. doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">10.4230/LIPIcs.FSTTCS.2022.29</a>'
  apa: 'Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami,
    R., &#38; Zikelic, D. (2022). Algorithms and hardness results for computing cores
    of Markov chains. In <i>42nd IARCS Annual Conference on Foundations of Software
    Technology and Theoretical Computer Science</i> (Vol. 250). Madras, India: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>'
  chicago: Ahmadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer,
    Roodabeh Safavi Hemami, and Dorde Zikelic. “Algorithms and Hardness Results for
    Computing Cores of Markov Chains.” In <i>42nd IARCS Annual Conference on Foundations
    of Software Technology and Theoretical Computer Science</i>, Vol. 250. Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>.
  ieee: A. Ahmadi, K. Chatterjee, A. K. Goharshady, T. Meggendorfer, R. Safavi Hemami,
    and D. Zikelic, “Algorithms and hardness results for computing cores of Markov
    chains,” in <i>42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.
  ista: 'Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic
    D. 2022. Algorithms and hardness results for computing cores of Markov chains.
    42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical
    Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer
    Science vol. 250, 29.'
  mla: Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of
    Markov Chains.” <i>42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science</i>, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2022, doi:<a href="https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29">10.4230/LIPIcs.FSTTCS.2022.29</a>.
  short: A. Ahmadi, K. Chatterjee, A.K. Goharshady, T. Meggendorfer, R. Safavi Hemami,
    D. Zikelic, in:, 42nd IARCS Annual Conference on Foundations of Software Technology
    and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2022.
conference:
  end_date: 2022-12-20
  location: Madras, India
  name: 'FSTTC: Foundations of Software Technology and Theoretical Computer Science'
  start_date: 2022-12-18
date_created: 2023-01-01T23:00:50Z
date_published: 2022-12-14T00:00:00Z
date_updated: 2025-07-14T09:09:55Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
doi: 10.4230/LIPIcs.FSTTCS.2022.29
ec_funded: 1
file:
- access_level: open_access
  checksum: 6660c802489013f034c9e8bd57f4d46e
  content_type: application/pdf
  creator: dernst
  date_created: 2023-01-20T10:39:44Z
  date_updated: 2023-01-20T10:39:44Z
  file_id: '12324'
  file_name: 2022_LIPICs_Ahmadi.pdf
  file_size: 872534
  relation: main_file
  success: 1
file_date_updated: 2023-01-20T10:39:44Z
has_accepted_license: '1'
intvolume: '       250'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '665385'
  name: International IST Doctoral Program
publication: 42nd IARCS Annual Conference on Foundations of Software Technology and
  Theoretical Computer Science
publication_identifier:
  isbn:
  - '9783959772617'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithms and hardness results for computing cores of Markov chains
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 250
year: '2022'
...