Token shifting on graphs. Issue 4 (2nd October 2022)

• Record Type: Journal Article
• Authors: Myint, Win Hlaing Hlaing; Uehara, Ryuhei; Viglietta, Giovanni
• Is Part Of: International journal of computer mathematics. Volume 7:Issue 4(2022)
• Page Start: 223
• Page End: 234
• Publication Date: 2022-10-02
• Subjects: Reconfiguration problem -- cyclic shift -- barbell graph -- block graph -- NP-hard; 05A05 Permutations -- words -- matrices -- 05C57 Games on graphs(graph-theoretic aspects); Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2022.2118622
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: We investigate a new variation of a token reconfiguration problem on graphs using the cyclic shift operation. A coloured or labelled token is placed on each vertex of a given graph, and a 'move' consists in choosing a cycle in the graph and shifting tokens by one position along its edges. Given a target arrangement of tokens on the graph, our goal is to find a shortest sequence of moves that will re-arrange the tokens as in the target arrangement. The novelty of our model is that tokens are allowed to shift along any cycle in the graph, as opposed to a given subset of its cycles. We first discuss the problem on special graph classes: we give efficient algorithms for optimally solving the 2-Coloured Token Shifting Problem on complete graphs and block graphs, as well as the Labelled Token Shifting Problem on complete graphs and variants of barbell graphs. We then show that, in the 2-Coloured Token Shifting Problem, the shortest sequence of moves is NP-hard to approximate within a factor of 1 / 2 + ε, even for grid graphs. The latter result settles an open problem posed by Sai et al.