 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.44
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10283/
 Go to the corresponding LIPIcs Volume Portal

### Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

 pdf-format:

### Abstract

We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and l columns, x is a vector of l variables, and b is a vector of k integers, we ask whether there exists x in N^l that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and |A|_infty, the largest absolute value of an entry in A, are small. Papadimitriou [Christos H. Papadimitriou, 1981] was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((|A |_infty + |b|_infty) * k)^O(k^2). This was very recently improved by Eisenbrand and Weismantel [Friedrich Eisenbrand and Robert Weismantel, 2018], who used the Steinitz lemma to design an algorithm with running time (k |A|_infty)^{O(k)}* |b|_infty^2, which was subsequently improved by Jansen and Rohwedder [Klaus Jansen and Lars Rohwedder, 2019] to O(k |A |_infty)^k* log |b|_infty. We prove that for {0,1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2^{o(k log k)}* (l+|{b}|_infty)^{o(k)} would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [Fedor V. Fomin et al., 2018]. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter {dual treedepth} of the matrix A, denoted td_D(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. [Martin Koutecký et al., 2018] that {ILP Feasibility} can be solved in time |A |_infty^{2^O(td_D(A))} * (k+l+log |b|_infty)^O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and {b} are in {-1,0,1}, the existence of an algorithm with running time 2^{2^o(td_D(A))} * (k+l)^O(1) would contradict the ETH.

### BibTeX - Entry

```@InProceedings{knop_et_al:LIPIcs:2019:10283,
author =	{Dusan Knop and Michal Pilipczuk and Marcin Wrochna},
title =	{{Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints}},
booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages =	{44:1--44:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-100-9},
ISSN =	{1868-8969},
year =	{2019},
volume =	{126},
editor =	{Rolf Niedermeier and Christophe Paul},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 