# Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
## 2 Preliminaries
### Graph Parameters
A \(k\)-graph is a graph whose vertices are labeled by \([k]\); formally, the graph is equipped with a labeling function \(\gamma\colon V(G)\to[k]\), and we also use \(\gamma^{-1}(i)\) to denote the set of vertices labeled \(i\) for \(i\in[k]\). We consider an arbitrary graph as a \(k\)-graph with all vertices labeled by \(1\). We call the \(k\)-graph consisting of exactly one vertex \(v\) (say, labeled by \(i\)) an initial \(k\)-graph and denote it by \(i(v)\). The _clique-width_ of a graph \(G\) is the smallest integer \(k\) such that \(G\) can be constructed from initial \(k\)-graphs by means of repeated application of the following three operations:  
1. Disjoint union (denoted by \(\oplus\));
2. Relabeling: changing all labels \(i\) to \(j\) (denoted by \(p_{i\to j}\));
3. Edge insertion: adding an edge between each vertex labeled by \(i\) and each vertex labeled by \(j\), where \(i\
eq j\) (denoted by \(\eta_{i,j}\) or \(\eta_{j,i}\)). A construction of a \(k\)-graph \(G\) using the above operations can be represented by an algebraic term composed of \(\oplus\), \(p_{i\to j}\) and \(\eta_{i,j}\) (where \(i\
eq j\) and \(i,j\in[k]\)). Such a term is called a \(k\)-expression defining \(G\), and the _clique-width_ of \(G\) is the smallest integer \(k\) such that \(G\) can be defined by a \(k\)-expression. A _k-expression tree_ (also called parse trees in the literature [22]) is a rooted tree representation of a _k_-expression; specifically, the _k_-expression tree can be built from a _k_-expression in a leaves-to-root fashion by using a leaf to represent each \(i(v)\), each \(\oplus\) operator is represented by an \(\oplus\) node with two children, and each \(p_{i\to j}\) and \(\eta_{j,j}\) operator is represented by a corresponding node with a single child. There are many graph classes which are known to have bounded clique-width. Examples of such graph classes include every graph class of bounded treewidth [23], co-graphs [23], complete (bipartite) graphs and distance hereditary graphs [24]. If the edges of \(G\) have signs, then one can define two different variants of clique-width for \(G\). The _unsigned clique-width_ of \(G\) is simply the clique-width of the graph \(G^{\prime}\) obtained by removing all signs on the edges of \(G\). On the other hand, the _signed clique-width_ of \(G\) is the minimum \(k\) such that \(G\) can be defined by a _signed k-expression_, which is analogous to a _k_-expression with the sole distinction that the operation \(\eta_{i,j}\) is replaced by \(\eta_{i,j}^{\ell}\) which adds an edge with sign \(\ell\) between all vertices labeled \(i\) and \(j\). An example is provided in Figure 1.  
We list a few known facts and observations about clique-width below:  
* The difference between the signed clique-width (scw) and unsigned clique-width (cw) of a signed graph \(G\) can be arbitrarily large; more precisely, for every gap \(g\) there exists a signed graph \(G\) such that \(\operatorname{scw}(G)\geq\operatorname{cw}(G)+g\)[25]. * There exists a function \(f\) and a polynomial-time algorithm which takes as input a (signed) graph \(G\) and either outputs a (signed) \(f(k)\)-expression or correctly determines that the (signed) clique-width of \(G\) is greater than \(k\)[26; 27]. * Every signed graph of (signed) clique-width \(k\) can be defined by a (signed) \(k\)-expression which does not use the \(\eta_{i,j}\) operator to create edges between vertices that are already adjacent (i.e., each edge is created only once). * A signed \(k\)-expression of a bipartite signed graph \(G\) with bi-partition \(V_{1}\), \(V_{2}\) can be converted to a signed \((k+1)\)-expression of \(G\) such that the labels used for \(V_{1}\) are completely disjoint from those used for \(V_{2}\) (this is because any label that was originally used for \(V_{1}\) and \(V_{2}\) cannot be used to create new edges).