Algebraic Algorithms for Linear Matroid Parity Problems
Algebraic Algorithms for Linear Matroid Parity Problems
复制标题
线性拟阵奇偶校验问题的代数算法
DOI：
10.1145/2601066
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
K. M. Leung
中科院分区：
文献类型：
--
作者：
Ho Yee Cheung;L. Lau;K. M. Leung
我们提出了线性拟阵奇偶问题的快速而简单的代数算法及其应用。对于线性拟阵奇偶问题，我们得到了一个运行时间<i>为O</i>（<i>mr</i><sup>ω-1</sup>）的简单随机算法，其中<i>m</i>和<i>r</i>分别为列数和行数，ω = 2.3727为矩阵乘指数.这改进了Gabow和Stallmann的<i>O</i>（<i>mr</i><sup>ω</sup>）时间算法，并与线性拟阵求交的代数算法的运行时间相匹配，回答了Harvey的一个问题.我们还提出了一个非常简单的替代算法，运行时间<i>为O</i>（<i>MR</i><sup>2</sup>），它不需要快速矩阵乘法。
我们进一步改进的代数算法，为一些特定的图形问题的兴趣。对于马德尔的不交<i>S</i>-路问题，我们给出了一个<i>O</i>（<i>n</i><sup>ω</sup>）时间的随机算法，其中<i>n</i>是顶点数.这大大提高了现有结果的运行时间，并与图匹配的代数算法的运行时间相匹配。对于图拟阵奇偶问题，我们给出了一个<i>O</i>（<sup>n4</sup>）时间随机化算法，其中<i>n</i>是顶点数，并针对一种特殊情况给出了一个<i>O</i>（<sup>n3</sup><i></i><i></i>这些算法在<i>n</i>方面是最优的，因为输入大小可以分别是Ω（<i>n</i><sup>4</sup>）和Ω（<i>n</i><sup>3</sup>）。
这些技术是基于由Mucha和Sankowski，Harvey和Sankowski开发的代数算法框架。虽然线性拟阵奇偶校验和马德尔的不相交<i>的S</i>-路的组合算法的设计具有挑战性的推广，我们的研究结果表明，线性拟阵相交和图匹配的代数算法可以很好地扩展到更一般的设置。即使不使用快速矩阵乘法，所有算法仍然比现有算法快。这些提供了可以在实践中容易地实现的简单算法。
We present fast and simple algebraic algorithms for the linear matroid parity problem and its applications. For the linear matroid parity problem, we obtain a simple randomized algorithm with running time <i>O</i>(<i>mr</i><sup>ω-1</sup>), where <i>m</i> and <i>r</i> are the number of columns and the number of rows, respectively, and ω ≈ 2.3727 is the matrix multiplication exponent. This improves the <i>O</i>(<i>mr</i><sup>ω</sup>)-time algorithm by Gabow and Stallmann and matches the running time of the algebraic algorithm for linear matroid intersection, answering a question of Harvey. We also present a very simple alternative algorithm with running time <i>O</i>(<i>mr</i><sup>2</sup>), which does not need fast matrix multiplication.
We further improve the algebraic algorithms for some specific graph problems of interest. For the Mader’s disjoint <i>S</i>-path problem, we present an <i>O</i>(<i>n</i><sup>ω</sup>)-time randomized algorithm where <i>n</i> is the number of vertices. This improves the running time of the existing results considerably and matches the running time of the algebraic algorithms for graph matching. For the graphic matroid parity problem, we give an <i>O</i>(<i>n</i><sup>4</sup>)-time randomized algorithm where <i>n</i> is the number of vertices, and an <i>O</i>(<i>n</i><sup>3</sup>)-time randomized algorithm for a special case useful in designing approximation algorithms. These algorithms are optimal in terms of <i>n</i> as the input size could be Ω (<i>n</i><sup>4</sup>) and Ω (<i>n</i><sup>3</sup>), respectively.
The techniques are based on the algebraic algorithmic framework developed by Mucha and Sankowski, Harvey, and Sankowski. While linear matroid parity and Mader’s disjoint <i>S</i>-path are challenging generalizations for the design of combinatorial algorithms, our results show that both the algebraic algorithms for linear matroid intersection and graph matching can be extended nicely to more general settings. All algorithms are still faster than the existing algorithms even if fast matrix multiplication is not used. These provide simple algorithms that can be easily implemented in practice.