Designing Compact ILPs via Fast Witness Verification
Michał Włodarczyk · 2025
Read Designing Compact ILPs via Fast Witness Verification by Michał Włodarczyk (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-2509-25445.txt.
Introduction
Michał Włodarczyk wrote this 2025 theory paper on shrinking hard problems before solving them. In the study of parameterized problems, a common trick is to trim an input down to a small core. Some problems resist that trick, so he asks a different question: when can an input be turned into a small integer linear program instead?
He shows this is possible exactly for a known class of problems called WK[1]. The link runs through short proofs that a fast check can verify. He builds such checks for problems such as Steiner Tree and several kinds of graph cuts. He also gives direct program forms for weighted vertex cover on some graphs.
Catalog record
| CREATOR | Michał Włodarczyk |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-25445
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Designing Compact ILPs via Fast Witness Verification Michał Włodarczyk Abstract The standard formalization of preprocessing in parameterized complexity is given by kernelization. In this work, we depart from this paradigm and study a different type of preprocessing for problems without polynomial kernels, still aiming at producing instances that are easily solvable in practice. Specifically, we ask for which parameterized problems an instance ( I , k ) (I,k) can be reduced in polynomial time to an integer linear program (ILP) with 𝗉𝗈𝗅𝗒 ( k ) \mathsf{poly}(k) constraints. We show that this property coincides with the parameterized complexity class WK[1], previously studied in the context of Turing kernelization lower bounds. In turn, the class WK[1] enjoys an elegant characterization in terms of witness verification protocols: a yes-instance should admit a witness of size 𝗉𝗈𝗅𝗒 ( k ) \mathsf{poly}(k) that can be verified in time 𝗉𝗈𝗅𝗒 ( k ) \mathsf{poly}(k) . By combining known data structures with new ideas, we design such protocols for several problems, such as r r -Way Cut , Vertex Multiway Cut , Steiner Tree , and Minimum Common String Partition , thus showing that they can be modeled by compact ILPs. We also present explicit ILP and MILP formulations for Weighted Vertex Cover on graphs with small (unweighted) vertex cover number. We believe that these results will provide a background for a systematic study of ILP-oriented preprocessing procedures for parameterized problems. University of Warsaw, [email protected]://orcid.org/0000-0003-0968-8414 ccs Theory of computation Parameterized complexity and exact algorithms keywords integer programming, kernelization, nondeterminism, multiway cut † † runningauthor: M. Włodarczyk † † copyright: Michał Włodarczyk † † funding: Supported by Polish National Science Centre SONATA-19 grant 2023/51/D/ST6/00155. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Kernelization [ 38 ] provides a rigorous theory for data preprocessing in the following sense: given an instance I with parameter k we would like to transform it in polynomial time into an equivalent instance (I^{\prime},k^{\prime}) so that |I^{\prime}|+k^{\prime}\leq f(k) for a slowly growing function f . Historically, kernelization was meant as just another tool for establishing fixed-parameterized tractability [ 25 ] but later it grew into a mature theory on its own, especially after a hardness framework has been established [ 6 ] . The main question in this paradigm is: which parameterized problems admit polynomial kernels, that is, when can the function f be estimated as polynomial? From the practical point of view, once the instance size is reduced, it may become amenable to brute-force or heuristic methods. In recent years, empirical observations have provided evidence that analyzing preprocessing through the lens of kernelization might be too restrictive. In the annual PACE challenge [ 29 , 43 , 54 , 55 ] , co-organized with the IPEC conference, competitors solve a collection of instances of a certain NP-hard problem related to parameterized complexity. It turned out that the many successful submissions [ 3 , 4 , 9 , 23 , 24 ] do not follow the algorithms from FPT handbooks but instead reduce the problem to (mixed) integer linear programming (ILP) and then employ a specialized solver. Even though the contestants are not allowed to use the state-of-the-art industrial solvers, already the open source solvers often outperform sophisticated FPT algorithms with provable worst-case guarantees. However, it is usually challenging to model the problem in question as a concise ILP. In our opinion, parameterized complexity should seek an explanation of this phenomenon and understand which problems can be handled with ILP-driven preprocessing. In this work, we make a first step in this direction and investigate one of the possible ways of formalizing such a notion of preprocessing. Even though modeling NP-hard problems as succinct (mixed) ILPs has been a subject of operation research since 1950s [ 14 , 22 , 37 , 42 , 66 , 67 , 72 ] , no systematical study has addressed this question from the perspective of parameterized complexity so far. What kind of preprocessing? Following the design of kernelization theory, we consider polynomial-time procedures that output an equivalent instance (of a possibly different decision problem) that should be well-structured as long as the initial parameter is not too large. While there are many ways to measure the difficulty of an ILP [ 49 , 1 , 18 , 40 , 36 , 30 , 11 , 51 , 17 , 28 ] , the most natural are the number of constraints and the number of variables. In this work, we focus on the first one. Specifically, we are interested in processing an instance (I,k) in polynomial time to rewrite it as an ILP of the form (Ax\leq b,\,x\in\mathbb{Z}^{n}_{\geq 0}) , where A\in\mathbb{Z}^{m\times n},\,b\in\mathbb{Z}^{m} , and m is polynomially bounded in k . In other words, we would like to reduce solving the problem in question to feasibility check of an ILP with only \mathsf{poly}(k) constraints. This strategy matches the assumption guiding the kernelization paradigm: when the parameter k is small, then heuristic algorithms should work fast in practice when the search space has ‘‘dimension’’ 1 1 1 Usually the “dimension” of an ILP refers to the number of variables but the known FPT algorithms [ 32 , 52 ] for solving ILP parameterized by the number of constraints m perform computations in a lattice of dimension m . \mathsf{poly}(k) . Naturally, it would be desirable to obtain ILP formulations with m=\mathcal{O}(k) or m=\mathcal{O}(k^{2}) but we believe that a new framework should first focus on establishing general bounds and more fine-grained results will follow. For comparison, the first work on polynomial kernelization for Feedback Vertex Set only guaranteed a kernel of size \mathcal{O}(k^{11}) [ 13 ] but it was soon improved to \mathcal{O}(k^{2}) [ 70 ] . What kind of problems? Before we delve further into technicalities, let us reflect on for which parameterized problems the question above makes sense. First of all, we are interested in problems without (known) polynomial kernels. Secondly, any problem that can be reduced as described above must (1) belong to NP and (2) admit an FPT algorithm with running time of the form 2^{\mathsf{poly}(k)}\cdot n^{\mathcal{O}(1)} [ 52 ] . Restricting to only such problems allows us to assume \log n\leq\mathsf{poly}(k) because otherwise the FPT running time above can be estimated as polynomial in n . Later we will also see another property that must be satisfied: an instance (I,k) should admit an NP-witness of size \mathsf{poly}(k,\log|I|) . Therefore, we should not hope to handle structural parameterizations like treewidth due to known barriers [ 27 ] . Fast witness verification. The question outlined above can be formalized in the following way: we ask which parameterized problems admit a polynomial parameter transformation (PPT) to ILP feasibility checking parameterized by the number of constraints. It is easy to see that Set Cover parameterized by the universe size admits such a reduction and we will present a reduction in the opposite direction as well. In turn,