TY - GEN

T1 - Trichotomy for the reconfiguration problem of integer linear systems

AU - Kimura, Kei

AU - Suzuki, Akira

N1 - Funding Information:
The first author is partially supported by JSPS KAKENHI Grant Number JP17K12636. The second author is partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP17K12636 and JP18H04091, Japan.
Funding Information:
The first author is partially supported by JSPS KAKENHI Grant Number JP17K12636. The second author is partially supported by JST CREST Grant Number JPMJCR1402, and JSPSKAKENHI Grant Numbers JP17K12636 and JP18H04091, Japan.
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.

KW - Combinatorial reconfiguration

KW - Complexity index

KW - Integer linear systems

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 -