Document Open Access Logo

Covering Vectors by Spaces: Regular Matroids

Authors Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.56.pdf
  • Filesize: 492 kB
  • 15 pages

Document Identifiers

Author Details

Fedor V. Fomin
Petr A. Golovach
Daniel Lokshtanov
Saket Saurabh

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Covering Vectors by Spaces: Regular Matroids. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.56

Abstract

We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, we study the Space Cover problem, where we are given a matrix M and a subset of its columns T; the task is to find a minimum set F of columns of M disjoint with T such that that the linear span of F contains all vectors of T. This is a fundamental problem arising in different domains, such as coding theory, machine learning, and graph algorithms. 
 
We give a parameterized algorithm with running time 2^{O(k)}||M|| ^{O(1)} solving this problem in the case when M is a totally unimodular matrix over rationals, where k is the size of F. In other words, we show that the problem is fixed-parameter tractable parameterized by the rank of the covering subspace. The algorithm is "asymptotically optimal" for the following reasons.

Choice of matrices: Vector matroids corresponding to totally unimodular matrices over rationals are exactly the regular matroids. It is known that for matrices corresponding to a more general class of matroids, namely, binary matroids, the problem becomes W[1]-hard being parameterized by k.

Choice of the parameter: The problem is NP-hard even if |T|=3 on matrix-representations of a subclass of regular matroids, namely cographic matroids. Thus for a stronger parameterization, like by the size of T, the problem becomes intractable. 

Running Time: The exponential dependence in the running time of our algorithm cannot be asymptotically improved unless Exponential Time Hypothesis (ETH) fails. 

Our algorithm exploits the classical decomposition theorem of Seymour for regular matroids.

Subject Classification

Keywords
  • regular matroids
  • spanning set
  • parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, Pranabendu Misra, M. S. Ramanujan, and Saket Saurabh. Parameterized algorithms to preserve connectivity. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 800-811. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_66.
  2. Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Information Theory, 24(3):384-386, 1978. URL: http://dx.doi.org/10.1109/TIT.1978.1055873.
  3. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 67-74. ACM, 2007. Google Scholar
  4. Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, and Srinath Sridhar. Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction. In Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I, volume 4051 of Lecture Notes in Computer Science, pages 667-678. Springer, 2006. URL: http://dx.doi.org/10.1007/11786986_58.
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  6. Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864-894, 1994. URL: http://dx.doi.org/10.1137/S0097539792225297.
  7. Michael Dinitz and Guy Kortsarz. Matroid secretary for regular and decomposable matroids. SIAM J. Comput., 43(5):1807-1830, 2014. URL: http://dx.doi.org/10.1137/13094030X.
  8. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  9. Rodney G. Downey, Michael R. Fellows, Alexander Vardy, and Geoff Whittle. The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput., 29(2):545-570, 1999. URL: http://dx.doi.org/10.1137/S0097539797323571.
  10. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: http://dx.doi.org/10.1002/net.3230010302.
  11. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Spanning circuits in regular matroids. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1433-1441. SIAM, 2017. Google Scholar
  12. Tomás Gavenciak, Daniel Král, and Sang-il Oum. Deciding first order properties of matroids. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, volume 7392, pages 239-250. Springer, 2012. Google Scholar
  13. James F. Geelen, A. M. H. Gerards, and Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs. J. Comb. Theory, Ser. B, 84(2):270-290, 2002. URL: http://dx.doi.org/10.1006/jctb.2001.2082.
  14. Jim Geelen, Bert Gerards, and Geoff Whittle. Excluding a planar graph from gf(q)-representable matroids. J. Comb. Theory, Ser. B, 97(6):971-998, 2007. URL: http://dx.doi.org/10.1016/j.jctb.2007.02.005.
  15. Jim Geelen, Bert Gerards, and Geoff Whittle. Solving Rota’s conjecture. Notices Amer. Math. Soc., 61(7):736-743, 2014. URL: http://dx.doi.org/10.1090/noti1139.
  16. Jim Geelen, Bert Gerards, and Geoff Whittle. The Highly Connected Matroids in Minor-Closed Classes. Ann. Comb., 19(1):107-123, 2015. URL: http://dx.doi.org/10.1007/s00026-015-0251-3.
  17. Leslie Ann Goldberg and Mark Jerrum. A polynomial-time algorithm for estimating the partition function of the ferromagnetic ising model on a regular matroid. SIAM J. Comput., 42(3):1132-1157, 2013. URL: http://dx.doi.org/10.1137/110851213.
  18. Alexander Golynski and Joseph Douglas Horton. A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In Algorithm Theory - SWAT 2002, 8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings, volume 2368 of Lecture Notes in Computer Science, pages 200-209. Springer, 2002. Google Scholar
  19. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of generalized vertex cover problems. In Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, volume 3608 of Lecture Notes in Computer Science, pages 36-48, 2005. URL: http://dx.doi.org/10.1007/11534273_5.
  20. Moritz Hardt and Ankur Moitra. Algorithms and hardness for robust subspace recovery. In Proceedings of the 26th Annual Conference on Learning Theory (COLT), volume 30 of JMLR Proceedings, pages 354-375. JMLR.org, 2013. Google Scholar
  21. Petr Hlinený. Branch-width, parse trees, and monadic second-order logic for matroids. J. Comb. Theory, Ser. B, 96(3):325-351, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.08.005.
  22. Petr Hlinený and Sang-il Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput., 38(3):1012-1032, 2008. URL: http://dx.doi.org/10.1137/070685920.
  23. Jisu Jeong, Eun Jung Kim, and Sang-il Oum. Constructive algorithm for path-width of matroids. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1695-1704. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch116.
  24. Gwenaël Joret and Adrian Vetta. Reducing the rank of a matroid. Discrete Mathematics & Theoretical Computer Science, 17(2):143-156, 2015. URL: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2334.
  25. Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In FOCS 2011, pages 160-169. IEEE Computer Society, 2011. Google Scholar
  26. Leonid G. Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. On the complexity of some enumeration problems for matroids. SIAM J. Discrete Math., 19(4):966-984, 2005. URL: http://dx.doi.org/10.1137/S0895480103428338.
  27. Daniel Král'. Decomposition width of matroids. Discrete Applied Mathematics, 160(6):913-923, 2012. URL: http://dx.doi.org/10.1016/j.dam.2011.03.016.
  28. Dániel Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394-406, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.10.007.
  29. Jesper Nederlof. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica, 65(4):868-884, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9630-x.
  30. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96(4):514-528, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.10.006.
  31. Sang-il Oum and Paul D. Seymour. Testing branch-width. J. Comb. Theory, Ser. B, 97(3):385-393, 2007. URL: http://dx.doi.org/10.1016/j.jctb.2006.06.006.
  32. James Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, second edition, 2011. URL: http://dx.doi.org/10.1093/acprof:oso/9780198566946.001.0001.
  33. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network sparsification for steiner problems on planar and bounded-genus graphs. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 276-285. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.37.
  34. Paul D. Seymour. Decomposition of regular matroids. J. Comb. Theory, Ser. B, 28(3):305-359, 1980. URL: http://dx.doi.org/10.1016/0095-8956(80)90075-1.
  35. Paul D. Seymour. Matroid minors. In Handbook of combinatorics, Vol. 1, 2, pages 527-550. Elsevier, Amsterdam, 1995. Google Scholar
  36. Klaus Truemper. Max-flow min-cut matroids: Polynomial testing and polynomial algorithms for maximum flow and shortest routes. Math. Oper. Res., 12(1):72-96, 1987. URL: http://dx.doi.org/10.1287/moor.12.1.72.
  37. Klaus Truemper. Matroid decomposition. Academic Press, 1992. Google Scholar
  38. Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Information Theory, 43(6):1757-1766, 1997. URL: http://dx.doi.org/10.1109/18.641542.
  39. D. J. A. Welsh. Combinatorial problems in matroid theory. In Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pages 291-306. Academic Press, London, 1971. Google Scholar
  40. Mingyu Xiao and Hiroshi Nagamochi. An FPT algorithm for edge subset feedback edge set. Inf. Process. Lett., 112(1-2):5-9, 2012. URL: http://dx.doi.org/10.1016/j.ipl.2011.10.007.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact