Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field $\mathbb F$, we wish to find a "branch-decomposition" 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 (1996) 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\v{e}n\'y and Oum (2008) 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. (2003) that the number of forbidden minors is finite and uses the algorithm of Hlin\v{e}n\'y (2006) 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$.


翻译:以一个固定的有限字段的有限维向量空间的$美元为基数 美元=mathb F$,我们希望找到这些宽度亚空间的“支架分解” $k$, 也就是一个基底树的亚基值$T$美元, 上面绘制的叶子双向地向子空间, 每个边缘的美元为T$, 与叶的一个部分的叶子相关的子空间总和 $-e$, 而与其它部分的叶叶子相关的子空间总和, 相交的尺寸为$kyy 美元。 这个问题包括计算一个基底基底的 $mahb 基数的分支 $m- 美元; 我们的亚基底基底的直基数使用一个基底基数的亚值 。

0
下载
关闭预览

相关内容

【硬核书】矩阵代数基础,248页pdf
专知会员服务
86+阅读 · 2021年12月9日
强化学习最新教程,17页pdf
专知会员服务
180+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
195+阅读 · 2019年10月10日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【泡泡一分钟】一种实用且高效的多视图匹配方法
泡泡机器人SLAM
6+阅读 · 2018年11月19日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Simple Recurrent Unit For Sentence Classification
哈工大SCIR
6+阅读 · 2017年11月29日
Arxiv
0+阅读 · 2021年12月23日
Arxiv
0+阅读 · 2021年12月23日
Arxiv
0+阅读 · 2021年12月23日
Query Embedding on Hyper-relational Knowledge Graphs
Arxiv
4+阅读 · 2021年6月17日
Arxiv
4+阅读 · 2019年2月8日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【泡泡一分钟】一种实用且高效的多视图匹配方法
泡泡机器人SLAM
6+阅读 · 2018年11月19日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
LibRec 精选:推荐的可解释性[综述]
LibRec智能推荐
10+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Simple Recurrent Unit For Sentence Classification
哈工大SCIR
6+阅读 · 2017年11月29日
相关论文
Arxiv
0+阅读 · 2021年12月23日
Arxiv
0+阅读 · 2021年12月23日
Arxiv
0+阅读 · 2021年12月23日
Query Embedding on Hyper-relational Knowledge Graphs
Arxiv
4+阅读 · 2021年6月17日
Arxiv
4+阅读 · 2019年2月8日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员