{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:14Z","timestamp":1787321114800,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE40-0025-01"],"award-info":[{"award-number":["ANR-18-CE40-0025-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"publisher","award":["IBS-R029-C1"],"award-info":[{"award-number":["IBS-R029-C1"]}],"id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2017R1A2B4005020"],"award-info":[{"award-number":["NRF-2017R1A2B4005020"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field ${\\mathbb F}$, we wish to find a \u201cbranch-decomposition\u201d of these subspaces of width at most $k$ that is a subcubic tree $T$ with $n$ leaves mapped bijectively to the subspaces such that for every edge $e$ of $T$, the sum of subspaces associated to the leaves in one component of $T-e$ and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most $k$. This problem includes the problems of computing branch-width of ${\\mathbb F}$-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most $k$, if it exists, for input subspaces of a finite-dimensional vector space over ${\\mathbb F}$. Our algorithm is analogous to the algorithm of Bodlaender and Kloks [ J. Algorithms, 21 (1996), pp. 358--402] on tree-width of graphs. To extend their framework to branch-decompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. The only known previous fixed-parameter algorithm for branch-width of ${\\mathbb F}$-represented matroids was due to Hlin\u011bn\u00fd and Oum [ SIAM J. Comput., 38 (2008), pp. 1012--1032] that runs in time $O(n^3)$ where $n$ is the number of elements of the input ${\\mathbb F}$-represented matroid. But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. [ J. Combin. Theory Ser. B, 88 (2003), pp. 261--265] that the number of forbidden minors is finite and uses the algorithm of Hlin\u011bn\u00fd [ J. Combin. Theory Ser. B, 96 (2006), pp. 325--351] on checking monadic second-order formulas on ${\\mathbb F}$-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed $k$.<\/jats:p>","DOI":"10.1137\/19m1285895","type":"journal-article","created":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T15:37:28Z","timestamp":1636040248000},"page":"2544-2617","source":"Crossref","is-referenced-by-count":7,"title":["Finding Branch-Decompositions of Matroids, Hypergraphs, and More"],"prefix":"10.1137","volume":"35","author":[{"given":"Jisu","family":"Jeong","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6824-0516","authenticated-orcid":true,"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6889-7286","authenticated-orcid":true,"given":"Sang-il","family":"Oum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,4]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"atypb2","first-page":"627","author":"Bodlaender H. L.","year":"1997","journal-title":"Berlin"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"atypb4","first-page":"158","author":"Cunningham W. H.","year":"2007","journal-title":"Berlin"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/070687256"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00046-1"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.08.005"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/070685920"},{"key":"atypb9","first-page":"1695","author":"Jeong J.","year":"2016","journal-title":"Philadelphia"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2740283"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9399-y"},{"key":"atypb12","first-page":"532","author":"Lagergren J.","year":"1991","journal-title":"Berlin"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.06.006"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"J. Oxley,\n                      Matroid Theory\n                      , 2nd ed., Oxf. Grad. Texts Math., 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":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"key":"atypb19","unstructured":"D. M. Thilikos and H. L. Bodlaender,\n                      Constructive Linear Time Algorithms for Branchwidth\n                      , Tech. Report UU-CS 2000-38, Universiteit Utrecht, 2000,http:\/\/www.cs.uu.nl\/research\/techreps\/UU-CS-2000-38.html."},{"key":"atypb20","first-page":"192","author":"Thilikos D. M.","year":"2000","journal-title":"Berlin"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1285895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:33Z","timestamp":1787317593000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1285895"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1285895"],"URL":"https:\/\/doi.org\/10.1137\/19m1285895","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}