Knop, Dusan ;
Pilipczuk, Michal ;
Wrochna, Marcin
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
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 fixedparameter 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 nontight 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 nonzero 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:144:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10283},
doi = {10.4230/LIPIcs.STACS.2019.44},
annote = {Keywords: integer linear programming, fixedparameter tractability, ETH}
}
12.03.2019
Keywords: 

integer linear programming, fixedparameter tractability, ETH 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

12.03.2019 