Blocking Trails for $f$-factors of Multigraphs

Blocking flows (aka blocking paths) are a fundamental tool for speeding up augmenting-type algorithms. They were introduced by Dinic [3] to obtain the first strongly polynomial algorithm for maximum network flow. Hopcroft and Karp [19] (and independently Karzanov [21]) applied the idea to maximum cardinality bipartite matching. They also proving its applicability to general graph matching, and Micali and Vazirani [24] gave the first blocking paths algorithm for general graph cardinality matching. Gabow and Tarjan applied blocking flows in cost-scaling algorithms for minimum cost network flow (aka degree-constrained subgraphs or $f$-matchings) [16] and minimum cost general graph matching [17]. Here we have only cited some first applications of the idea, see reference [25, Sec. 9.6,10.8b,16.7a,17.5a,24.4a] for a comprehensive bibliography for the many uses of blocking paths.

We present an algorithm for blocking trails for $f$-factors of general multigraphs. Here “general” is to be contrasted with “bipartite”, an important but much simpler special case. For the definitions of $f$-factors, blocking trails, etc., please see the above abstract or the last paragraph of this section.

We turn to discussing recent work that applies blocking trails to multigraph $f$-factors. Huang and Pettie [20] give algorithms for a host of problems on general multigraphs: They achieve time $O(\sqrt{\Phi}\,m\,\alpha(m,n))$ for maximum cardinality $f$-matching. Here $\Phi=\sum_{v\in V}f(v)$, i.e., twice the size of an $f$-factor. The same bound holds for a minimum cardinality $f$-edge cover (i.e., $f$ is a lower bound for degrees in the desired subgraph). These algorithms use a scaling algorithm that finds an approximation to the weighted version of the problem. The scaling algorithm uses time $O(m\,\alpha(m,n)\,\epsilon^{-1}\,{\rm log}\,\epsilon^{-1})$ to find a $(1-\epsilon)$-approximate maximum weight $f$-matching, or a $(1+\epsilon)$-approximate minimum weight $f$-edge cover.

The next applications are scaling algorithms for maximum weight $f$-factors. To put the results in perspective first recall the classic time bounds for (unweighted) bipartite $f$-factors [21, 8]:

For maximum weight bipartite $f$-factors, Gabow and Tarjan [16] presented a scaling algorithm whose time bound is just a scaling factor above (1.1), i.e., time $O(n^{2/3}\;m\;\,{\rm log}\,(nW))$ for simple graphs and $O(\sqrt{\Phi}\;m\;\,{\rm log}\,(\Phi W))$ for multigraphs. Here $W$ is the maximum (integral) edge weight.

Now consider general graphs. Duan, He and Zhang [4] give a scaling algorithm for maximum weight $f$-factors of simple general graphs. The time is only logarithmic factors above (1.1), i.e., $\widetilde{O}(n^{2/3}\,m\,\,{\rm log}\,W)$. In fact when all weights are 1 this is the first algorithm to achieve the bound of (1.1), to within logarithmic factors, for unweighted $f$-factors of simple general graphs. Returning to weighted $f$-factors, Gabow [12] gives a scaling algorithm that achieves the multigraph bound of (1.1), to within logarithmic factors, specifically $O(\sqrt{\Phi\,{\rm log}\,\Phi}\,m\,\alpha(m,n)\,\,{\rm log}\,(\Phi W))$.

All of the above algorithms use a subroutine that finds a set of blocking trails. The time bounds cited above assume the blocking set is found by the subroutine presented by Huang and Pettie [20]. It finds a blocking set (more specifically, a set of blocking trails and cycles) in time $O(m\alpha(m,n))$. Our blocking trail algorithm runs in time $O(m)$. Using our algorithm the above time bounds all decrease by a factor $\alpha(m,n)$. (The decrease occurs in [4] but is hidden by the use of $\widetilde{O}$.)

Our algorithm is based on the depth-first-search approach to blocking paths for matching, introduced in [17]; see also [11]. Dfs is a natural approach for finding blocking paths, since backing up prematurely may necessitate reexploring edges later on. However it introduces complications for managing blossoms – they are usually processed immediately on discovery, but they are necessarily postponed in a dfs regime [17, 11]. Extending the dfs approach to $f$-factors of general multigraphs introduces new complications, which we now summarize.

Fundamentally, in previous settings blossoms are “shrunk” using vertex contraction. This holds even in previous $f$-factor algorithms, e.g., see the definition of blossom in [14]. However dfs requires shrinking by edge contraction. A first consequence is new way of discovering blossoms, which we call “skew blossoms”. Skew blossoms have the same properties as ordinary blossoms. However they require a reorganization in order to achieve valid blossom structure (Lemma 2.1).

A second consequence of dfs is incomplete blossoms, i.e., blossoms that do not get completely processed because of the discovery of an augmenting trail. Incomplete blossoms occur in ordinary matching, but they present additional complexity in $f$-factors. Specifically because of edge contraction, an alternating trail from a later search can reenter an incomplete blossom. (See Sec.2.) The analysis of Sec.5 shows these reentries present no problem.

Finally edge-contracted blossoms are not immediately handled by the standard min-max formula for maximum cardinality $f$-matching (which we require to prove the blocking property). We show the essential structure of vertex-contracted blossoms is preserved by our algorithm (e.g., Lemma 5.2).

These complications also reveal the high-level difference between our approach and that of Huang and Pettie [20]. Their algorithm uses vertex contraction rather than edge contraction. Its fundamental idea is cycle cancellation, which does not occur in our algorithm.

The paper is organized as follows. Section 2 discusses blossoms, first reviewing the definition of $f$-factor blossoms, and discussing the new types of blossoms in our algorithm. Appendix A gives the depth-first search algorithm for blocking ordinary matchings [17, 11], for possible help in the reading of Section 2. Section 3 presents the blocking algorithm. Section 4 proves the algorithm constructs a valid search structure, most importantly, the blossoms are valid. Section 5 proves the augmenting trails found by the algorithm form a blocking set. This completes the analysis of the algorithm, which is summarized in Theorem 5.5.

Blossoms are the main issue, and the main stumbling block, in any algorithm for matching general graphs. So it is appropriate to start with the new features of blossoms in our algorithm. This section starts by reviewing the natural definition of $f$-factor blossoms presented in [14]. Then it introduces our new blossom variant, skew blossoms, and overviews the new potential difficulty for our algorithm, incomplete blossoms. Finally it presents a blossom substitute structure that allows our algorithm to treat weighted blossoms as ordinary vertices. Appendix A gives the predecessor of our algorithm and may be useful for Fig.2 showing incomplete blossoms.

This section presents the algorithm. It illustrates the algorithm’s execution and elaborates on details of the algorithm statement.

We manage each $BL(x)$ using a routine pop that removes edges from a list. Specifically pop$(L)$ removes and returns an element $e$ of list $L$, where $e$ can be chosen arbitrarily with one exception: The first invocation of pop$(L)$ must return the first element that was added to $L$. Obviously this is a special case of a FIFO queue, but we use pop for clarity and greater generality.

The $d$ routine works in two phases. It starts by using its GL to do every possible grow step. Then it uses the BL to do every possible blossom step. In this second phase $BL(x)$ contains the edges where the dfs retreated from $x$.

The algorithm constructs a search tree $\cal T$ consisting of the edges added in grow steps. To distinguish $\cal T$ from $G$ we use the terms node and arc for elements of $V({\cal T})$ and $E({\cal T})$, respectively. We view $\cal T$ as an out-tree, so every arc is directed, from parent to child. Consider an edge of $G$ $e={\{x,y\}}$. An occurrence of $e$ in $\cal T$ is denoted as $xy$ or $yx$, where the arc is directed from the first vertex to the second, e.g., $xy$ means $x$ is the parent.

Since a vertex $x\in V(G)$ can occur multiple times in $\cal T$, we identify nodes of $\cal T$ by an incident $\cal T$-arc. Specifically let $yx$ be an arc in $\cal T$. The notation $y\dot{x}$ refers to the node of $\cal T$ at the $x$ end of $yx$, and $x\dot{y}$ is the node at the $y$ end. So node ${y\dot{x}}$ has $y$ the parent of $x$ or a child of $x$.

The low-level algorithm represents blossoms using a data structure for set merging. The universe is the set of $\cal T$-nodes. The sets are the vertex sets of the current blossoms. (So these blossoms are complete or incomplete.) In the pseudocode below, $B_{{x\dot{y}}}$ is maintained as the set of all nodes in the blossom currently containing node ${x\dot{y}}$. It is a simple matter to transform this to a low-level linear-time set merging algorithm [15] (also see the simplfied incremental-tree set-merging algorithm of [13]).²²2A node ${z\dot{x}}$ not in any blossom has $B_{{x\dot{y}}}=\{{z\dot{x}}\}$. This condition also holds for a loop $xx$ when edge $\{x,x\}$ is a singleton blossom. This double usage will not cause any confusion. At any point in time $\overline{{\cal T}}$ denotes the graph with the current blossoms (i.e., the $B_{\cdot}$ sets) contracted.

An invocation of $d$ either returns normally or gets terminated, i.e., it stops execution prematurely. The latter occurs when an augmenting trail is discovered. When this occurs every invocation of $d$ in the current call chain is terminated. All those terminated invocations correspond to edges on the augmenting trail. This trail is added to ${\cal A}$, the set of all augmenting trails that have been discovered.

find_trails does not rematch the trails of ${\cal A}$, leaving that to the calling routine. For instance in applications of our algorithm for weighted matching, the rematching must undo the blossom substitutes. Rematching is further discussed in detail after Theorem 5.5 of Section 5. The other advantage of postponing the rematching is that it simplifies wording in the analysis.

In contrast, the algorithm maintains the quantities $def(x)$, $x\in V(G)$, as the deficiency of vertex $x$ when the trails of ${\cal A}$ have been rematched. This allows proper identification of the free vertices.

Fig.4 gives the pseudocode for our algorithm. Fig.5 gives examples of searches of $d$.

Let us comment on various statements in the algorithm. An invocation $d({\varepsilon\dot{\alpha}})$ made in the main routine is called a search (for an augmenting trail). This invocation is terminated iff an augmenting trail is discovered. So $d({\varepsilon\dot{\alpha}})$ returns if no augmenting trail is discovered. The discussion following Lemma 4.7 will show $\alpha$ remains free for the rest of the algorithm.

We make some conventions to justify the terminology for $\cal T$. As usual we call $\cal T$ a search tree even though it is a forest (each search starts at a different root). Also we allow $\cal T$ to contain loops $xx$ (added in grow steps). Similarly we allow the path $P$ in a blossom step to contain loops.

We continue discussing the blossom step. Fig.6 is a high level illustration of the structure of the three types of blossoms in $d$. In the blossom base test, it is unclear why the pop routine returns the correct edge (i.e., it may have the wrong M-type). Lemma 4.1 will show correctness. In the blossom enlarge test note $z\dot{x}$ is in a blossom is easily checked. Also let us informally explain this test (the explanation is proved rigorously below). The possibility that $z\dot{x}$ is in a blossom covers ordinary blossoms (the possibility holds when either $z\dot{x}$ is already the base vertex of a blossom, or $zx$ or its reverse occurs on the blossom path). The possibility that $z\dot{x}$ is not in a blossom but $w\dot{x}$ is holds for skew blossoms. Next note that in the blossom step we identify each arc of $P$ by its nodes in $\cal T$. The blossom step may have $P$ empty, specifically $B_{{y\dot{x}}}=B_{{z\dot{x}}}$. We call such a blossom step a noop since nothing changes (there are no $B_{{u\dot{v}}}$ merges or $d({v\dot{u}})$ invocations). An invocation $d({x\dot{y}})$ in a grow step adds $xy$ to $\cal T$, but $d({v\dot{u}})$ in the blossom step does not cause a similar addition. So the call chain of $d$ can be a proper subset of the current search path. (More precisely, an invocation $d({z\dot{x}})$ in the current call chain has the corresponding arc $xz$ or $zx$ in the current search path. Within blossoms, the call chain may omit search path edges.)

For more motivation let us explain the restriction on $uv$ in the blossom-invocation loop. (The explanation gets rigorously proved in our analysis below.) Let $ab$ be the first arc of $P$, i.e., $d({a\dot{b}})$ is not called in the blossom-invocation loop. ($x=a$ in Fig.6(a) and (c).) Let $B$ denote the blossom being formed. Consider two cases.

Suppose the first node of $P$ is not in a blossom. This means $B$ is either the first blossom formed with base edge $zx$, or $B$ is a skew blossom (Fig.6(a) or (c)). There is no need to invoke $d({a\dot{b}})$ because the edges of $GL(x)$ have all been scanned before the blossom step. (In Fig.6(a) the scanning occurs because of edges $zx$ and $yx$. In Fig.6(c) the scanning occurs in blossom $A$ or some subblossom.)

Suppose the first end of $P$ is in a blossom $A$ (Fig.6(b)). (We remark that this implies the last end of $P$ is also in $A$.) There is no need for $d({a\dot{b}})$ since $a\dot{b}$ belongs to $A$. So just like the skew blossom case, $A$ gives an invocation $d({v\dot{u}})$ with ${v\dot{u}}={a\dot{b}}$ and $\mu(vu)=\mu(ab)$.

We turn to the issue of blossom completeness. A blossom $B$ becomes complete when $\eta(B)$ returns. (Recall there are two possibilities if $\beta(B)$ is a free vertex, say $b$. In a search rooted at $b$, i.e., $b=\alpha$, $\eta(B)$ is the artificial arc $\varepsilon\alpha$. Alternatively $b$ may occur in a search where it is not the root. In that case $\eta(B)$ can be a matched $G$-edge. In both cases $B$ can be completed when $d(\eta(B))$ returns.)

The goal of this section is to show find_trails constructs a valid search structure, i.e., all blossoms are valid and all search paths are alternating [14]. We adopt this as an invariant maintained by the algorithm:

All the proofs and other arguments in this section make the implicit assumption that all previous steps satisfy (I1). We explicitly prove (I1) for every step that modifies the search structure. As part of this analysis we will verify that the algorithm is well-defined. Specifically, in the blossom step it is unclear why the path $P$ exists for arbitrary $yx\in BL(x)$. The other statements of the algorithm present no problems in terms of their meaning.

We start with a fundamental concept of the algorithm. Consider a vertex $x$. Let $d({z\dot{x}})$ be the first invocation of $d$ for $x$ that returns. Define $e_{1}(x)$ to be the edge $\{z,x\}$. This definition requires that $d({z\dot{x}})$ is not terminated. For example an invocation $d({\varepsilon\dot{\alpha}})$ that gives an unsuccessful search makes $e_{1}(\alpha)=\varepsilon\alpha$. If every search for a vertex $x$ is successful then $e_{1}(x)$ is an edge of $G$ reached in a search rooted at some free vertex $\neq x$. $e_{1}(x)$ need not exist in this case.

$e_{1}(x)$ may be either arc $zx$ or $xz$. In fact we will show the former always holds (Lemma 4.3) but this is not required at the moment. We usually abbreviate $e_{1}(x)$ to $e_{1}$ when context establishes the identity of the node $x$.

We begin the analysis by showing correctness of the pop routine.

If the blossom base test is satisfied then $BL(x)$ is nonempty so $e_{1}(x)$ exists. Suppose for contradiction that $\mu(zx)=\mu(e_{1})$. Let $xy$ be the edge that satisfies the blossom test, i.e., $xy\in BL(x)\cap\overline{\mu}$. So $\mu(xy)=\overline{\mu}(zx)=\overline{\mu}(e_{1})$. $d({y\dot{x}})$ has returned (since $xy\in BL(x)$). $e_{1}$ was added to $BL(x)$ before $d({y\dot{x}})$ returned (by definition of $e_{1}$. Also $e_{1}\neq yx$ since the edges have opposite M-types.) So $d({y\dot{x}})$ satisfied the blossom test before $d({z\dot{x}})$. This triggered the operation pop$(BL(x))$, contradiction. $\Box$

A blossom has a simple structure in $\cal T$:

Let $d({z\dot{x}})$ be the invocation that forms blossom $B$. Suppose the blossom base test is satisfied. $P$ is the path from $z\dot{x}$ to $B_{{y\dot{x}}}$. So $z\dot{x}$ is $\beta(B)$ and $zx$ is $\eta(B)$, as claimed in the lemma. Suppose the blossom enlarge test is satisfied. By induction $z\dot{x}$ is $\beta(B_{{z\dot{x}}})$ before the merge of $B_{\cdot}$ values. As in the blossom base test, $z\dot{x}$ remains $\beta(B)$. $\Box$

Now we continue to investigate $e_{1}(x)$. In a slight abuse of notation we write $d(e_{1}(x))$ to denote $d({z\dot{x}})$ for the invocation defining $e_{1}(x)$. We next show this invocation is for a $\cal T$-arc $zx$. More generally, every invocation for an occurrence of $x$ in the call chain to $d(e_{1}(x))$ corresponds to a $\cal T$-arc. Fig.5(f) illlustrates this with arcs $z_{i}x$, $i=1,\ldots,4$, $z_{4}x=e_{1}(x)$, as well as $b^{\prime}z_{4}=e_{1}(z_{4})$.

Let $ax$ be the parent arc of $xz$. ($ax$ may be the artificial arc $\varepsilon\alpha$.) We analyze two cases depending on whether $d({a\dot{x}})$ returns before or after ${a\dot{x}}$ has entered a blossom.

Let $yx\in BL(x)$ be the edge triggering the blossom step that makes $a\dot{x}$ a base. $yx$ was added to $BL(x)$ when $d({y\dot{x}})$ returned. So $yx$ returns before $a\dot{x}$ becomes a base vertex. This is before blossom $B$ is formed. So it is before ${a\dot{x}}={z\dot{x}}$ is in a blossom. Thus it is before $d({z\dot{x}})$ is invoked. So $yx$ is the desired edge $wx$. $\Box$

Consider the special case of the lemma for occurrences of $x$ in searches before $d(e_{1}(x))$ is invoked. Every such occurrence of $x$ is on a trail of ${\cal A}$. In proof, suppose $zx$ is the arc leading to the occurrence of $x$. The corresponding invocation $d({z\dot{x}})$ does not return before $d(e_{1})$ returns (definition of $e_{1}$). So it is terminated, i.e., $zx$ is on the augmenting path. Furthermore $zx$ is not in a blossom (that would also imply $d({z\dot{x}})$ has returned). So $zx\in E({{\cal A}})$ as claimed.

The next result establishes the significance of $e_{1}$. We extend our notational convention to abbreviate $\mu(e_{1}(x))$ to $\mu$ when $x$ is clear. Let ${\cal A}$ be defined when $d(e_{1})$ is invoked, i.e., ${\cal A}$ contains the augmenting trails in the searches before $e_{1}$ is reached.

Lemma 4.11($iii$) extends ($i.a$) to describe the ancestors of $e_{1}$ after $e_{1}$ is popped. In Fig.5(d.2) the leaf occurrence of $v$ illustrates ($i.b$).

We later prove that ($ii$) holds without the requirement on $\mu(zx)$.