标题： 关于看起来像路径的整数规划 显示英文标题

标题： On Integer Programs That Look Like Paths

摘要： 求解形式为$\min \{\mathbf{x} \mid A\mathbf{x} = \mathbf{b}, \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n \}$的整数规划问题，在一般情况下是$\mathsf{NP}$-难的。 因此，人们投入了大量努力来识别可以在多项式或$\mathsf{FPT}$时间内求解的整数规划子类。 这些整数规划中的许多都具有约束矩阵的星型结构。 arguably 最简单的不是星型的形式是路径。 我们研究约束矩阵$A$具有这种路径型结构的整数规划：每个非零系数最多出现在两个连续的约束中。 我们证明，即使所有$A$的系数都被限制为 8，通过从 3-SAT 的约简，判断此类整数规划的可行性是$\mathsf{NP}$-难的。 鉴于存在针对具有星型结构的整数规划的有效算法，以及一个密切相关的情况，其中每列的绝对值之和被限制为 2（因此，每列最多有两个非零元素，其大小不超过 2），这一难度结果令人惊讶。 显示英文摘要

摘要： 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.