Shortest bibranchings and valuated matroid intersection
Shortest bibranchings and valuated matroid intersection
复制标题
最短分枝和评估拟阵交集
DOI：
10.1007/s13160-012-0072-2
复制
发表时间：
2012
影响因子：
0.9
通讯作者：
K. Takazawa
中科院分区：
文献类型：
--
作者：
Y. Cui;J. Jansson;and W.-K. Sung.;J. Jansson and A. Lingas.;須田亮平，中野眞一，山中克久;K. Takazawa
对于有向图D =（V，A）和V的一个划分{S，T}，如果T中的每个顶点都可达且S中的每个顶点都可达子图（V，B），则称弧集为S-T。双分支通常推广了二分边覆盖和树状结构。Schrijver给出了一个确定S-T多胞形的完全对偶积分线性系统，而最短S-T问题，其目标是找到一个最小总弧权的S-T，可以用椭球方法或Keijloven和Pendavingh的快速组合算法在多项式时间内求解。Murota提出的赋值拟阵交问题是独立匹配问题的加权推广，包括独立分配问题和加权拟阵交问题。通过推广加权拟阵求交问题的经典组合算法，可以用多项式多值预言机有效地求解赋值拟阵求交问题。在本文中，我们证明了最短S − T问题是多项式可约化的赋值拟阵交问题。这种简化给出了为什么最短S − T问题是易处理的一个答案，并暗示了基于赋值拟阵交集算法的最短S − T问题的新组合算法，其中值预言对应于计算最小权重树形图。
For a digraphD= (V,A) and a partition {S,T} ofV, an arc setis called anS−Tif each vertex inTis reachable fromSand each vertex inSreachesTin the subgraph (V,B). Bibranchings commonly generalize bipartite edge covers and arborescences. A totally dual integral linear system determining theS−Tpolytope is provided by Schrijver, and the shortestS−Tproblem, whose objective is to find anS−Tof minimum total arc weight, can be solved in polynomial time by the ellipsoid method or a faster combinatorial algorithm due to Keijsper and Pendavingh. The valuated matroid intersection problem, introduced by Murota, is a weighted generalization of the independent matching problem, including the independent assignment problem and the weighted matroid intersection problem. The valuated matroid intersection problem can be solved efficiently with polynomially many value oracles by extending classical combinatorial algorithms for the weighted matroid intersection problem. In this paper, we show that the shortestS−Tproblem is polynomially reducible to the valuated matroid intersection problem. This reduction suggests one answer to why the shortestS−Tproblem is tractable, and implies new combinatorial algorithms for the shortestS−Tproblem based on the valuated matroid intersection algorithm, where a value oracle corresponds to computing a minimum-weight arborescence.