Faster ILP Algorithms for Problems with Sparse Matrices and Their Applications to Multipacking and Multicover Problems in Graphs and Hypergraphs
share
Let P be a polyhedron, defined by a system A x ≤ b, where A ∈ Z^m × n, rank(A) = n, and b ∈ Z^m. In the Integer Feasibility Problem, we need to decide whether P ∩ Z^n = ∅ or to find some x ∈ P ∩ Z^n in the opposite case. Currently, its state of the art algorithm, due to <cit.> (see also <cit.> for more general formulations), has the complexity bound O(n)^n · poly(ϕ), where ϕ = size(A,b). It is a long-standing open problem to break the O(n)^n dimension-dependence in the complexity of ILP algorithms. We show that if the matrix A has a small l_1 or l_∞ norm, or A is sparse and has bounded elements, then the integer feasibility problem can be solved faster. More precisely, we give the following complexity bounds min{A_∞, A_1}^5 n· 2^n · poly(ϕ), ( A_max)^5 n·min{cs(A),rs(A)}^3 n· 2^n · poly(ϕ). Here A_max denotes the maximal absolute value of elements of A, cs(A) and rs(A) denote the maximal number of nonzero elements in columns and rows of A, respectively. We present similar results for the integer linear counting and optimization problems. Additionally, we apply the last result for multipacking and multicover problems on graphs and hypergraphs, where we need to choose a minimal/maximal multiset of vertices to cover/pack the edges by a prescribed number of times. For example, we show that the stable multiset and vertex multicover problems on simple graphs admit FPT-algorithms with the complexity bound 2^O(|V|)· poly(ϕ), where V is the vertex set of a given graph.
READ FULL TEXT