{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:34Z","timestamp":1787320054195,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. 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, in the Space Cover problem, 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 the linear span of $F$ contains all vectors of $T$. For graphic matroids this problem is essentially Steiner Forest and for cographic matroids this is a generalization of Multiway Cut. Our main result is the algorithm with running time $2^{\\mathcal{O}h(k)}\\cdot ||M|| ^{\\mathcal{O}h(1)}$ solving Space Cover 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 on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace.<\/jats:p>","DOI":"10.1137\/17m1151250","type":"journal-article","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T13:23:22Z","timestamp":1542288202000},"page":"2512-2565","source":"Crossref","is-referenced-by-count":0,"title":["Covering Vectors by Spaces: Regular Matroids"],"prefix":"10.1137","volume":"32","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,15]]},"reference":[{"key":"atypb1","first-page":"800","author":"Basavaraju M.","year":"2014","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"atypb3","first-page":"67","author":"Bj\u00f6rklund A.","year":"2007","journal-title":"New York"},{"key":"atypb4","first-page":"667","author":"Blelloch G. E.","year":"2006","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"atypb7","first-page":"290","author":"Dinic E. A.","year":"1976","journal-title":"Moscow"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/13094030X"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts in Comput. Sci., Springer, New York, 2013,https:\/\/doi.org\/10.1007\/978-1-4471-5559-1.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797323571"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"atypb13","first-page":"1433","author":"Fomin F. V.","year":"2017","journal-title":"Philadalphia"},{"key":"atypb14","first-page":"239","author":"Gavenciak T.","year":"2012","journal-title":"New York"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.02.005"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1090\/noti1139"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-015-0251-3"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2082"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/110851213"},{"key":"atypb20","first-page":"200","author":"Golynski A.","year":"2002","journal-title":"New York"},{"key":"atypb21","first-page":"36","author":"Guo J.","year":"2005","journal-title":"New York"},{"key":"atypb22","first-page":"354","author":"Hardt M.","year":"2013","journal-title":"JMLR"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.08.005"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/070685920"},{"key":"atypb25","first-page":"1695","author":"Jeong J.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb26","first-page":"143","volume":"17","author":"Joret G.","year":"2015","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"atypb27","first-page":"160","author":"Kawarabayashi K.","year":"2011","journal-title":"IEEE Computer Society"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103428338"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.03.016"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.016"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/110855247"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.06.006"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"J. Oxley,\n                      Matroid Theory\n                      , 2nd ed., Oxford Grad. Texts in Math. 21, Oxford University Press, Oxford, UK, 2011,https:\/\/doi.org\/10.1093\/acprof:oso\/9780198566946.001.0001.","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"atypb37","first-page":"276","author":"Pilipczuk M.","year":"2014","journal-title":"IEEE"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579179"},{"key":"atypb40","first-page":"527","author":"Seymour P. D.","year":"1995","journal-title":"Amsterdam"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.1.72"},{"key":"atypb42","unstructured":"K. Truemper,\n                      Matroid Decomposition\n                      , Academic Press, New York, 1992."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/18.641542"},{"key":"atypb44","first-page":"291","author":"D. J.","year":"1971","journal-title":"London"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.007"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1151250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:53Z","timestamp":1787316833000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1151250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1151250"],"URL":"https:\/\/doi.org\/10.1137\/17m1151250","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}