Kernelization Complexity of Solution Discovery Problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916411112161280 |
|---|---|
| author | Grobler, Mario Maaz, Stephanie Mouawad, Amer E. Nishimura, Naomi Ramamoorthi, Vijayaragunathan Siebertz, Sebastian |
| author_facet | Grobler, Mario Maaz, Stephanie Mouawad, Amer E. Nishimura, Naomi Ramamoorthi, Vijayaragunathan Siebertz, Sebastian |
| contents | In the solution discovery variant of a vertex (edge) subset problem $Π$ on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph $G$ together with a budget $b$. The question is whether we can transform this configuration into a feasible solution of $Π$ on $G$ with at most $b$ modification steps. We consider the token sliding variant of the solution discovery framework, where each modification step consists of sliding a token to an adjacent vertex (edge). The framework of solution discovery was recently introduced by Fellows et al. [Fellows et al., ECAI 2023] and for many solution discovery problems the classical as well as the parameterized complexity has been established. In this work, we study the kernelization complexity of the solution discovery variants of Vertex Cover, Independent Set, Dominating Set, Shortest Path, Matching, and Vertex Cut with respect to the parameters number of tokens $k$, discovery budget $b$, as well as structural parameters such as pathwidth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_17250 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Kernelization Complexity of Solution Discovery Problems Grobler, Mario Maaz, Stephanie Mouawad, Amer E. Nishimura, Naomi Ramamoorthi, Vijayaragunathan Siebertz, Sebastian Data Structures and Algorithms Computational Complexity Combinatorics In the solution discovery variant of a vertex (edge) subset problem $Π$ on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph $G$ together with a budget $b$. The question is whether we can transform this configuration into a feasible solution of $Π$ on $G$ with at most $b$ modification steps. We consider the token sliding variant of the solution discovery framework, where each modification step consists of sliding a token to an adjacent vertex (edge). The framework of solution discovery was recently introduced by Fellows et al. [Fellows et al., ECAI 2023] and for many solution discovery problems the classical as well as the parameterized complexity has been established. In this work, we study the kernelization complexity of the solution discovery variants of Vertex Cover, Independent Set, Dominating Set, Shortest Path, Matching, and Vertex Cut with respect to the parameters number of tokens $k$, discovery budget $b$, as well as structural parameters such as pathwidth. |
| title | Kernelization Complexity of Solution Discovery Problems |
| topic | Data Structures and Algorithms Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2409.17250 |