---
_id: '14344'
abstract:
- lang: eng
  text: We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in
    two different settings. In the first one, G is given to us in the form of randomly
    ordered adjacency lists while in the second one, we are given the adjacency matrix
    of G. In each of the two settings we derive a deterministic algorithm that w.h.p.
    either finds a Hamilton cycle or returns a certificate that such a cycle does
    not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and  respectively,
    each being best possible in its own setting.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
citation:
  ama: 'Anastos M. Fast algorithms for solving the Hamilton cycle problem with high
    probability. In: <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>.
    Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:<a
    href="https://doi.org/10.1137/1.9781611977554.ch88">10.1137/1.9781611977554.ch88</a>'
  apa: 'Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem
    with high probability. In <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete
    Algorithms</i> (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial
    and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611977554.ch88">https://doi.org/10.1137/1.9781611977554.ch88</a>'
  chicago: Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem
    with High Probability.” In <i>Proceedings of the Annual ACM-SIAM Symposium on
    Discrete Algorithms</i>, 2023:2286–2323. Society for Industrial and Applied Mathematics,
    2023. <a href="https://doi.org/10.1137/1.9781611977554.ch88">https://doi.org/10.1137/1.9781611977554.ch88</a>.
  ieee: M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high
    probability,” in <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms</i>,
    Florence, Italy, 2023, vol. 2023, pp. 2286–2323.
  ista: 'Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with
    high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
    SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323.'
  mla: Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with
    High Probability.” <i>Proceedings of the Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>, vol. 2023, Society for Industrial and Applied Mathematics, 2023,
    pp. 2286–323, doi:<a href="https://doi.org/10.1137/1.9781611977554.ch88">10.1137/1.9781611977554.ch88</a>.
  short: M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete
    Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.
conference:
  end_date: 2023-01-25
  location: Florence, Italy
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2023-01-22
date_created: 2023-09-17T22:01:10Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-09-25T09:13:41Z
day: '01'
department:
- _id: MaKw
doi: 10.1137/1.9781611977554.ch88
external_id:
  arxiv:
  - '2111.14759'
intvolume: '      2023'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2111.14759
month: '01'
oa: 1
oa_version: Preprint
page: 2286-2323
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '9781611977554'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast algorithms for solving the Hamilton cycle problem with high probability
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...
---
_id: '12676'
abstract:
- lang: eng
  text: Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum
    games played on directed graphs with probabilistic transitions. The goal of player-max
    is to maximize the probability to reach a target state against the adversarial
    player-min. These games lie in NP ∩ coNP and are among the rare combinatorial
    problems that belong to this complexity class for which the existence of polynomial-time
    algorithm is a major open question. While randomized sub-exponential time algorithm
    exists, all known deterministic algorithms require exponential time in the worst-case.
    An important open question has been whether faster algorithms can be obtained
    parametrized by the treewidth of the game graph. Even deterministic sub-exponential
    time algorithm for constant treewidth turn-based stochastic games has remain elusive.
    In this work our main result is a deterministic algorithm to solve turn-based
    stochastic games that, given a game with n states, treewidth at most t, and the
    bit-complexity of the probabilistic transition function log D, has running time
    O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time
    for games with constant or poly-logarithmic treewidth.
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
  grant.
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: Tobias
  full_name: Meggendorfer, Tobias
  id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
  last_name: Meggendorfer
  orcid: 0000-0002-1712-2165
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  ama: 'Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm
    for turn-based stochastic games with bounded treewidth. In: <i>Proceedings of
    the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial
    and Applied Mathematics; 2023:4590-4605. doi:<a href="https://doi.org/10.1137/1.9781611977554.ch173">10.1137/1.9781611977554.ch173</a>'
  apa: 'Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., &#38; Svoboda, J.
    (2023). Faster algorithm for turn-based stochastic games with bounded treewidth.
    In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>
    (pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics.
    <a href="https://doi.org/10.1137/1.9781611977554.ch173">https://doi.org/10.1137/1.9781611977554.ch173</a>'
  chicago: Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta,
    and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded
    Treewidth.” In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete
    Algorithms</i>, 4590–4605. Society for Industrial and Applied Mathematics, 2023.
    <a href="https://doi.org/10.1137/1.9781611977554.ch173">https://doi.org/10.1137/1.9781611977554.ch173</a>.
  ieee: K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster
    algorithm for turn-based stochastic games with bounded treewidth,” in <i>Proceedings
    of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy,
    2023, pp. 4590–4605.
  ista: 'Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster
    algorithm for turn-based stochastic games with bounded treewidth. Proceedings
    of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
    on Discrete Algorithms, 4590–4605.'
  mla: Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic
    Games with Bounded Treewidth.” <i>Proceedings of the 2023 Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2023,
    pp. 4590–605, doi:<a href="https://doi.org/10.1137/1.9781611977554.ch173">10.1137/1.9781611977554.ch173</a>.
  short: K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings
    of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
    and Applied Mathematics, 2023, pp. 4590–4605.
conference:
  end_date: 2023-01-25
  location: Florence, Italy
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2023-01-22
date_created: 2023-02-24T12:20:47Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2025-07-14T09:09:50Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1137/1.9781611977554.ch173
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1137/1.9781611977554.ch173
month: '02'
oa: 1
oa_version: Published Version
page: 4590-4605
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  isbn:
  - '9781611977554'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
status: public
title: Faster algorithm for turn-based stochastic games with bounded treewidth
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...