When explaining the Blossom algorithm for maximum (nonbipartite) matchings, Shrijver describes, given a simple graph $G = (V,E)$, a matching $M \subseteq E$, and the set $X \subseteq V$ of nodes missed by $M$:

A walk $P = (v_0, v_1, \dots, v_t)$ is called $M$-alternating if for each $i = 1, \dots, t - 1$ exactly one of the edges $v_{i - 1}v_i$ and $v_iv_{i + 1}$ belongs to $M$. Note that one can find a shortest $M$-alternating $X-X$ walk of positive length, by considering the auxiliary directed graph $D = (V,A)$ with $$A := \{(u,v) \mid \exists x \in V : ux \in E, xv \in M \}.$$ Then each $M$-alternating $X-X$ walk of positive length yields a directed $X-N(X)$ path in $D$, and vice versa (where $N(X)$ denotes the set of neighbors of $X$).

(Walks are sequences of nodes which may contain duplicate nodes, and $v_iv_{i + 1} \in E$.)

I am not entirely clear on 1) the correspondence between $M$-alternating $X-X$ walks in $G$ and directed $X - N(X)$ paths in $D$, and 2) what exactly the algorithm is for finding the shortest $M$-alternating walk in $G$.

  1. If a directed path in $D$ begins in $X$ and ends in $N(X)$, how does that uniquely correspond to a sequence of nodes which begins in $X$ and ends in $X$?

    EDIT1: I now realize a directed path in $D$ need not begin in $X$, but it is my understanding that we consider only such paths to find augmenting paths in $G$.

    EDIT2: I now also realize the answer is pretty obvious: if the path in $D$ ends on $N(X)$, that last node is neighbors with a node in $X$. Thus appending that neighbor to the walk yields an $X-X$ walk.

  2. My first idea is to apply BFS from each node in $X$ to compute all shortest $X - N(X)$ paths (since $D$ is unweighted). Then, the path with the shortest length (number of edges) is the one we select to represent our shortest walk. This feels inefficient, but no alternative is specified in the text. Does anyone have an idea of what algorithm Shrijver may be hinting at here?

I understand asking multiple questions is frowned upon, but these are closely related.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.