Faster algorithms for sparse ILP and hypergraph multi-packing/multi-cover problems

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in $${{\,\mathrm{\mathcal {P}}\,}}\cap {{\,\mathrm{\mathbb {Z}}\,}}^n$$ P ∩ Z n , assuming that $${{\,\mathrm{\mathcal {P}}\,}}$$ P is a polyhedron, defined by systems $$A x \le b$$ A x ≤ b or $$Ax = b,\, x \ge 0$$ A x = b , x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form $$s^{O(n)}$$ s O ( n ) , where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For $$s = o\bigl (\log n \bigr )$$ s = o ( log n ) , this bound outperforms the state-of-the-art ILP feasibility complexity bound $$(\log n)^{O(n)}$$ ( log n ) O ( n ) , due to Reis & Rothvoss (in: 2023 IEEE 64th Annual symposium on foundations of computer science (FOCS), IEEE, pp. 974–988). For $$s = \phi ^{o(\log n)}$$ s = ϕ o ( log n ) , where $$\phi $$ ϕ denotes the input bit-encoding length, it outperforms the state-of-the-art ILP counting complexity bound $$\phi ^{O(n \log n)}$$ ϕ O ( n log n ) , due to Barvinok et al. (in: Proceedings of 1993 IEEE 34th annual foundations of computer science, pp. 566–572, https://doi.org/10.1109/SFCS.1993.366830 , 1993), Dyer, Kannan (Math Oper Res 22(3):545–549, https://doi.org/10.1287/moor.22.3.545 , 1997), Barvinok, Pommersheim (Algebr Combin 38:91–147, 1999), Barvinok (in: European Mathematical Society, ETH-Zentrum, Zurich, 2008). We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems.