Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.08798 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914031496855552 |
|---|---|
| author | Fernau, Henning Mann, Kevin |
| author_facet | Fernau, Henning Mann, Kevin |
| contents | Different variations of alliances in graphs have been introduced into the graph-theoretic literature about twenty years ago. More broadly speaking, they can be interpreted as groups that collaborate to achieve a common goal, for instance, defending themselves against possible attacks from outside. In this paper, we initiate the study of reconfiguring alliances. This means that, with the understanding of having an interconnection map given by a graph, we look at two alliances of the same size~$k$ and investigate if there is a reconfiguration sequence (of length at most~$\ell$) formed by alliances of size (at most)~$k$ that transfers one alliance into the other one. Here, we consider different (now classical) movements of tokens: sliding, jumping, addition/removal. We link the latter two regimes by introducing the concept of reconfiguration monotonicity. Concerning classical complexity, most of these reconfiguration problems are \textsf{PSPACE}-complete, although some are solvable in \textsf{Log\-SPACE}. We also consider these reconfiguration questions through the lense of parameterized algorithms and prove various \textsf{FPT}-results, in particular concerning the combined parameter $k+\ell$ or neighborhood diversity together with $k$ or neighborhood diversity together with $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08798 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How to Reconfigure Your Alliances Fernau, Henning Mann, Kevin Computational Complexity Discrete Mathematics Different variations of alliances in graphs have been introduced into the graph-theoretic literature about twenty years ago. More broadly speaking, they can be interpreted as groups that collaborate to achieve a common goal, for instance, defending themselves against possible attacks from outside. In this paper, we initiate the study of reconfiguring alliances. This means that, with the understanding of having an interconnection map given by a graph, we look at two alliances of the same size~$k$ and investigate if there is a reconfiguration sequence (of length at most~$\ell$) formed by alliances of size (at most)~$k$ that transfers one alliance into the other one. Here, we consider different (now classical) movements of tokens: sliding, jumping, addition/removal. We link the latter two regimes by introducing the concept of reconfiguration monotonicity. Concerning classical complexity, most of these reconfiguration problems are \textsf{PSPACE}-complete, although some are solvable in \textsf{Log\-SPACE}. We also consider these reconfiguration questions through the lense of parameterized algorithms and prove various \textsf{FPT}-results, in particular concerning the combined parameter $k+\ell$ or neighborhood diversity together with $k$ or neighborhood diversity together with $k$. |
| title | How to Reconfigure Your Alliances |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2509.08798 |