2013/02/14 by Stefan Kratsch, Kratsch, Stefan
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Scheduling and Optimization Algorithms #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1302.3494
To appear in STACS 2013
openalex publication_date 2013/02/14 · arxiv created 2013/02/15 · arxiv updated 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Integer linear programs (ILPs) are a widely applied framework for dealing with combinatorial problems that arise in practice. It is known, e.g., by the success of CPLEX, that preprocessing and simplification can greatly speed up the process of optimizing an ILP. The present work seeks to further the theoretical understanding of preprocessing for ILPs by initiating a rigorous study within the framework of parameterized complexity and kernelization. A famous result of Lenstra (Mathematics of Operations Research, 1983) shows that feasibility of any ILP with n variables and m constraints can be decided in time O(cn3 mc'). Thus, by a folklore argument, any such ILP admits a kernelization to an equivalent instance of size O(cn3). It is known, that unless NP ⊆ coNP/poly and the polynomial hierarchy collapses, no kernelization with size bound polynomial in n is possible. However, this lower bound only applies for the case when constraints may include an arbitrary number of variables since it follows from lower bounds for Satisfiability and Hitting Set, whose bounded arity variants admit polynomial kernelizations. We consider the feasibility problem for ILPs Ax<= b where A is an r-row-sparse matrix parameterized by the number of variables. We show that the kernelizability of this problem depends strongly on the range of the variables. If the range is unbounded then this problem does not admit a polynomial kernelization unless NP ⊆ coNP/poly. If, on the other hand, the range of each variable is polynomially bounded in n then we do get a polynomial kernelization. Additionally, this holds also for the more general case when the maximum range d is an additional parameter, i.e., the size obtained is polynomial in n+d.