# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 2 Preliminaries
### Graph Parameters  
Treewidth.Treewidth is the most prominent structural parameter and has been extensively studied in a number of fields. In order to define treewidth, we begin with the definition of its associated decomposition. A _tree-decomposition_\(\mathcal{T}\) of a graph \(G=(V,E)\) is a pair \((T,\chi)\), where \(T\) is a tree and \(\chi\) is a function that assigns each tree node \(t\) a set \(\chi(t)\subseteq V\) of vertices such that the following conditions hold:  
1. For every edge \(\{u,v\}\in E(G)\) there is a tree node \(t\) such that \(u,v\in\chi(t)\). 2. For every vertex \(v\in V(G)\), the set of tree nodes \(t\) with \(v\in\chi(t)\) forms a non-empty subtree of \(T\). The sets \(\chi(t)\) are called _bags_ of the decomposition \(\mathcal{T}\) and \(\chi(t)\) is the bag associated with the tree node \(t\). The _width_ of a tree-decomposition \((T,\chi)\) is the size of a largest bag minus \(1\). A tree-decomposition of minimum width is called _optimal_. The _treewidth_ of a graph \(G\), denoted by \(\operatorname{tw}(G)\), is the width of an optimal tree decomposition of \(G\). **Proposition 1** ([18; 19; 20]). : _It is possible to compute an optimal tree-decomposition of an \(n\)-vertex graph \(G\) with treewidth \(k\) in time \(k^{\mathcal{O}(k^{3})}n\), and to compute a \(5\)-approximate one in time \(2^{\mathcal{O}(k)}n\). Moreover, the number of nodes in the obtained tree decompositions is at most \(\mathcal{O}(n)\)._Treedepth.Another important notion that we make use of extensively is that of treedepth. Treedepth is a structural parameter closely related to treewidth, and the structure of graphs of bounded treedepth is well understood [21]. A useful way of thinking about graphs of bounded treedepth is that they are (sparse) graphs with no long paths. We formalize a few notions needed to define treedepth. A _rooted forest_ is a disjoint union of rooted trees. For a vertex \(x\) in a tree \(T\) of a rooted forest, the _height_ (or _depth_) of \(x\) in the forest is the number of vertices in the path from the root of \(T\) to \(x\). The _height of a rooted forest_ is the maximum height of a vertex of the forest. Definition 1 (Treedepth): Let the _closure_ of a rooted forest \(\mathcal{F}\) be the graph \(\text{clos}(\mathcal{F})=(V_{c},E_{c})\) with the vertex set \(V_{c}=\bigcup_{T\in\mathcal{F}}V(T)\) and the edge set \(E_{c}=\{xy\colon x\text{ is an ancestor of }y\text{ in some }T\in\mathcal{F}\}\). A _treedepth decomposition_ of a graph \(G\) is a rooted forest \(\mathcal{F}\) such that \(G\subseteq\text{clos}(\mathcal{F})\). The _treedepth \(\text{td}(G)\)_ of a graph \(G\) is the minimum height of any treedepth decomposition of \(G\). We will later use \(T_{x}\) to denote the vertex set of the subtree of \(T\) rooted at a vertex \(x\) of \(T\). Similarly to treewidth, it is possible to determine the treedepth of a graph in FPT time. Proposition 2 ([21]): _Given a graph \(G\) with \(n\) nodes and a constant \(w\), it is possible to decide whether \(G\) has treedepth at most \(w\), and if so, to compute an optimal treedepth decomposition of \(G\) in time \(\mathcal{O}n\)._  
The following alternative (equivalent) characterization of treedepth will be useful later. Proposition 3 ([21]): _Let \(G_{i}\) be the connected components of \(G\). Then_  
\[\text{td}(G)= \begin{cases}1,&\text{if }|V(G)|=1;\\ 1+\min_{v\in V(G)}td(G-v),&\text{if }G\text{ is connected and }|V(G)|>1;\\ \max_{i}td(G_{i}),&\text{otherwise.}\end{cases} \]  
We conclude with a few useful facts about treedepth. Proposition 4 ([21]): _If a graph \(G\) has no path of length \(d\), then \(\text{td}(G)\leq d\)._  
_If \(\text{td}(G)\leq d\), then \(G\) has no path of length \(2^{d}\)._  
\(\text{tw}(G)\leq\text{td}(G)\)_._  
_If \(\text{td}(G)\leq d\), then \(\text{td}(G^{\prime})\leq d+1\) for any graph \(G^{\prime}\) obtained by adding one vertex into \(G\)._  
(Signed) Clique-width.Let \(k\) be a positive integer.