Reconstructing a Matrix with a Given List of Coefficients and Prescribed Row and Column Sums Is NP-Hard
We investigate a natural generalization of the problem of reconstruction of a binary matrix A with prescribed row and column sums: we consider an integer matrix whose list of coefficients is given in the input. The question is to organize the coefficients
- PDF / 173,569 Bytes
- 9 Pages / 430 x 660 pts Page_size
- 22 Downloads / 153 Views
bstract. We investigate a natural generalization of the problem of reconstruction of a binary matrix A with prescribed row and column sums: we consider an integer matrix whose list of coefficients is given in the input. The question is to organize the coefficients in the matrix in order to obtain prescribed row and column sums. We prove that this problem is NP-complete by reducing it to a 2D problem of Discrete Tomography with 3 directions of projections. Keywords: discrete NP-completeness.
1
tomography,
combinatorial
matrix
theory,
Introduction
Reconstruction of binary matrices with prescribed line sums is a subject which has drawn attention of many mathematicians and computer scientists since the fifties. The initial problem was the reconstruction of a binary matrix with prescribed row and column sums. We call it for short Gale-Ryser problem from the name of the two pioneers which have both and independently discovered in 1957 that the question can be solved in polynomial time [5,12]. This result is the starting point of many generalizations which have been considered in combinatorial frameworks (Time-Table problems [4,10], Combinatorial Matrix Theory[1]...) or under pression of Electronic Microscopy, Medical Imaging (Discrete Tomography [9,6]...). Most of these generalizations are known today as NP-hard. Some of these complexities remain open problems such as for instance the multi-atomic problem of reconstruction with 3 kinds of atoms [7,3]. We consider in this paper a new generalization in relation with Combinatorial Matrix Theory or Tomography. The input is made of a row sum vector R, a column sum vector S and an initial integer matrix X0 . The question is to permute the coefficients of X0 in order to obtain a matrix X with the prescribed line sums R and S. If we consider an initial matrix X0 with only binary coefficients, we fall in the well-known framework of initial Gale-Ryser problem. With coefficients which are just assumed to be integers, the problem becomes more complicated. As the coefficients are not restricted to {0, 1}, we can consider matrices X0 V.E. Brimkov, R.P. Barneva, H.A. Hauptman (Eds.): IWCIA 2008, LNCS 4958, pp. 363–371, 2008. c Springer-Verlag Berlin Heidelberg 2008
364
Y. Gerard
and X as gray-levels images. In this framework, the problem is to permute the pixels of an image in order to obtain prescribed row and column sums. It places the problem on the boundary of Discrete Tomography (the set of the coefficients remains discrete since it is finite) and Computerized Tomography since we can work with any gray-level image. We are also clearly in the framework of Combinatorial Image Theory or again Combinatorial Matrix Theory. This last field provides an interpretation of our problem in terms of flows in a bipartite graph: imagine that ri passengers are waiting in m airports (1 ≤ i ≤ m) and that a flight supervisor has the mission to send them in n other airports. sj (with 1 ≤ j ≤ n) passengers exactly are waited in the arrival airport j (without taking account of their origin). The aircraft isma
Data Loading...
