{"ID":2850383,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.22430","arxiv_id":"2510.22430","title":"On Integer Programs That Look Like Paths","abstract":"Solving integer programs of the form $\\min \\{\\mathbf{x} \\mid A\\mathbf{x} = \\mathbf{b}, \\mathbf{l} \\leq \\mathbf{x} \\leq \\mathbf{u}, \\mathbf{x} \\in \\mathbb{Z}^n \\}$ 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$ 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$ are bounded by 8, deciding the feasibility of such integer programs is $\\mathsf{NP}$-hard via a reduction from 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.","short_abstract":"Solving integer programs of the form $\\min \\{\\mathbf{x} \\mid A\\mathbf{x} = \\mathbf{b}, \\mathbf{l} \\leq \\mathbf{x} \\leq \\mathbf{u}, \\mathbf{x} \\in \\mathbb{Z}^n \\}$ is, in general, $\\mathsf{NP}$-hard. Hence, great effort has been put into identifying subclasses of integer programs that are solvable in polynomial or $\\mat...","url_abs":"https://arxiv.org/abs/2510.22430","url_pdf":"https://arxiv.org/pdf/2510.22430v1","authors":"[\"Marcin Briański\",\"Alexandra Lassota\",\"Kristýna Pekárková\",\"Michał Pilipczuk\",\"Janina Reuter\"]","published":"2025-10-25T20:28:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}