Abstract
Given n subspaces of a finitedimensional vector space over a fixed finite field F, we wish to find a "branchdecomposition" 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 Te 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 branchwidth of Frepresented matroids, rankwidth of graphs, branchwidth of hypergraphs, and carvingwidth of graphs.
We present a fixedparameter algorithm to construct such a branchdecomposition of width at most k, if it exists, for input subspaces of a finitedimensional vector space over F. Our algorithm is analogous to the algorithm of Bodlaender and Kloks (1996) on treewidth of graphs. To extend their framework to branchdecompositions of vector spaces, we developed highly generic tools for branchdecompositions on vector spaces. For this problem, a fixedparameter algorithm was known due to HlinenÃ½ and Oum (2008). But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. (2003) that the number of forbidden minors is finite and uses the algorithm of HlinenÃ½ (2006) on checking monadic secondorder formulas on Frepresented matroids of small branchwidth. Our result does not depend on such a fact and is completely selfcontained, and yet matches their asymptotic running time for each fixed k.
BibTeX  Entry
@InProceedings{jeong_et_al:LIPIcs:2018:9084,
author = {Jisu Jeong and Eun Jung Kim and Sangil Oum},
title = {{Finding BranchDecompositions of Matroids, Hypergraphs, and More}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {80:180:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9084},
URN = {urn:nbn:de:0030drops90849},
doi = {10.4230/LIPIcs.ICALP.2018.80},
annote = {Keywords: branchwidth, rankwidth, carvingwidth, fixedparameter tractability}
}
Keywords: 

branchwidth, rankwidth, carvingwidth, fixedparameter tractability 
Collection: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 
Issue Date: 

2018 
Date of publication: 

04.07.2018 