Packing of (0, 1)-matrices
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 519-535.

The MATRIX PACKING DOWN problem asks to find a row permutation of a given (0,1)-matrix in such a way that the total sum of the first non-zero column indexes is maximized. We study the computational complexity of this problem. We prove that the MATRIX PACKING DOWN problem is NP-complete even when restricted to zero trace symmetric (0,1)-matrices or to (0,1)-matrices with at most two 1’s per column. Also, as intermediate results, we introduce several new simple graph layout problems which are proved to be NP-complete.

DOI : 10.1051/ita:2006037
Classification : 68Q17, 68Q25
Mots-clés : NP-hardness, $(0,1)$-matrix 
@article{ITA_2006__40_4_519_0,
     author = {Vialette, St\'ephane},
     title = {Packing of (0, 1)-matrices},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {519--535},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {4},
     year = {2006},
     doi = {10.1051/ita:2006037},
     mrnumber = {2277046},
     zbl = {1110.68049},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2006037/}
}
TY  - JOUR
AU  - Vialette, Stéphane
TI  - Packing of (0, 1)-matrices
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 519
EP  - 535
VL  - 40
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2006037/
DO  - 10.1051/ita:2006037
LA  - en
ID  - ITA_2006__40_4_519_0
ER  - 
%0 Journal Article
%A Vialette, Stéphane
%T Packing of (0, 1)-matrices
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 519-535
%V 40
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2006037/
%R 10.1051/ita:2006037
%G en
%F ITA_2006__40_4_519_0
Vialette, Stéphane. Packing of (0, 1)-matrices. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 4, pp. 519-535. doi : 10.1051/ita:2006037. http://archive.numdam.org/articles/10.1051/ita:2006037/

[1] C. Berge, Perfect graphs, in Studies in graph theory, edited by D.R. Fulkerson. Washington D.C., Math. Assoc. Amer. (1975) 1-22. | Zbl

[2] A. Brandstädt, V. Bang Le and J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (1999). | MR | Zbl

[3] R.A. Brualdi and H.J. Ryser, Combinatorial Matrix Theory. Cambridge University Press, New York (1991). | MR | Zbl

[4] B. Dasgupta, T. Jiang, S. Kannan, M. Li and E. Sweedyk, On the complexity and approximation of syntenic distance. Discrete Appl. Math. 88 (1998) 59-82. | Zbl

[5] J. Dìaz, M.D. Penrose, J. Petit and M. Serna, Approximating layout problems on random geometric graphs. J. Algorithms 39 (2001) 78-116. | Zbl

[6] J. Dìaz, J. Petit and M. Serna, A survey on graph layout problems. ACM Comput. Surveys 34 (2002) 313-356.

[7] R. Diestel, Graph theory. Number 173 in Graduate texts in Mathematics. Springer-Verlag, second edition (2000). | MR | Zbl

[8] S. Even and Y. Shiloach, NP-completeness of several arrangement problems. Technical Report TR-43, Dept. of Computer Science, Haifa (1975).

[9] M.R. Garey and D.S. Johnson, Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Franciso (1979). | MR | Zbl

[10] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems. Theor. Comput. Sci. 1 (1976) 237-267. | Zbl

[11] F. Gavril, The intersection graphs of subtrees are exactly the chordal graphs. J. Combin. Theory Ser. B 16 (1974) 47-56. | Zbl

[12] F. Gavril, Some NP-complete problems on graphs, in Proc. of the 11th Conference on Information Sciences and Systems, John Hopkins University, Baltimore (1977) 91-95.

[13] P.W. Goldberg, M.C. Golumbic, H. Kaplan and R. Shamir, Four strikes against physical mapping of dna. J. Comput. Biology 2 (1995) 139-152.

[14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). | MR | Zbl

[15] W.W. Hager, Minimizing the profile of a symmetric matrix. SIAM J. Scientific Comput. 23 (2002) 1799-1816. | Zbl

[16] P.L. Hammer and S. Foldes, Split graphs. Congr. Numer. 19 (1997) 311-315. | Zbl

[17] M. Juvan and B. Mohar, Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36 (1992) 153-168. | Zbl

[18] B. Kumar, P. Sadayappan and C.-H. Huang, On sparse matrix reordering for parallel factorization, in International Conference on Supercomputing (1994) 431-438.

[19] T.A. Mckee and F.R. Mcmorris, Topics in intersection graph theory. SIAM Monogr. Discrete Math. Appl. (1999). | MR | Zbl

[20] B. Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods 7 (1986) 505-512. | Zbl

[21] B. Monien and I.H. Sudborough, Min Cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58 (1988) 209-229. | Zbl

[22] C.H. Papadimitriou, The NP-completness of the bandwidth minimization problem. Computing 16 (1976) 263-270. | Zbl

[23] Y. Shiloach, A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 30 (1979) 1173-1789. | Zbl

[24] H.S. Wilf, On crossing numbers, and some unsolved problems, in Combinatorics, Geometry and Probability: A Tribute to Paul Erdös, edited by B. Bollobás and A. Thomason, Cambridge University Press (1997) 557-562. | Zbl

Cité par Sources :