# Solution of Bin Packing Instances in Falkenauer T Class: Not So Hard
## 2 Illustration of Solving an Instance
### Graph Representation  
We can associate the colored table shown in Figure 1 with an edge-colored graph. The vertices are the B-items and C-items, each occurring once; in the present scenario, the vertex set is \(\{20,\ldots,60\}\setminus\{22\}\). Edge \((b,c)\) is labeled with color \(i\) if the entry in the \(b\)-th row and \(c\)-th column of Figure 1 is \(i\). In this way, an edge may have more than one color; for instance, the edge belonging to the item pair \((334,270)\) has both colors 16 and 17. In order to avoid double colors, we can introduce parallel edges. In our case, we take two edges connecting the vertices of items 334 and 270, assigning color 16 to one of those edges, and color 17 to the other.  
The graph under consideration has 40 vertices and 97 edges (108 nonzero entries, \(2\times 17\) of them in doubled columns, which yield 17 edges instead of 34, but 6 other entries have to be counted twice as they represent both colors 16 and 17), with an edge coloring that uses 20 colors. The top of Figure 2 shows the subgraph formed by the edges assigned to color 1 (blue) and color 2 (red). These two colors span a bipartite graph; we present this more convenient drawing. Let us note that it is not an induced subgraph because \((270,262)\) and \((275,257)\) are edges of color 3; moreover, the doubled \((275,260)\) is of color 4.  
A closely related alternative is to view the matrix representation as the adjacency matrix of a colored bipartite graph. We give an illustration at the bottom of Figure 2, namely the subgraph formed by the edges of colors 1 through 5. The isolated vertex 264 is  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**A-Item Index** & **A-Item Size** & \multicolumn{3}{c}{**Possible Pairs of B-Item and C-Item**} & \\ \hline
1 & 475 & (270,255) & (269,256) & (267,258) & (265,260) & (264,261) \\
2 & 473 & (275,252) & (270,257) & (269,258) & (267,260) & (265,262) \\
3 & 468 & (280,255)  
included with the intention to keep the vertex order in the column labeling unbroken, as given on the top of Figure 1. In the non-bipartite representation, the higher 265 and lower 265 vertices would be identical.  
Comparing the two parts of the figure, one can also observe that an increase in the number of colors may make the situation substantially more complicated.  
Recall from graph theory that a _perfect matching_ is a collection of mutually disjoint edges whose union is the entire vertex set. Moreover, \"rainbow subgraph\" in an edge-colored graph means a subgraph in which no color occurs more than once on the edges.  
**Observation 3**.: _Having fixed the \(A\)-items, the solutions of the scenario are in one-to-one correspondence with the rainbow perfect matchings of the associated graph._  
Figure 1: Matrix representation for the scenario involving \(a_{22}\).  
Proof.: A solution means that the set of B-items and C-items is split into pairs, and each pair is assigned to a distinct A-item. Denoting by \(G\) the associated graph, an item pair can form a good triplet with some A-item if and only if the corresponding vertex pair is an edge in \(G\). Hence, a partition of items into pairs such that each pair can be extended to a good triplet is equivalent to a perfect matching in \(G\). Finally, the \"rainbow\" condition means that distinct edges of a perfect matching are coupled with distinct A-items.  
In this way, searching for a solution of a given scenario is an instance of the rainbow matching search problem on graphs, which is also NP-hard, as discussed in Section 1.8.2.  
In the matrix representation. it means that we have an \(m_{1}\times m_{2}\) matrix with \(m_{1}\geq n\) rows and \(m_{2}\geq n\) columns, and entries of mutually distinct values have to be selected in such a way that no row or column contains more than one selected element. We shall refer to this task as the _colorful assignment_ problem.