We study the existence of polynomial kernels for the problem of deciding feasibility of integer linear programs (ILPs), and for finding good solutions for covering and packing ILPs. Our main results are as follows: First, we show that the ILP Feasibility problem admits no polynomial kernelization when parameterized by both the number of variables and the number of constraints, unless NP C coNP/poly. This extends to the restricted cases of bounded variable degree and bounded number of variables per constraint, and to covering and packing ILPs. Second, we give a polynomial kernelization for the Cover ILP problem, asking for a solution to Ax ≥ b with c~Tx ≤ k, parameterized by k, when A is row-sparse; this generalizes a known polynomial kernelization for the special case with 0/1-variables and coefficients (d-Hitting Set).
展开▼
机译：我们研究多项式内核的存在，以决定整数线性程序（ILP）的可行性，并找到覆盖和打包ILP的良好解决方案。我们的主要结果如下：首先，我们证明了ILP可行性问题在通过变量数量和约束数量进行参数化时不接受多项式核化，除非NP C coNP / poly。这扩展到有界变量度和每个约束变量的有界数的受限情况，以及覆盖和打包ILP。其次，我们为Cover ILP问题提供了多项式核化，当A为行稀疏时，要求用k参数化c〜Tx≤k的Ax≥b的解。对于具有0/1变量和系数（d-Hitting Set）的特殊情况，这概括了已知的多项式核化。
展开▼
