# Star Bicolouring of Bipartite Graphs
## 4 Column Generation--Pricing Problem  
[PERSON] and [PERSON] [20] proposed a column generation technique to solve problems with a large number of variables/columns. The column generation algorithm is effective when the columns corresponding to variables are combinatorial objects such as cycles, tours, paths, and subtrees. The idea is to start with a few columns that give a feasible solution that is not necessarily optimal. The primal with a small number of columns is known as the restricted master problem (RMP). A new column is generated by solving a pricing subproblem instead of searching for possible columns not present in the RMP. The addition of the new column (with a negative reduced cost) improves the value of the solution to the primal problem. The pricing subproblem is an optimisation problem. At times, it is a linear programming problem [21]. The pricing subproblem aims to find a column with a negative reduced cost. This is similar to the pricing step of the simplex method for finding a nonbasic variable with a negative reduced cost. If the minimum reduced cost is non-negative, the algorithm halts; otherwise, the new column is added to the restricted master problem, and the process iterates.  
The goal of the pricing problem is to find a new column for the LP that, when added to the current solution, will reduce the objective function value. In this case, the pricing problem is formulated as an integer linear program (ILP). This ILP seeks to find a new set of vertices to colour with a single colour that satisfies the star bicolouring constraints and that has a negative reduced cost.  
We compute \(\chi_{fs}\) by introducing columns with negative reduced costs in the basis one at a time. The column insertion/exchange process is implicit in the simplex method. It was noted by [PERSON] and [PERSON] that a separate optimization problem (the pricing problem) can be solved to determine the column with a negative reduced cost [21]. Let \(r,c\) be the size of the two partitions, and let \(p=|P|\) be the number of paths in the bipartite graph. Then, a column \(C\) of incidence matrix is a \(0/1\) vector of length \(r+c+p\). First, \(r+c\) components of \(C\) correspond to vertices. They identify the subset of vertices \(s\) that are assigned the same colour. There are two entries \(i,j\) such that \(1\leq i\leq r\) and \(r+1\leq j\leq r+c\) cannot simultaneously be \(1\). Otherwise, the two sides share a colour. The remaining \(p\) entries in the column indicate whether path \(P_{i}\) contains one of the nodes in the set \(s\). Let \(\pi\) be the vector of dual values to the LP relaxation above. The pricing problem can now be cast as the following ILP. \(P_{i}\) refers to the \(i^{th}\) path below.  
\[\max \sum_{i=1}^{r+c+p}\pi_{i}x_{i} \tag{2}\] \[x_{i}+x_{j}\leq 1 \forall i\in[1\ldots r],j\in[r+1\ldots r+c]\] (3) \[x_{r+c+i}\leq\sum_{j\in P_{i}}x_{j} \forall i\in[1\ldots p]\] (4) \[x_{j}\leq x_{r+c+i} \forall j\in P_{i}\] (5) \[x_{i}\in\{0,1\} \forall i\in[1\ldots r+c+p] \tag{6}\]  
If the optimal solution \(x^{*}\) to the ILP above has a value strictly larger than 1, then introducing a column, given by the optimal solution to the pricing problem, in the existing basis will lead to an improved solution for the master problem.