Packing A-paths in Group-Labeled Graphs via Linear Matroid Parity
Packing A-paths in Group-Labeled Graphs via Linear Matroid Parity
复制标题
通过线性拟阵奇偶校验将 A 路径打包在组标记图中
DOI：
10.1137/130949877
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Yutaro Yamaguchi
中科院分区：
文献类型：
--
作者：
Kansai Fukumitsu;Kazuto Fujishima;Azumi Yoshimura;You Kure Wu;John Heuser;and Mineko Kengaku．;Yutaro Yamaguchi
马德尔的不相交路问题是非二部匹配和门格尔的不相交路问题的一个共同推广。Lova ́ sz [J. Combin. Theory Ser. B，28（1980），pp. 208--236]）通过简化为拟阵匹配，提出了一个多项式时间算法。后来Schrijver [Combinatorial Optimization：Polyhedra and Efficiency，Springer-Verlag，柏林，2003]给出了线性拟阵奇偶问题的更直接的简化，这导致了更快的算法。作为马德尔问题的推广，Chudnovsky等人[Combinatorica，26（2006），pp. 521 - 532]引入了一个群标号图的非零路填充框架，并证明了一个极小极大定理。Chudnovsky，Cunningham，and Geelen [Combinatorica，28（2008），pp. 145 - 161]给出了求解这一广义问题的有效组合算法。另一方面，Pap [Combinatorica，27（2007），pp. 247 - 251]引入了一个包装非返回路径的框架作为进一步的推广。在本文中，我们讨论了Schrijver约简技术和Chudnovsky，Cunningham和Geelen算法的可能扩展[Combinatorica，28（2008），pp. 145 - 161]到Pap [A Constructive Approach to Matching and Its Generalizations，Ph. D.论文，数学研究所，Eo tvo s Lora ́ nd大学，布达佩斯，匈牙利，2006年]，在子群模型的名义下，这显然是推广，但实际上是相当于包装不返回路径。提取组合方面的Schrijver的减少，我们引入了相干表示的概念，并提供了一个必要和充分条件的问题，承认减少线性拟阵奇偶校验问题与相干表示的群体。因此，我们针对填充非零路径的重要特殊情况给出了更快的算法。此外，事实证明，包装不归路承认这样的减少线性拟阵奇偶问题的当且仅当输入标签集的大小是最多4，这导致其有效的可解性，在这种特殊情况下。
Mader's disjoint-paths problem is a common generalization of non-bipartite matching and Menger's disjoint paths problems. Lovász [J. Combin. Theory Ser. B, 28 (1980), pp. 208--236]) proposed a polynomial-time algorithm for this problem through a reduction to matroid matching. A more direct reduction to the linear matroid parity problem was given later by Schrijver [Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003], which led to faster algorithms. As a generalization of Mader's problem, Chudnovsky et al. [Combinatorica, 26 (2006), pp. 521--532] introduced a framework of packing non-zero-paths in group-labelled graphs and proved a min-max theorem. Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145--161] provided an efficient combinatorial algorithm for this generalized problem. On the other hand, Pap [Combinatorica, 27 (2007), pp. 247--251] introduced a framework of packing non-returning-paths as a further generalization. In this paper, we discuss possible extensions of Schrijver's reduction technique and the algorithm of Chudnovsky, Cunningham, and Geelen [Combinatorica, 28 (2008), pp. 145--161] to another framework introduced by Pap [A Constructive Approach to Matching and Its Generalizations, Ph.D. thesis, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary, 2006], under the name of the subgroup model, which apparently generalizes but in fact is equivalent to packing nonreturning-paths. Extracting combinatorial aspects of Schrijver's reduction, we introduce the concept of coherent representation and provide a necessary and sufficient condition for the groups in question to admit a reduction to the linear matroid parity problem with coherent representations. As a consequence, we give faster algorithms for important special cases of packing nonzero-paths. In addition, it turns out that packing nonreturning-paths admits such a reduction to the linear matroid parity problem if and only if the size of the input label set is at most four, which leads to its efficient solvability in this special case.