TY - GEN

T1 - A Fast Algorithm for Unbounded Monotone Integer Linear Systems with Two Variables per Inequality via Graph Decomposition

AU - Tamori, Takuya

AU - Kimura, Kei

N1 - Funding Information:
by JSPS KAKENHI Grant
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

PY - 2019

Y1 - 2019

N2 - In this paper, we consider the feasibility problem of integer linear systems where each inequality has at most two variables. Although the problem is known to be weakly NP-complete by Lagarias, it has many applications and, importantly, a large subclass of it admits (pseudo-)polynomial algorithms. Indeed, the problem is shown pseudo-polynomially solvable if every variable has upper and lower bounds by Hochbaum, Megiddo, Naor, and Tamir. However, determining the complexity of the general case, pseudo-polynomially solvable or strongly NP-complete, is a longstanding open problem. In this paper, we reveal a new efficiently solvable subclass of the problem. Namely, for the monotone case, i.e., when two coefficients of the two variables in each inequality are opposite signs, we associate a directed graph to any instance, and present an algorithm that runs in time, where s is the length of the input and is the maximum number of the vertices in any strongly connected component of the graph. If is a constant, the algorithm runs in polynomial time. From the result, it can be observed that the hardness of the feasibility problem lies on large strongly connected components of the graph.

AB - In this paper, we consider the feasibility problem of integer linear systems where each inequality has at most two variables. Although the problem is known to be weakly NP-complete by Lagarias, it has many applications and, importantly, a large subclass of it admits (pseudo-)polynomial algorithms. Indeed, the problem is shown pseudo-polynomially solvable if every variable has upper and lower bounds by Hochbaum, Megiddo, Naor, and Tamir. However, determining the complexity of the general case, pseudo-polynomially solvable or strongly NP-complete, is a longstanding open problem. In this paper, we reveal a new efficiently solvable subclass of the problem. Namely, for the monotone case, i.e., when two coefficients of the two variables in each inequality are opposite signs, we associate a directed graph to any instance, and present an algorithm that runs in time, where s is the length of the input and is the maximum number of the vertices in any strongly connected component of the graph. If is a constant, the algorithm runs in polynomial time. From the result, it can be observed that the hardness of the feasibility problem lies on large strongly connected components of the graph.

UR - http://www.scopus.com/inward/record.url?scp=85062675710&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062675710&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-10564-8_17

DO - 10.1007/978-3-030-10564-8_17

M3 - Conference contribution

AN - SCOPUS:85062675710

SN - 9783030105631

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 209

EP - 218

BT - WALCOM

A2 - Das, Gautam K.

A2 - Mandal, Partha S.

A2 - Mukhopadhyaya, Krishnendu

A2 - Nakano, Shin-ichi

PB - Springer Verlag

T2 - 13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019

Y2 - 27 February 2019 through 2 March 2019

ER -