Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems

Journal of Global Optimization. 2024. Vol. 89. P. 1033–1067.

Gribanov D., Shumilov I., Malyshev D., Zolotykh N. Y.

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 P ∩ Zn , assuming that P is a polyhedron, defined by systems Ax ≤ b or Ax = 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), where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For s = o(log n), this bound outperforms the state-of- the-art ILP feasibility complexity bound (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 = φo(log n), where φ denotes the input bit-encoding length, it outperforms the state-of- the-art ILP counting complexity bound φ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.

Keywords: integer linear programming, sparse matrix, dominating set, stable set, parameterized complexity, Counting Problem, Multipacking, Multicover, vertex cover, hypergraph matching

Publication based on the results of: Network models, optimization and computational complexity (2024)