The 3-color tomography problem
The 3-color tomography problem is NP-hard, but this webpage aims to provide some intuition about the structure of the problem. The input are projections from the red and green cells. (Yellow cell projections are redundant). The input can either be entered in the form on the right, or generated by editing some grid coloring on the left.
When you submit the input, a linear pogram is generated, modeling the problem, and for every cell we use some solver to decide what colors the cell can have in a solution. Note: we only solve the relaxed linear program, where cells can have fractional colors, and therefore it is possible that the solver outputs something, while the instance is not feasible, i.e. the integer program has in fact no solution.
- example a: under some conditions on the projections, the grid can be divided into four parts, such that in any solution one part must be all red, and the opposite part must be free of any red.
- example b: more generaly, under some conditions the grid can be divided into 9 regions 11,12,13,21,22,23,31,32,33, such that in any solution the region 11 must be all yellow, the region 22 all red, the region 13 free of any red, and so on.
-
example 1: For E={(1,2), (1,3), (3,4)}, n=6, k=3. This is a simplified version of the instance produced by our reduction from Vertex Cover.
- example 2: when the source and the sink are fixed to the same pattern, all translators are fixed as well.
- example 3 When the source is fixed to a pattern a and the sink to a pattern b that dominates a, then the translators are not fixed anymore.
- example 4: but when a dominates b then there is no solution.
Input