# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 5 Other Parameters Exploiting Variable-Constraint Interactions  
Of course, ILP has also been studied through the lens of structural parameters that are different than treewidth. The first example of such a parameter is the _fracture number_ of [PERSON] et al. (2013), which captures the \"distance\" of an ILP instance from being fractured into small independent components. Three variants of the fracture number will be of interest for the purposes of this survey: the _constraint fracture number_ of an ILP \(\mathcal{I}\) (\(\text{frac}_{C}(\mathcal{I})\)) is the minimum number \(\ell\) of constraints that need to be deleted from \(\mathcal{I}\) so that the resulting instance \(\mathcal{I}^{\prime}\) satisfies the following: each connected component of \(G_{I}(\mathcal{I}^{\prime})\) contains at most \(\ell\) vertices. The _variable fracture number_ (\(\text{frac}_{V}(\mathcal{I})\)) and _mixed fracture number_ (\(\text{frac}(\mathcal{I})\)) are then defined analogously, with the distinction that we may only delete variables or are allowed to delete both variables and constraints, respectively. The constraint fracture number is bounded whenever the dual graph has bounded treedepth, and the mixed fracture number is bounded whenever the incidence graph has bounded treedepth (and similarily for the variables fracture number and the primal graph); however, the converse of these statements is not true. Intuitively, this means that the fracture number can be viewed as a stronger restriction than treedepth. [PERSON] et al. (2013) showed that the fracture number can be used to obtain XP-algorithms for ILP in settings which would remain **NP**-hard if treedepth were used instead (see Theorem 12). See Figure 3 for an illustration of the relationships between the different variants of fracture number as well as their relation to treewidth and treedepth. \begin{table}
\begin{tabular}{l c c c} \hline \hline \multicolumn{1}{c}{\multirow{2}{*}{**Acyclic Primal Graph**}} & \multicolumn{2}{c}{**Acyclic Incidence Graph**} \\ \cline{3-4}  & & **ILPF** & **ILP** \\ \hline Unary & **P** & **P** & **P** \\ Unary-C & **NP**-hard & **P** & **NP**-hard \\ Unary-D & **P** & **P** & **NP**-hard \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The complexity map for \(\text{ILP}_{\leq}\) for unary instances (first row), instances whose coefficients are encoded in unary (second row), and instances with unary bounded domain (third row). Without these restrictions, the problem becomes intractable due to the simple acyclic structure of the classical encoding of Subset Sum into ILP. Figure 3: The relationship between the structural parameters treewidth, treedepth, and fracture number for the primal, dual, and incidence graph. An arc from one parameter to another indicates that the former is a more general parameter, i.e., whenever the later is bounded so is the former. The variable, constraint, and mixed fracture number are defined in Section 5. **Theorem 14** (Corollary 8, [43]). : ILP _admits an \(\mathrm{XP}\)-algorithm parameterized by \(\|A\|_{\infty}+\mathrm{frac}(\mathcal{I})\)._  
**Theorem 15** (Theorem 12, [43]). : ILP _restricted to unary instances admits an \(\mathrm{XP}\)-algorithm parameterized by \(\mathrm{frac}_{C}(\mathcal{I})\)._  
Note that theorem 15 cannot be improved to an FPT-algorithm due to (Theorem 14, [43]). Moreover, an analogous result does not hold for the mixed respectively variable fracture number as already unary ILP is \(\mathbf{NP}\)-hard if the variable fracture number is bounded by a constant (Theorem 13, [43]), which also excludes the use of a less restrictive parameter than constraint fracture number (such as treedepth) in Theorem 15. Another structural parameter that can be used to solve ILP is the _torso-width_. The base idea behind torso-width is to decompose instances into (possibly many) separate parts with only limited interaction between them, and to solve some parts with [PERSON]'s algorithm (Theorem 1) and others with dynamic programming along a tree decomposition as per Theorem 5.