Dominating sets reconfiguration under token sliding - GREYC amacc Access content directly
Preprints, Working Papers, ... Year : 2021

Dominating sets reconfiguration under token sliding

Abstract

Let $G$ be a graph and $D_{\sf s}$ and $D_{\sf t}$ be two dominating sets of $G$ of size $k$. Does there exist a sequence $\langle D_0 = D_{\sf s}, D_1, \ldots, D_{\ell-1}, D_\ell = D_{\sf t} \rangle$ of dominating sets of $G$ such that $D_{i+1}$ can be obtained from $D_i$ by replacing one vertex with one of its neighbors? In this paper, we investigate the complexity of this decision problem. We first prove that this problem is PSPACE-complete, even when restricted to split, bipartite or bounded treewidth graphs. On the other hand, we prove that it can be solved in polynomial time on dually chordal graphs (a superclass of both trees and interval graphs) or cographs.
Fichier principal
Vignette du fichier
main.pdf (493.84 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02394839 , version 1 (06-12-2019)
hal-02394839 , version 2 (19-05-2021)

Identifiers

Cite

Marthe Bonamy, Paul Dorbec, Paul Ouvrard. Dominating sets reconfiguration under token sliding. 2021. ⟨hal-02394839v2⟩
170 View
280 Download

Altmetric

Share

Gmail Facebook X LinkedIn More