Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem
Résumé
We consider the problem of coloring a grid using p 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 ⩾ 7 and p ⩾ 4 , respectively. The case p = 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 d 1 , d 2 in a complete bipartite graph K X , 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 d 1 + d 2 restricted to X or Y 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 k or k + 1 , for some integer k . In the present paper we prove an analog to Chen and Shastri’s characterization when d 1 + d 2 restricted to X and to Y has span at most two. That is, there exist integers k 1 and k 2 such that the sum of the number of occurrences of two of the colors in each row is k 1 − 1 , k 1 or k 1 + 1 , and in each column is k 2 − 1 , k 2 or k 2 + 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.