Document Open Access Logo

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.59.pdf
  • Filesize: 495 kB
  • 13 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • Department of Informatics, University of Bergen, Norway
Petr A. Golovach
  • Department of Informatics, University of Bergen, Norway
Daniel Lokshtanov
  • Department of Computer Science, University of California Santa Barbara, USA
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Meirav Zehavi
  • Ben-Gurion University, Israel

Funding

The research leading to these results has received funding from the Research Council of Norway via the projects "CLASSIS" and "MULTIVAL".

Acknowledgements

We thank Jim Geelen for valuable insights regarding matroid minors.

Cite AsGet BibTex

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.59

Abstract

Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an r-rank perturbed graphic matroid M is a binary matroid that can be represented in the form I +P, where I is the incidence matrix of some graph and P is a binary matrix of rank at most r. Such matroids naturally appear in a number of theoretical and applied settings. The main motivation behind our work is an attempt to understand which parameterized algorithms for various problems on graphs could be lifted to perturbed graphic matroids. We study the parameterized complexity of a natural generalization (for matroids) of the following fundamental problems on graphs: Steiner Tree and Multiway Cut. In this generalization, called the Space Cover problem, we are given a binary matroid M with a ground set E, a set of terminals T subseteq E, and a non-negative integer k. The task is to decide whether T can be spanned by a subset of E \ T of size at most k. We prove that on graphic matroid perturbations, for every fixed r, Space Cover is fixed-parameter tractable parameterized by k. On the other hand, the problem becomes W[1]-hard when parameterized by r+k+|T| and it is NP-complete for r <= 2 and |T|<= 2. On cographic matroids, that are the duals of graphic matroids, Space Cover generalizes another fundamental and well-studied problem, namely Multiway Cut. We show that on the duals of perturbed graphic matroids the Space Cover problem is fixed-parameter tractable parameterized by r+k.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Binary matroids
  • perturbed graphic matroids
  • spanning set
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. Nikhil Bansal, Daniel Reichman, and Seeun William Umboh. LP-based robust algorithms for noisy minor-free and bounded treewidth graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1964-1979. SIAM, 2017. Google Scholar
  3. Édouard Bonnet, László Egri, and Dániel Marx. Fixed-parameter Approximability of Boolean MinCSPs. CoRR, abs/1601.04935, 2016. URL: http://arxiv.org/abs/1601.04935.
  4. Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? J. ACM, 58(3):11:1-11:37, 2011. URL: http://dx.doi.org/10.1145/1970392.1970395.
  5. Venkat Chandrasekaran, Sujay Sanghavi, Pablo A. Parrilo, and Alan S. Willsky. Rank-Sparsity Incoherence for Matrix Decomposition. SIAM Journal on Optimization, 21(2):572-596, 2011. URL: http://dx.doi.org/10.1137/090761793.
  6. Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michal Pilipczuk. Designing FPT Algorithms for Cut Problems Using Randomized Contractions. SIAM J. Comput., 45(4):1171-1229, 2016. URL: http://dx.doi.org/10.1137/15M1032077.
  7. 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.
  8. 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.
  9. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 3rd edition, 2005. Google Scholar
  10. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  11. 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.
  12. Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: http://dx.doi.org/10.1002/net.3230010302.
  13. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Covering Vectors by Spaces: Regular Matroids. SIAM J. Discrete Math., 32(4):2512-2565, 2018. Google Scholar
  14. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. CoRR, abs/1902.06957, 2019. URL: http://arxiv.org/abs/1902.06957.
  15. Jim Geelen, Bert Gerards, and Geoff Whittle. Solving Rota’s conjecture. Notices Amer. Math. Soc., 61(7):736-743, 2014. Google Scholar
  16. Jim Geelen, Bert Gerards, and Geoff Whittle. The Highly Connected Matroids in Minor-Closed Classes. Ann. Comb., 19(1):107-123, 2015. Google Scholar
  17. Jim Geelen and Rohan Kapadia. Computing Girth and Cogirth in Perturbed Graphic Matroids. Combinatorica, 38(1):167-191, 2018. URL: http://dx.doi.org/10.1007/s00493-016-3445-3.
  18. Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke. Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Computer and System Sciences, 72(8):1386-1396, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2006.02.001.
  19. Avner Magen and Mohammad Moharrami. Robust Algorithms for Max Independent Set on Minor-Free Graphs Based on the Sherali-Adams Hierarchy. In Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 13th International Workshop on Randomization and Computation (RANDOM), volume 5687 of Lecture Notes in Comput. Sci., pages 258-271. Springer, 2009. Google Scholar
  20. 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.
  21. James G. Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford university press, 2nd edition, 2010. Google Scholar
  22. Nauman Shahid, Nathanael Perraudin, Vassilis Kalofolias, Gilles Puy, and Pierre Vandergheynst. Fast Robust PCA on Graphs. J. Sel. Topics Signal Processing, 10(4):740-756, 2016. URL: http://dx.doi.org/10.1109/JSTSP.2016.2555239.
  23. Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6):1757-1766, 1997. Google Scholar
  24. John Wright, Arvind Ganesh, Shankar R. Rao, YiGang Peng, and Yi Ma. Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization. In Proceedings of 23rd Annual Conference on Neural Information Processing Systems (NIPS), pages 2080-2088. Curran Associates, Inc., 2009. URL: http://papers.nips.cc/paper/3704-robust-principal-component-analysis-exact-recovery-of-corrupted-low-rank-matrices-via-convex-optimization.
  25. 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.
  26. Mengnan Zhao, M. Devrim Kaba, René Vidal, Daniel P. Robinson, and Enrique Mallada. Sparse Recovery over Graph Incidence Matrices. In Proceedings of the 57th IEEE Conference on Decision and Control (CDC), pages 364-371, 2018. URL: http://dx.doi.org/10.1109/CDC.2018.8619666.
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 Imprint Privacy Contact