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 PSPACE-complete, although some are solvable in LogSPACE. We also consider these reconfiguration questions through the lense of parameterized algorithms and prove various FPT-results, in particular concerning the combined parameter \(k+\ell \) or neighborhood diversity together with k or neighborhood diversity together with \(\ell \) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

How to Reconfigure Your Alliances

  • Henning Fernau,
  • Kevin Mann

摘要

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 PSPACE-complete, although some are solvable in LogSPACE. We also consider these reconfiguration questions through the lense of parameterized algorithms and prove various FPT-results, in particular concerning the combined parameter \(k+\ell \) or neighborhood diversity together with k or neighborhood diversity together with \(\ell \) .