IEICE Technical Committee Submission System
Conference Paper's Information
Online Proceedings
[Sign in]
Tech. Rep. Archives
 Go Top Page Go Previous   [Japanese] / [English] 

Paper Abstract and Keywords
Presentation 2021-12-03 11:10
Token Sliding on Directed Graphs
Takehiro Ito (Tohoku Univ), Yuni Iwamasa, Yasuaki Kobayashi (Kyoto Univ), Yu Nakahata (NAIST), Masahiro Takahashi (Kyoto Univ), Yota Otachi (Nagoya Univ), Kunihiro Wasa (Toyohashi Tech) COMP2021-23
Abstract (in Japanese) (See Japanese page) 
(in English) given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. textsc{Directed Token Sliding} is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions.
In this paper, we initiate the algorithmic study of textsc{Directed Token Sliding}. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees~[Demaine et al.~TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which admits an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.
Keyword (in Japanese) (See Japanese page) 
(in English) / / / / / / /  
Reference Info. IEICE Tech. Rep., vol. 121, no. 285, COMP2021-23, pp. 11-18, Dec. 2021.
Paper # COMP2021-23 
Date of Issue 2021-11-26 (COMP) 
ISSN Online edition: ISSN 2432-6380
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
Download PDF COMP2021-23

Conference Information
Committee COMP  
Conference Date 2021-12-03 - 2021-12-03 
Place (in Japanese) (See Japanese page) 
Place (in English) Kanazawa Chamber of Commerce and Industry 
Topics (in Japanese) (See Japanese page) 
Topics (in English)  
Paper Information
Registration To COMP 
Conference Code 2021-12-COMP 
Language English 
Title (in Japanese) (See Japanese page) 
Sub Title (in Japanese) (See Japanese page) 
Title (in English) Token Sliding on Directed Graphs 
Sub Title (in English)  
1st Author's Name Takehiro Ito  
1st Author's Affiliation Tohoku University (Tohoku Univ)
2nd Author's Name Yuni Iwamasa  
2nd Author's Affiliation Kyoto University (Kyoto Univ)
3rd Author's Name Yasuaki Kobayashi  
3rd Author's Affiliation Kyoto University (Kyoto Univ)
4th Author's Name Yu Nakahata  
4th Author's Affiliation Nara Institute of Science and Technology (NAIST)
5th Author's Name Masahiro Takahashi  
5th Author's Affiliation Kyoto University (Kyoto Univ)
6th Author's Name Yota Otachi  
6th Author's Affiliation Nagoya University (Nagoya Univ)
7th Author's Name Kunihiro Wasa  
7th Author's Affiliation Toyohashi University of Technology (Toyohashi Tech)
8th Author's Name  
8th Author's Affiliation ()
9th Author's Name  
9th Author's Affiliation ()
10th Author's Name  
10th Author's Affiliation ()
11th Author's Name  
11th Author's Affiliation ()
12th Author's Name  
12th Author's Affiliation ()
13th Author's Name  
13th Author's Affiliation ()
14th Author's Name  
14th Author's Affiliation ()
15th Author's Name  
15th Author's Affiliation ()
16th Author's Name  
16th Author's Affiliation ()
17th Author's Name  
17th Author's Affiliation ()
18th Author's Name  
18th Author's Affiliation ()
19th Author's Name  
19th Author's Affiliation ()
20th Author's Name  
20th Author's Affiliation ()
Speaker Author-5 
Date Time 2021-12-03 11:10:00 
Presentation Time 30 minutes 
Registration for COMP 
Paper # COMP2021-23 
Volume (vol) vol.121 
Number (no) no.285 
Page pp.11-18 
Date of Issue 2021-11-26 (COMP) 

[Return to Top Page]

[Return to IEICE Web Page]

The Institute of Electronics, Information and Communication Engineers (IEICE), Japan