 On the positive side, the problem is solvable in polynomial time on bipartite domino-free graphs .Regarding the existence of approximation algorithms, proved that the problem cannot be approximated well (assuming P ≠ NP).Indeed, the bipartite dimension is NP-hard to approximate within formula_31 for every fixed formula_32, already for bipartite graphs .