Blocking Trails for $f$-factors of Multigraphs

Abstract

Blocking flows, introduced by Dinic [2] for network flow, have been used to speed up many augmenting-path type algorithms, especially matching algorithms e.g., [18, 23, 16]. We present an $O(m)$ time algorithm for blocking trails for f-factors of general multigraphs. This improves a previous algorithm by a factor of $\alpha (m,n)$. This speeds up a number of efficient algorithms for f-factors, e.g., the algorithm of [11] for maximum weight f-matching improves by the aforementioned $\alpha (m,n)$ factor to running time $O(\sqrt{\Phi \log \Phi }m\log (\Phi W))$ for $\Phi ={\sum }_{v\in V}f(v)$, $W$ the maximum edge weight. This time bound is within a factor $\sqrt{\log \Phi }$ of the bound for bipartite multigraphs. The technical difficulty for this work stems from the fact that previous algorithms for both matching and $f$-matching use vertex contractions to form blossoms, but our dfs-based approach necessitates using edge contractions. As an example difficulty, edge contractions introduce a new form of blossoms we call "skew blossoms". These are configurations that must be reorganized in order to become valid blossoms.

arXiv comment33 pages, 14 figures