Abstract:Given a static vertex-selection problem (e.g. independent set, dominating set) on a graph, we can define a corresponding temporally satisfying reconfiguration problem on a temporal graph which asks for a sequence of solutions to the vertex-selection problem at each time such that we can reconfigure from one solution to the next. We can think of each solution in the sequence as a set of vertices with tokens placed on them; our reconfiguration model allows us to slide tokens along active edges of a temporal graph at each time-step.
We show that it is possible to efficiently check whether one solution can be reconfigured to another, and show that approximation results on the static vertex-selection problem can be adapted with a lifetime factor to the reconfiguration version. Our main contributions are fixed-parameter tractable algorithms with respect to: enumeration time of the related static problem; the combination of temporal neighbourhood diversity and lifetime of the input temporal graph; and the combination of lifetime and treewidth of the footprint graph.
From: Laura Larios-Jones [view email]
[v1]
Mon, 17 Feb 2025 16:09:00 UTC (60 KB)
[v2]
Tue, 16 Sep 2025 13:14:55 UTC (59 KB)
[v3]
Fri, 19 Sep 2025 14:28:38 UTC (52 KB)
[v4]
Tue, 8 Sep 2026 10:01:27 UTC (51 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。