# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 3 Solving ILPs with Explicit Restrictions
One year after [PERSON] and [PERSON]'s result, [PERSON] and [PERSON] used a reduction from Subset Sum to rule out the application of treewidth In the setting of unbounded domain--even for extremely restricted instances of ILPF. **Theorem 6** ([38]). : ILPF _is_ **NP**_-complete even when restricted to instances \(\mathcal{I}\) such that \(\operatorname{tw}_{P}(\mathcal{I})\leq 2\) and \(\|\mathbf{b}\|=\|A\|_{\infty}=1\)._  
In the same paper, [PERSON] and [PERSON] complemented this result with a fixed-parameter algorithm for ILP parameterized by \(\operatorname{td}_{P}(\mathcal{I})+\|A\|_{\infty}+\|\mathbf{b}\|\); the proof uses a pruning technique which transforms the instance into an equivalent one of size bounded by the parameter (a \"kernel\"). Their result was later superseded by [PERSON], [PERSON] and [PERSON] [39], who used Graver-best oracles to show:  
**Theorem 7** ([39]). : ILP _is_ **FPT** _when parameterized by \(\operatorname{td}_{P}(\mathcal{I})+\|A\|_{\infty}\)._  
We note that both parameters \(\operatorname{td}_{P}(\mathcal{I})\) and \(\|A\|_{\infty}\) are required to achieve even XP algorithms: it is well known that ILP is **NP**-hard when restricted to instances with \(\|A\|_{\infty}=1\), and [PERSON] and [PERSON] [38] showed that it is also **NP**-hard when restricted to instances with \(\operatorname{td}_{P}(\mathcal{I})\leq 4\). It is worth noting that both Theorem 7 and its predecessor have a non-elementary dependency on the parameter. In their paper, [PERSON], [PERSON] and [PERSON] also used the same techniques to obtain a fixed-parameter algorithm that uses the treedepth of the dual graph (as opposed to the primal one):  
**Theorem 8** ([39]). : ILP _is_ **FPT** _when parameterized by \(\operatorname{td}_{D}(\mathcal{I})+\|A\|_{\infty}\)._  
They also established an analogue to Theorem 6 for dual graphs, showing that restricting the dual or primal graphs leads to a similar complexity behavior for ILP:  
**Theorem 9** ([39]). : ILPF _is_ **NP**_-complete even when restricted to instances \(\mathcal{I}\) such that \(\operatorname{tw}_{D}(\mathcal{I})\leq 3\) and with \(\|A\|_{\infty}=2\)._  
Since the classical encoding of Subset Sum into an instance \(\mathcal{I}\) of ILPF only uses a single constraint (i.e., \(|\operatorname{con}(\mathcal{I})|=1\)), it is immediate that ILPF is also **NP**-complete when \(\operatorname{td}_{D}(\mathcal{I})=1\); in other words, it is not possible to strengthen Theorem 8 by dropping any of the parameters. By the standard reduction from Subset Sum we mean the reduction to the ILP instance that has one binary variable for every integer in the Subset Sum instance (representing whether or not the integer is in a solution) and one constraint over all variables ensuring that the sum of all chosen integers equals the target value of the Subset Sum instance. The third fundamental graph representation that has been considered for restricting the variable-constraint interactions of an ILP instance \(\mathcal{I}\) is the incidence graph. It is worth noting that a trivial transformation of the respective decompositions yields \(\operatorname{td}_{I}(\mathcal{I})\leq\max(\operatorname{td}_{P}(\mathcal{I }),\operatorname{td}_{D}(\mathcal{I}))\) and similarly \(\operatorname{tw}_{I}(\mathcal{I})\leq\max(\operatorname{tw}_{P}(\mathcal{I }),\operatorname{tw}_{D}(\mathcal{I}))\); on the other hand, there are instances where both \(\operatorname{td}_{I}(\mathcal{I})\) and \(\operatorname{tw}_{I}(\mathcal{I})\) are bounded but the dual and primal graphs exhibit neither bounded treewidth nor treedepth. Hence, tractability results using the treewidth and treedepth of the incidence graph have the potential to supersede similar results for both previously considered graph representations, while any obtained hardness results carry over from primal and dual graphs to incidence graphs. [PERSON], [PERSON] and [PERSON] [40] identified conditions under which \(\operatorname{tw}_{I}(\mathcal{I})\) can be used to obtain algorithms for ILP.