Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem

We consider the problem of coloring a grid using pp colors with the requirement that each row and each column has a specific total number of entries of each color.Ryser (1957) [20], and independently Gale (1957) [10], obtained a necessary and sufficient condition for the existence of such a coloring when two colors are considered. This characterization yields a linear-time algorithm for constructing the coloring when it exists. Later, Gardner et al. (2000) [11], and Chrobak and Dürr (2001) [5], showed that the problem is NP-hard when p⩾7p⩾7 and p⩾4p⩾4, respectively.The case p=3p=3 was an open problem for several years and has been recently settled by Dürr et al. (2009) [9]: it is NP-hard too. This grid coloring problem is equivalent to finding disjoint realizations of two degree sequences d1,d2d1,d2 in a complete bipartite graph KX,YKX,Y. These kinds of questions are well studied when one of the degree sequences has span zero or one, where the span of a function is the difference between its maximum and its minimum values. In [4], Chen and Shastri (1989) showed a necessary and sufficient condition for the existence of a coloring when d1+d2d1+d2 restricted to XX or YY has span at most one. In terms of discrete tomography this latter condition means that for two colors, the sum of the number of occurrences of these colors in each row is kk or k+1k+1, for some integer kk.In the present paper we prove an analog to Chen and Shastri’s characterization when d1+d2d1+d2 restricted to XX and to YY has span at most two. That is, there exist integers k1k1 and k2k2 such that the sum of the number of occurrences of two of the colors in each row is k1−1,k1k1−1,k1 or k1+1k1+1, and in each column is k2−1,k2k2−1,k2 or k2+1k2+1. Our characterization relies on a new natural condition called the total saturation condition which, when not satisfied, gives a non-existence certificate of such a coloring that can be checked in polynomial time.