On Integer Programs That Look Like Paths M.P. was supported by the project BOBR that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 948057. K.P. was supported by the project GA24-11098S of the Czec

Marcin Briański, Alexandra Lassota, Kristýna Pekárková, Michał Pilipczuk, Janina Reuter · 2025

Read On Integer Programs That Look Like Paths M.P. was supported by the project BOBR that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 948057. K.P. was supported by the project GA24-11098S of the Czec by Marcin Briański, Alexandra Lassota, Kristýna Pekárková, Michał Pilipczuk, Janina Reuter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22430.txt.

Introduction

Marcin Briański and four co-authors study integer programs whose constraint matrix has a path like shape, where each non zero entry appears in at most two neighbouring constraints. Such programs are hard in general, and much work seeks special shapes that can be solved fast. Star shaped matrices were known to be easier, so the path shape was a natural next case.

Surprisingly, the team proves the problem stays hard even when every coefficient is at most eight, by reducing from a classic satisfiability problem. The result is striking because a close cousin with tiny column sums is tractable. It maps a sharp border between easy and hard shapes.

Catalog record

CREATORMarcin Briański, Alexandra Lassota, Kristýna Pekárková, Michał Pilipczuk, Janina Reuter
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22430

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Integer Programs That Look Like Paths M.P. was supported by the project BOBR that is funded from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme with grant agreement No. 948057. K.P. was supported by the project GA24-11098S of the Czech Science Foundation at the beginning of the project, and by the funding received from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 101002854) towards the end of the project. Marcin Briański, Alexandra Lassota, Kristýna Pekárková, Michał Pilipczuk, Janina Reuter Abstract Solving integer programs of the form min { 𝐱 | A 𝐱 = 𝐛 , 𝐥 ⩽ 𝐱 ⩽ 𝐮 , 𝐱 ∈ ℤ n } \min\bigl\{\mathbf{x}\bigm|A\mathbf{x}=\mathbf{b},\mathbf{l}\leqslant\mathbf{x}\leqslant\mathbf{u},\mathbf{x}\in\mathbb{Z}^{n}\bigr\} is, in general, 𝖭𝖯 \mathsf{NP} - hard. Hence, great effort has been put into identifying subclasses of integer programs that are solvable in polynomial or 𝖥𝖯𝖳 \mathsf{FPT} time. A common scheme for many of these integer programs is a star-like structure of the constraint matrix. The arguably simplest form that is not a star is a path. We study integer programs where the constraint matrix A A has such a path-like structure: every non-zero coefficient appears in at most two consecutive constraints. We prove that even if all coefficients of A A are bounded by 8 8 , deciding the feasibility of such integer programs is 𝖭𝖯 \mathsf{NP} - hard via a reduction from 3 3 -SAT. Given the existence of efficient algorithms for integer programs with star-like structures and a closely related pattern where the sum of absolute values is column-wise bounded by 2 (hence, there are at most two non-zero entries per column of size at most 2), this hardness result is surprising. 1 Introduction We study integer programs (to which we refer to as IP s) of the form \min\bigl\{\mathbf{x}\bigm|A\mathbf{x}=\mathbf{b},\mathbf{l}\leqslant\mathbf{x}\leqslant\mathbf{u},\mathbf{x}\in\mathbb{Z}^{n}\bigr\}, (G) with constraint matrix A\in\mathbb{Z}^{m\times n} , right-hand side \mathbf{b}\in\mathbb{Z}^{m} , lower and upper bounds \mathbf{l}\in(\mathbb{Z}\cup\{-\infty\})^{n} and \mathbf{u}\in(\mathbb{Z}\cup\{\infty\})^{n} . Solving such IPs means to either decide that the system is infeasible, there exists an optimal feasible solution (and give the value of it), or it is unbounded and provides a solution with an unbounded direction of improvement. Note that restricting to equality constraints does not restrict the problem, as every inequality constraint can be turned to equality by introducing slack variables (which also preserve the special structures we discuss in this paper). Integer programming is a powerful tool that has been applied to many combinatorial problems, such as scheduling and bin packing [ 13 , 18 ] , graph problems [ 8 , 9 ] , multichoice optimization [ 7 ] and computational social choice [ 1 , 21 ] , among others. Unfortunately, solving integer programs is, in general, \mathsf{NP} - hard. This motivated a flourishing line of research that aims to understand the structural properties of matrices that allow the corresponding IPs to be solved efficiently, see, e.g. [ 8 , 13 , 14 , 18 , 21 ] . Arguably, the most famous is Lenstra’s 1983 algorithm, which introduced the first \mathsf{FPT} time algorithm for constraint matrices with few columns [ 19 ] . The body of literature for the over three decades-long research and the many structures, parameters, and applications is too vast to cover here; we thus refer to [ 12 ] for an overview. One striking property for many of these IPs is the star-likeness of the constraint matrix, which is probably best exemplified by n -fold and 2 -stage stochastic integer programs. Here, an integer program is of n -fold form if its constraint matrix, after removing at most k rows ( aka constraints), consists of n independent blocks with at most k rows each. The transpose of this matrix is called 2 -stage stochastic integer programs, i.e., after removal of at most k columns ( aka variables), they are decomposed into independent blocks with at most k columns each. As proven in [ 16 , 15 ] , the optimization problem for n -fold and 2 -stage stochastic integer programs can be solved in time f(k,\Delta)\cdot|I|^{1+o(1)} , where f is a computable function, \Delta is the largest absolute coefficient in the constraint matrix, and |I| is the total bitsize of the instance. This running time is \mathsf{FPT} with parameters k and \Delta . The structure of n -fold and 2-stage stochastic integer programs can be generalized by allowing multiple stages of deleting rows or columns and decomposing into blocks. This gives rise to so-called tree-fold and multistage stochastic integer programs, which retain efficient solvability, see, e.g., [ 6 , 3 ] . The structure of tree-fold and multistage stochastic IPs can be perhaps best understood through decompositions of the associated graphs. For a matrix A , we define the constraint graph of A as the graph on the rows (constraints) of A in which two rows are adjacent if they simultaneously have non-zero entries in the same column (in other words, there is a variable appearing in both the corresponding constraints). The variable graph of A is defined symmetrically for the columns (variables) of A . Then, the primal treedepth of A is the treedepth of its variable graph, and the dual treedepth of A is the treedepth of its constraint graph. Here, the treedepth of a graph is a parameter that measures star-likeness through the maximum depth of a procedure that alternately deletes a vertex and decomposes the graph into connected components, see for example [ 23 , Chapter 6] for a broad introduction. As proven in [ 17 , 10 , 11 ] , the optimization problem for integer programs can be solved in time f(d,\Delta)\cdot|I|^{1+o(1)} for a computable function f , where d is either the primal or the dual treedepth of the constraint matrix. We refer the reader to the article of Eisenbrand, Hunkenschröder, Klein, Koutecký, Levin and Onn [ 6 ] for a comprehensive introduction to the theory of parameterized algorithms for block-structured integer programming. It is, therefore, natural to ask to what extent the (primal or dual) treedepth of the constraint matrix captures the efficient solvability of integer programs. Several results in the literature suggest that integer programming quickly becomes \mathsf{NP} - hard once one relaxes the assumption of bounded treedepth. For instance, Ganian and Ordyniak [ 10 ] showed that the feasibility problem for integer programs of the form \{\mathbf{x}\,\mid\,A\mathbf{x}\leqslant\mathbf{b}\} is \mathsf{NP} -hard even when all the entries of A and \mathbf{b} are in \{-2,-1,0,1,2\} and the treewidth of the constraint graph of A is at most 4 . Their reduction is based on an earlier work of Jansen and Kratsch [ 17 ] , who achieved a similar result, but without obtaining the bound on the entries. We note that Ganian and Ordyniak stated their result in terms of the treewidth of the incidence graph of A : the bipartite graph on rows and columns of A where a row is adjacent to a column if the entry at their intersection is non-zero. As shown in [ 10 ] , the treewidth of the incidence graph of the constructed matrix is at most 3 , but one can also easily verify that the treewidth of the

Read the complete text