Finding BranchDecompositions of Matroids, Hypergraphs, and More
Jeong, Jisu; Kim, Eun Jung; Oum, SangIl (2021), Finding BranchDecompositions of Matroids, Hypergraphs, and More, SIAM Journal on Discrete Mathematics, 35, 4, p. 25442617. 10.1137/19M1285895
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1711.01381Date
2021Journal name
SIAM Journal on Discrete MathematicsVolume
35Number
4Publisher
SIAM  Society for Industrial and Applied Mathematics
Pages
25442617
Publication identifier
Metadata
Show full item recordAuthor(s)
Jeong, JisuDepartment of Mathematical Sciences, KAIST
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Oum, SangIl
Department of Mathematical Sciences, KAIST
Abstract (EN)
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 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 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. The only known previous fixedparameter algorithm for branchwidth of Frepresented matroids was due to Hliněný and Oum (2008) that runs in time O(n3) where n is the number of elements of the input Frepresented matroid. 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 Hliněný (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.Subjects / Keywords
Branchwidth; Rankwidth; Carvingwidth; Matroid; Fixedparameter tractabilityRelated items
Showing items related by title and author.

Jeong, Jisu; Kim, Eun Jung; Oum, Sangil (2016) Communication / Conférence

Kanté, Mamadou Moustapha; Kim, Eun Jung; Kwon, Ojoung; Oum, SangIl (2023) Article accepté pour publication ou publié

Jeong, Jisu; Kim, Eun Jung; Oum, SangIl (2017) Article accepté pour publication ou publié

Kim, Eun Jung; Oum, Sangil; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2018) Article accepté pour publication ou publié

Kim, Eun Jung; Oum, SangIl; Paul, Christophe; Sau Valls, Ignasi; Thilikos, Dimitrios M. (2015) Communication / Conférence