Dominating sets reconfiguration under token sliding

12/06/2019
by   Marthe Bonamy, et al.
0

Let G be a graph and D_s and D_t be two dominating sets of G of size k. Does there exist a sequence 〈 D_0 = D_s, D_1, ..., D_ℓ-1, D_ℓ = D_t〉 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 tree-width 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset