Skip to main content
SpringerLink
Log in

FPT Algorithms for Consecutive Ones Submatrix Problems

  • Conference paper
Parameterized and Exact Computation (IPEC 2013)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 8246))

Included in the following conference series:

  • 940 Accesses

Abstract

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 [8]: 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 [5]. In this work, we describe a recursive depth-bounded search tree algorithm in which the problems at the leaf-level of the recursion tree are solved as instances of Interval Deletion. Therefore, we show that d-COS-R is fixed-parameter tractable and has the current best run-time of O *(10d), which is associated with the Interval Deletion problem. We then consider a closely related optimization problem, called Min-ICPIA, and prove that it is computationally equivalent to the Vertex Cover problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
Â¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Atkins, J.E., Boman, E.G., Hendrickson, B.: A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing 28(1), 297–310 (1988)

    Article  MathSciNet  Google Scholar 

  2. Blin, G., Rizzi, R., Vialette, S.: A faster algorithm for finding minimum tucker submatrices. Theory of Computing Systems 51(3), 270–281 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  3. Booth, K.S.: PQ-tree algorithms. Ph.D. thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA (1975)

    Google Scholar 

  4. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13(3), 335–379 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. arXiv:1211.5933v2(cs.DS) (2013)

    Google Scholar 

  6. Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science 411(40-42), 3736–3756 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dom, M.: Recognition, generation, and application of binary matrices with the consecutive-ones property. Ph.D. thesis, Institut fur Informatik, Friedrich-Schiller-Universitat (2008)

    Google Scholar 

  8. Dom, M., Guo, J., Niedermeier, R.: Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. Journal of Computing System Sciences 76(3-4), 204–221 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Computational aspects of the Helly property: a survey. Journal of the Brazilian Computer Society 12(1), 7–33 (2006)

    MathSciNet  Google Scholar 

  10. Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics 15(3), 835–855 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  11. Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman (1979)

    Google Scholar 

  12. Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47–63 (1974)

    Google Scholar 

  13. Ghosh, S.P.: File organization: The consecutive retrieval property. Communications of the ACM 15(9), 802–808 (1972)

    Article  MATH  Google Scholar 

  14. Golumbic, M.C.: Algorithmic graph theory and perfect graphs, 2nd edn. Annals of Discrete Mathematics, vol. 57. Elsevier B.V. (2004)

    Google Scholar 

  15. Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science 234(1-2), 59–84 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hajiaghayi, M., Ganjali, Y.: A note on the consecutive ones submatrix problem. Information Processing Letters 83(3), 163–166 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hochbaum, D.S.: Approximation algorithms for NP-hard problems. PWS Publishing Company (1997)

    Google Scholar 

  18. Hsu, W.L.: PC-trees vs. PQ-trees. In: Wang, J. (ed.) COCOON 2001. LNCS, vol. 2108, pp. 207–217. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  19. Hsu, W.L.: A simple test for the consecutive ones property. Journal of Algorithms 43(1), 1–16 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  20. Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-Complete. Journal of Computer and System Sciences 20(2), 219–230 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  21. McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 768–777 (2004)

    Google Scholar 

  22. Meidanis, J., Porto, O., Telles, G.P.: On the consecutive ones property. Discrete Applied Mathematics 88(1-3), 325–354 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  23. Narayansaswamy, N.S., Subashini, R.: A new characterization of matrices with the consecutive ones property. Discrete Applied Mathematics 157, 3721–3727 (2009)

    Article  MathSciNet  Google Scholar 

  24. Raffinot, M.: Consecutive ones property testing: cut or swap. In: Models of Computation in Context - 7th Conference on Computability in Europe, pp. 239–249 (2011)

    Google Scholar 

  25. Robinson, W.S.: A method for chronologically ordering archaeological deposits. American Antiquity 16(4), 293–301 (1951)

    Article  Google Scholar 

  26. Tan, J., Zhang, L.: The consecutive ones submatrix problem for sparse matrices. Algorithmica 48(3), 287–299 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  27. Tucker, A.C.: A structure theorem for the consecutive ones property. Journal of Combinatorial Theory. Series B 12, 153–162 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  28. Wang, R., Lau, F.C.M., Zhao, Y.C.: Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices. Discrete Applied Mathematics 155(17), 2312–2320 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  29. West, D.B.: Introduction to graph theory, 2nd edn. Prentice Hall (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology Madras, India

    N. S. Narayanaswamy & R. Subashini

Authors
  1. N. S. Narayanaswamy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Subashini
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Royal Holloway, University of London, Egham Hill, TW20 0EX, Egham, UK

    Gregory Gutin

  2. Institute of Information Systems, Vienna University of Technology, (184/3), Favoritenstraße 9-11, 1040, Vienna, Austria

    Stefan Szeider

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer International Publishing Switzerland

About this paper

Cite this paper

Narayanaswamy, N.S., Subashini, R. (2013). FPT Algorithms for Consecutive Ones Submatrix Problems. In: Gutin, G., Szeider, S. (eds) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol 8246. Springer, Cham. https://doi.org/10.1007/978-3-319-03898-8_25

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-03898-8_25

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-03897-1

  • Online ISBN: 978-3-319-03898-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation