TY - GEN
T1 - Trichotomy for the reconfiguration problem of integer linear systems
AU - Kimura, Kei
AU - Suzuki, Akira
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2020.
PY - 2020
Y1 - 2020
N2 - In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system I and two feasible solutions s and t of I, and then asked to transform s to t by changing a value of only one variable at a time, while maintaining a feasible solution of I throughout. Z(I) for I is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67–78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index Z(I) of given I. We show that the problem is (i) solvable in constant time if Z(I) is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if Z(I) is exactly one, and (iii) PSPACE-complete if Z(I) is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge.
AB - In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system I and two feasible solutions s and t of I, and then asked to transform s to t by changing a value of only one variable at a time, while maintaining a feasible solution of I throughout. Z(I) for I is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67–78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index Z(I) of given I. We show that the problem is (i) solvable in constant time if Z(I) is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if Z(I) is exactly one, and (iii) PSPACE-complete if Z(I) is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge.
UR - http://www.scopus.com/inward/record.url?scp=85080877601&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85080877601&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-39881-1_29
DO - 10.1007/978-3-030-39881-1_29
M3 - Conference contribution
AN - SCOPUS:85080877601
SN - 9783030398804
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 336
EP - 341
BT - WALCOM
A2 - Rahman, M. Sohel
A2 - Sadakane, Kunihiko
A2 - Sung, Wing-Kin
PB - Springer
T2 - 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020
Y2 - 31 March 2020 through 2 April 2020
ER -