Finding a Reconfiguration Sequence between Longest Increasing Subsequences
IEICE Transactions on Information and Systems
Online ISSN : 1745-1361
Print ISSN : 0916-8532
Regular Section
Finding a Reconfiguration Sequence between Longest Increasing Subsequences
Yuuki AOIKEMasashi KIYOMIYasuaki KOBAYASHIYota OTACHI
Author information
JOURNAL FREE ACCESS

2024 Volume E107.D Issue 4 Pages 559-563

Details
Abstract

In this note, we consider the problem of finding a step-by-step transformation between two longest increasing subsequences in a sequence, namely Longest Increasing Subsequence Reconfiguration. We give a polynomial-time algorithm for deciding whether there is a reconfiguration sequence between two longest increasing subsequences in a sequence. This implies that Independent Set Reconfiguration and Token Sliding are polynomial-time solvable on permutation graphs, provided that the input two independent sets are largest among all independent sets in the input graph. We also consider a special case, where the underlying permutation graph of an input sequence is bipartite. In this case, we give a polynomial-time algorithm for finding a shortest reconfiguration sequence (if it exists).

Content from these authors
© 2024 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top