Obtaining Matrices with the Consecutive Ones Property by Row Deletions

详细信息    查看全文

• 作者：N. S. Narayanaswamy (1)
  R. Subashini (1)
  
  1. Department of Computer Science and Engineering ; Indian Institute of Technology Madras ; Chennai ; India
  
• 关键词：Consecutive ones property ; Consecutive ones submatrix ; Parameterized complexity
• 刊名：Algorithmica
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：71
• 期：3
• 页码：758-773
• 全文大小：295 KB
• 参考文献：1. Atkins, JE, Boman, EG, Hendrickson, B (1988) A spectral algorithm for seriation and the consecutive ones problem. SIAM J. Comput. 28: pp. 297-310 k" title="It opens in new window">CrossRef
  2. Atkins, JE, Middendorf, M (1996) On physical mapping and the consecutive ones property for sparse matrices. Discrete Appl Math 71: pp. 23-40 k" title="It opens in new window">CrossRef
  3. Blin, G, Rizzi, R, Vialette, S (2012) A faster algorithm for finding minimum tucker submatrices. Theory Comput. Syst. 51: pp. 270-281 k" title="It opens in new window">CrossRef
  4. Booth, K.S.: PQ-tree algorithms. Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley (1975)
  5. Booth, KS, Lueker, GS (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13: pp. 335-379 k" title="It opens in new window">CrossRef
  6. Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. pp. 122鈥?41. SIAM (2014)
  7. Chen, J, Kanj, IA, Xia, G (2010) Improved upper bounds for vertex cover. Theor. Comput. Sci. 411: pp. 3736-3756 k" title="It opens in new window">CrossRef
  8. Dom, M.: Recognition, generation, and application of binary matrices with the consecutive-ones property. Ph.D. thesis, Institut fur Informatik, Friedrich-Schiller-Universitat Jena, Germany, 2008, Published by Cuvillier (2010)
  9. Dom, M, Guo, J, Niedermeier, R (2010) Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. J. Comput. Syst. Sci. 76: pp. 204-221 k" title="It opens in new window">CrossRef
  10. Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Computational aspects of the helly property: a survey. J. Braz. Comput. Soc. 12(1), 7鈥?3 (2006)
  11. Fulkerson, DR, Gross, OA (1965) Incidence matrices and interval graphs. Pac. J. Math. 15: pp. 835-855 k" title="It opens in new window">CrossRef
  12. Garey, MR, Johnson, DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, London
  13. Garey, MR, Johnson, DS, Stockmeyer, LJ (1976) Some simplified NP-Complete graph problems. Theor. Comput. Sci. 1: pp. 237-267 k" title="It opens in new window">CrossRef
  14. Ghosh, SP (1972) File organization: The consecutive retrieval property. Commun. ACM 15: pp. 802-808 k" title="It opens in new window">CrossRef
  15. Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Volume 57 of Annals of Discrete Mathematics. Elsevier B. V., 2nd edition (2004).
  16. Golumbic, MC, Kaplan, H, Shamir, R (1994) On the complexity of DNA physical mapping. Adv. Appl. Math. 15: pp. 251-261 k" title="It opens in new window">CrossRef
  17. Habib, M, McConnell, RM, Paul, C, Viennot, L (2000) Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234: pp. 59-84 k" title="It opens in new window">CrossRef
  18. Hajiaghayi, M, Ganjali, Y (2002) A note on the consecutive ones submatrix problem. Inform. Process. Lett. 83: pp. 163-166 k" title="It opens in new window">CrossRef
  19. Hochbaum, DS (1997) Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston
  20. Hsu, WL (2002) A simple test for the consecutive ones property. J. Algorithm. 43: pp. 1-16 k" title="It opens in new window">CrossRef
  21. Hsu, WL, McConnell, RM (2003) PC-trees and circular-ones arrangements. Theor. Comput. Sci. 296: pp. 99-116 k" title="It opens in new window">CrossRef
  22. Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219鈥?30 (1980)
  23. Lindzey, N, McConnell, RM On finding tucker submatrices and lekkerkerker-boland subgraphs. In: Brandst盲dt, A, Jansen, K, Reischuk, R eds. (2013) WG. Lecture Notes in Computer Science. Springer, Berlin, pp. 345-357
  24. McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: J. Ian Munro (ed.) Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, SODA. pp. 768鈥?77 (2004)
  25. Meidanis, J, Porto, O, Telles, GP (1998) On the consecutive ones property. Discrete Appl. Math. 88: pp. 325-354 k" title="It opens in new window">CrossRef
  26. Narayansaswamy, NS, Subashini, R (2009) A new characterization of matrices with the consecutive ones property. Discrete Appl. Math. 157: pp. 3721-3727 k" title="It opens in new window">CrossRef
  27. Narayansaswamy, NS, Subashini, R FPT algorithms for consecutive ones submatrix problems. In: Gutin, Gregory, Szeider, Stefan eds. (2013) IPEC. Lecture Notes in Computer Science. Springer, Berlin, pp. 295-307
  28. Raffinot, M Consecutive ones property testing: cut or swap. In: L枚we, B, Normann, D, Soskov, IN, Soskova, AA eds. (2011) CiE. Lecture Notes in Computer Science. Springer, Berlin, pp. 239-249
  29. Robinson, WS (1951) A method for chronologically ordering archaeological deposits. Am. Antiq. 16: pp. 293-301 k" title="It opens in new window">CrossRef
  30. Khot, S, Regev, O (2008) Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74: pp. 335-349 k" title="It opens in new window">CrossRef
  31. Tan, J, Zhang, L (2007) The consecutive ones submatrix problem for sparse matrices. Algorithmica 48: pp. 287-299 k" title="It opens in new window">CrossRef
  32. Tucker, AC (1972) A structure theorem for the consecutive ones property. Journal of Combinatorial Theory. Series B 12: pp. 153-162 k" title="It opens in new window">CrossRef
  33. Wang, R, Lau, FCM, Zhao, YC (2007) Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices. Discrete Appl. Math. 155: pp. 2312-2320 k" title="It opens in new window">CrossRef
  34. West, D.B.: Introduction to graph theory. Second edition, Prentice Hall (2001)
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

A binary matrix \(M\) has the Consecutive Ones Property (COP) if there exists a permutation of columns that arranges the ones consecutively in all the rows. We consider the parameterized complexity of \(d\) -COS-R (Consecutive Ones Submatrix by Row deletions) problem [9]: Given a matrix \(M\) and a positive integer \(d\) , decide whether there exists a set of at most \(d\) rows of \(M\) whose deletion results in a matrix with the COP. The closely related Interval Deletion problem has recently been shown to be FPT [6]. We show that \(d\) -COS-R is fixed-parameter tractable and has the current best run-time of \(O^*(10^d)\) , which is associated with the Interval Deletion problem. We also introduce a closely related optimization problem called Min-ICPSA: For a finite sized universe \(\mathcal{U}\) the input consists of a family of \(n\) pairs of sets \(\mathcal{S} = \{(A_i,B_i) \mid A_i, B_i \subseteq \mathcal{U}, 1 \le i \le n\}\) ; the aim is to find a minimum number of pairs of sets to discard from \(\mathcal{S}\) such that for each one of the remaining pairs, say \((A_k,B_k), |A_k|=|B_k|\) , and for any two of the remaining pairs, indexed by \(1 \le j \ne k \le n\) , \(|A_j \cap A_k| = |B_j \cap B_k|\) . We show that Min-ICPSA is computationally equivalent to the Vertex Cover problem. We also show that it is at least as hard as the Hamilton Path problem in undirected graphs, even when each \(|A_k|=2, 1 \le k \le n\) .