TY - JOUR

T1 - Trichotomy for integer linear systems based on their sign patterns

AU - Kimura, Kei

AU - Makino, Kazuhisa

N1 - Funding Information:
The first author is supported by the Global COE “The Research and Training Center for New Development in Mathematics”, the Research Fellowship of the Japan Society for the Promotion of Science for Young Scientists , and by JST, ERATO , Kawarabayashi Large Graph Project. The second author is supported by KAKENHI Grant Number 22500007 , 24106002 , 26280001 .
Publisher Copyright:
© 2015 Elsevier B.V.

PY - 2016/2/19

Y1 - 2016/2/19

N2 - In this paper, we consider solving the integer linear systems, i.e., given a matrix A∈Rm×n, a vector b∈Rm, and a positive integer d, to compute an integer vector x∈Dn such that Ax≥b or to determine the infeasibility of the system, where m and n denote positive integers, R denotes the set of reals, and D={0,1,...,d-1}. The problem is one of the most fundamental NP-hard problems in computer science. For the problem, we propose a complexity index η which depends only on the sign pattern of A. For a real γ, let ILS(γ) denote the family of the problem instances I with η(I)=γ. We then show the following trichotomy: ILS(γ) is solvable in linear time, if γ<1,ILS(γ) is weakly NP-hard and pseudo-polynomially solvable, if γ=1,ILS(γ) is strongly NP-hard, if γ>1. This, for example, includes the previous results that Horn systems and two-variable-per-inequality (TVPI) systems can be solved in pseudo-polynomial time.

AB - In this paper, we consider solving the integer linear systems, i.e., given a matrix A∈Rm×n, a vector b∈Rm, and a positive integer d, to compute an integer vector x∈Dn such that Ax≥b or to determine the infeasibility of the system, where m and n denote positive integers, R denotes the set of reals, and D={0,1,...,d-1}. The problem is one of the most fundamental NP-hard problems in computer science. For the problem, we propose a complexity index η which depends only on the sign pattern of A. For a real γ, let ILS(γ) denote the family of the problem instances I with η(I)=γ. We then show the following trichotomy: ILS(γ) is solvable in linear time, if γ<1,ILS(γ) is weakly NP-hard and pseudo-polynomially solvable, if γ=1,ILS(γ) is strongly NP-hard, if γ>1. This, for example, includes the previous results that Horn systems and two-variable-per-inequality (TVPI) systems can be solved in pseudo-polynomial time.

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

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

U2 - 10.1016/j.dam.2015.07.004

DO - 10.1016/j.dam.2015.07.004

M3 - Article

AN - SCOPUS:84959377343

VL - 200

SP - 67

EP - 78

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -