# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 3 Solving ILPs with Explicit Restrictions
Notably, after factoring in Proposition 1 their result states:Theorem 10: ILP can be solved in time \(\Gamma^{\mathcal{O}(\mathrm{tw}_{I}(\mathcal{I}))}\cdot|\mathcal{I}|\), where \(\Gamma\) is the maximum absolute value of any partial evaluation of a constraint by any feasible assignment of \(\mathcal{I}\); here, a partial evaluation of a constraint/row \(\mathbf{r}\) of \(A\) with a feasible assignment \(\mathbf{x}\) is equal to \(\mathbf{rx}^{\prime}\), where \(\mathbf{x}^{\prime}\) is any vector obtained from \(\mathbf{x}\) after setting some of its entries to \(0\). Note that \(\Gamma\leq n\|A\|_{\infty}d\), where \(d\) is the maximum domain span of every variable in \(\mathcal{I}\). Hence, Theorem 10, e.g., implies that fully unary ILP can be solved in polynomial-time if \(\mathrm{tw}_{I}(\mathcal{I})\) is bounded by a constant. On the other hand, ILPF remains \(\mathbf{NP}\)-complete even when restricted to instances with strong restrictions on the treewidth and coefficients--to some extent justifying the dependency of the above algorithm on \(\Gamma\). Indeed, the first part of the following theorem follows from the classical encoding of Subset Sum into ILPF, while the second part was shown by [PERSON] et al. [40]. Theorem 11: ILPF _remains \(\mathbf{NP}\)-complete even on instances \(\mathcal{I}\) with (1) \(\mathrm{tw}_{I}(\mathcal{I})=1\) and Boolean domains for all variables, as well as with (2) \(\mathrm{tw}_{I}(\mathcal{I})\leq 3\) and \(\max(\|A\|_{\infty},\|\mathbf{b}\|)=2\)._  
A natural question is whether one can use \(\mathrm{td}_{I}(\mathcal{I})\) instead of \(\mathrm{tw}_{I}(\mathcal{I})\) in order to obtain tractability for ILP under a weaker restriction than by bounding \(\Gamma\)--notably, can one lift Theorems 7 and 8 to the incidence treedepth setting? Very recently, [PERSON] et al. [41] answered the question in the negative by showing:  
Theorem 12 ([41]): ILP _remains \(\mathbf{NP}\)-complete even when restricted to instances \(\mathcal{I}\) such that \(\max(\|A\|_{\infty},\|\mathbf{b}\|)=1\) and \(\mathrm{td}_{I}(\mathcal{I})\leq 5\)._  
In the full version of that paper, they also showed that restricting the structure by the size of a minimum vertex cover of \(G_{I}(\mathcal{I})\)--a significantly stronger restriction than treedepth--leads to tractability. Theorem 13: ILP _is \(\mathbf{FPT}\) parameterized by \(\|A\|_{\infty}\) and the vertex cover number of \(G_{I}(\mathcal{I})\)._  
Note that even though the vertex cover number is sensitive to changes between the equality and inequality form of ILP in general, the above theorem still holds for both forms. This is because the proof of Theorem 13 works by first observing that the number of (linearly independent) equalities is bounded by a function of the vertex cover number and \(\|A\|_{\infty}\) and then uses Theorem 2 to show tractability. Almost the same approach can be used for inequalities, i.e., one can again observe that the number of inequalities is bounded in terms of the parameters (otherwise there are redundant inequalities) and then use the standard reduction from \(\mathrm{ILP}_{\leq}\) to \(\mathrm{ILP}_{=}\); since the reduction does not increase the number of constraints, one can again apply Theorem 2. We conclude this section by touching on the complexity of integer linear programs whose graph representations have an extremely simple structure--notably, have treewidth 1 (i.e., are acyclic). This setting was investigated by [PERSON] et al. [42], who showed that \(\mathrm{ILP}_{\leq}\) restricted to unary instances whose graph representations are acycllic exhibit a different complexity behavior than ILP restricted to instances of bounded treewidth. We summarize their results in Table 1.