---
OA_place: repository
OA_type: green
_id: '19445'
abstract:
- lang: eng
  text: "In reconfiguration, we are given two solutions to a graph problem, such as
    Vertex Cover or Dominating Set, with each solution represented by a placement
    of tokens on vertices of the graph. Our task is to reconfigure one into the other
    using small steps while ensuring the intermediate configurations of tokens are
    also valid solutions. The two commonly studied settings are Token Jumping and
    Token Sliding, which allows moving a single token to an arbitrary or an adjacent
    vertex, respectively.\r\n\r\nWe introduce new rules that generalize Token Jumping,
    parameterized by the number of tokens allowed to move at once and by the maximum
    distance of each move. Our main contribution is identifying minimal rules that
    allow reconfiguring any possible given solution into any other for Independent
    Set, Vertex Cover, and Dominating Set. For each minimal rule, we also provide
    an efficient algorithm that finds a corresponding reconfiguration sequence.\r\n\r\nWe
    further focus on the rule that allows each token to move to an adjacent vertex
    in a single step. This natural variant turns out to be the minimal rule that guarantees
    reconfigurability for Vertex Cover. We determine the computational complexity
    of deciding whether a (shortest) reconfiguration sequence exists under this rule
    for the three studied problems. While reachability for Vertex Cover is shown to
    be in P, finding a shortest sequence is shown to be NP-complete. For Independent
    Set and Dominating Set, even reachability is shown to be PSPACE-complete."
acknowledgement: J. M. Křišťan acknowledges the support of the Czech Science Foundation
  Grant No. 24-12046S. This work was supported by the Grant Agency of the Czech Technical
  University in Prague, grant No. SGS23/205/OHK3/3T/18. J. Svoboda acknowledges the
  support of the ERC CoG 863818 (ForM-SMArt) grant.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan Matyáš
  full_name: Křišťan, Jan Matyáš
  last_name: Křišťan
- first_name: Jakub
  full_name: Svoboda, Jakub
  id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
  last_name: Svoboda
  orcid: 0000-0002-1419-3267
citation:
  ama: 'Křišťan JM, Svoboda J. Reconfiguration using generalized token jumping. In:
    <i>19th International Conference and Workshops on Algorithms and Computation</i>.
    Vol 15411. Springer Nature; 2025:244-265. doi:<a href="https://doi.org/10.1007/978-981-96-2845-2_16">10.1007/978-981-96-2845-2_16</a>'
  apa: 'Křišťan, J. M., &#38; Svoboda, J. (2025). Reconfiguration using generalized
    token jumping. In <i>19th International Conference and Workshops on Algorithms
    and Computation</i> (Vol. 15411, pp. 244–265). Chengdu, China: Springer Nature.
    <a href="https://doi.org/10.1007/978-981-96-2845-2_16">https://doi.org/10.1007/978-981-96-2845-2_16</a>'
  chicago: Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized
    Token Jumping.” In <i>19th International Conference and Workshops on Algorithms
    and Computation</i>, 15411:244–65. Springer Nature, 2025. <a href="https://doi.org/10.1007/978-981-96-2845-2_16">https://doi.org/10.1007/978-981-96-2845-2_16</a>.
  ieee: J. M. Křišťan and J. Svoboda, “Reconfiguration using generalized token jumping,”
    in <i>19th International Conference and Workshops on Algorithms and Computation</i>,
    Chengdu, China, 2025, vol. 15411, pp. 244–265.
  ista: 'Křišťan JM, Svoboda J. 2025. Reconfiguration using generalized token jumping.
    19th International Conference and Workshops on Algorithms and Computation. WALCOM:
    International Conference and Workshops on Algorithms and Computation, LNCS, vol.
    15411, 244–265.'
  mla: Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized
    Token Jumping.” <i>19th International Conference and Workshops on Algorithms and
    Computation</i>, vol. 15411, Springer Nature, 2025, pp. 244–65, doi:<a href="https://doi.org/10.1007/978-981-96-2845-2_16">10.1007/978-981-96-2845-2_16</a>.
  short: J.M. Křišťan, J. Svoboda, in:, 19th International Conference and Workshops
    on Algorithms and Computation, Springer Nature, 2025, pp. 244–265.
conference:
  end_date: 2025-03-02
  location: Chengdu, China
  name: 'WALCOM: International Conference and Workshops on Algorithms and Computation'
  start_date: 2025-02-28
date_created: 2025-03-23T23:01:27Z
date_published: 2025-02-20T00:00:00Z
date_updated: 2025-09-30T11:14:33Z
day: '20'
department:
- _id: KrCh
doi: 10.1007/978-981-96-2845-2_16
ec_funded: 1
external_id:
  arxiv:
  - '2411.12582'
  isi:
  - '001537885900016'
intvolume: '     15411'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2411.12582
month: '02'
oa: 1
oa_version: Preprint
page: 244-265
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 19th International Conference and Workshops on Algorithms and Computation
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9789819628445'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reconfiguration using generalized token jumping
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15411
year: '2025'
...