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 : https://doi.org/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},
     zbl = {1110.68049},
     mrnumber = {2277046},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2006037/}
}
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://www.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 0329.05118

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

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

[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 0928.68057

[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 0974.68148

[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 1743598 | Zbl 0945.05002

[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 519066 | Zbl 0411.68039

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

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

[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 562306 | Zbl 0541.05054

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

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

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

[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 1672910 | Zbl 0945.05003

[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 0624.68059

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

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

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

[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 0879.05022