A distributed blossom algorithmfor minimum-weight perfect matching

2025-04-30 0 0 1.02MB 16 页 10玖币

侵权投诉

A distributed blossom algorithm

for minimum-weight perfect matching

Eric C. Peterson∗

Eigenware

Berkeley, CA, USA

peterson.eric.c@gmail.com

Peter J. Karalekas∗

Eigenware

Berkeley, CA, USA

peter@karalekas.com

ABSTRACT

We describe a distributed, asynchronous variant of Edmonds’s

exact algorithm for producing perfect matchings of minimum

weight [

Edm65a

]. The development of this algorithm is driven

by an application to online error correction in quantum com-

puting, rst envisioned by Fowler [

FWH12

]; we analyze the

performance of our algorithm as applied to this domain in a

sequel [PK].

1 INTRODUCTION

Edmonds’s now-classic results on maximum matchings lie at

the intersection of computer science, combinatorics, and inte-

ger linear programming: starting from a known polynomial-

time algorithm for producing maximum matchings in bipar-

tite graphs [

CCPS09

, Proposition 5.7], he showed rst that a

polynomial-time modication could be used to handle a non-

bipartite graph [

Edm65b

], then that in the presence of edge

weights another polynomial-time modication could be used

to produce a minimum-weight representative among maxi-

mum matchings [

Edm65a

]. These are respectively called the

“blossom algorithm” and the “weighted blossom algorithm”.

These landmark results set in motion broad research programs

in several domains: there are theoretical consequences in both

computer science and mathematics; the algorithmic technique

itself admits both generalizations and eciency improvements;

and it opened the door to a host of applications.

As an example of such an application, minimum-weight per-

fect matchings (MWPMs) attracted the attention of quantum

computer scientists, who showed that an MWPM solver can be

used as an approximation algorithm for decoding syndromes

appearing in quantum error correction, with approximation

ratio dependent on the physical properties of the underlying

quantum device [

DKLP02

]. This idea has taken such hold with

designers of quantum computers that it has appeared in a vari-

ety of surveys on the subject (see, e.g., [

FMMC12

CNAA+20

])

as a solved problem. However, in order to deploy this on a live

quantum device, Fowler showed that one must make use of a

“parallelized” MWPM solver [

FWH12

], and work has stopped

short of producing (or referencing) such an algorithm.

Careful consideration of the intended application indicates

that the “parallelized” implementation must actually be dis-

tributed with only local information available to each worker,

online so as to cope with a dynamic problem graph, and ideally

asynchronous to best match lab hardware. Meanwhile, though

state of the art in MWPM solvers has advanced substantially

since the ’60s, they have had other concerns top of mind: it

∗All work was done prior to joining Amazon Web Services.

is easy to show that the worst-case complexity of an exact

solution to the matching problem on a cycle graph has runtime

polynomial in the diameter [

Lin92

], which has encouraged the

development of approximation algorithms instead ([

WW04

[LPR09], [LPP15], and many others).

In this paper, driven by the extra structure available on the

problem graphs in our intended application, we return to the

exact setting: we describe an exact, asynchronous distributed

blossom algorithm suitable for fullling Fowler’s claim and

prove its correctness. As part of extending Edmonds’s algo-

rithm to operate on alternating forests rather than trees, we

draw the reader’s attention to a new, naturally-occurring forest

operation which we call multireweight, which does not arise

during serial execution and which is crucial to the correctness

of the distributed algorithm. We also provide an implemen-

tation of the algorithm,

anatevka

[

ana

Ale49

], as part of a

simulation testbed for distributed systems described in a pre-

vious paper [

PK20

aet

]. We make no reference to quantum

computing outside of this introduction, since the existence and

behavior of this algorithm is entirely a matter of distributed

computing. Instead, we direct interested readers to the se-

quel paper [

] for the further modications necessary to the

application and the performance analysis in that context.

2 THE SERIAL ALGORITHM

Our distributed algorithm is most easily cast as a piecewise

modication of Edmonds’s serial blossom algorithm, with one

extra operation. To facilitate such a description, and to put

the unfamiliar reader at ease, we rst review the details of the

serial algorithm. The inputs and output of the problem are:

Denition 1.

Amatching

𝑀

on a graph

𝐺

is a set of edges

with no repeated vertices. A matching is maximum when it is

of maximum cardinality. A maximum matching on

𝐺

is perfect

when

𝐺

has an even number of vertices. For edge-weighted

𝐺

, a matching is said to be minimum weight if there is no

equal-sized matching with smaller edge weight sum.

The goal is to produce minimum-weight perfect matchings.

Remark 2 (Standing assumptions on

𝐺

).Initially, we will as-

sume

𝐺

to be unweighted and bipartite, though we will drop

these assumptions as our discussion progresses. Between any

pair of vertices in

𝐺

, we permit there to be no edges, one edge,

or several edges—but since a loop can never be a match edge,

it is harmless to assume that

𝐺

is loopless. For the purposes of

our description, it is convenient to permit the case of multiple

edges, but it is not necessary: the algorithm will behave as if

there is at most one edge between any pair of vertices (viz.,

the one of least weight). In the weighted setting, one can also

arXiv:2210.14277v1 [cs.DC] 25 Oct 2022

Eric C. Peterson and Peter J. Karalekas

𝑟 𝑠 𝑡𝑢 𝑣 𝑤

⇓

𝑟 𝑠 𝑡𝑢 𝑣 𝑤

Figure 1: The graph on top illustrates an augmenting

path joining 𝑟to 𝑤: neither 𝑟nor 𝑤is matched, and the

edges between them alternate between not belonging

and belonging to the matching. The graph below shows

the eect of augmenting along this path: whether an

edge is or is not a member of the matching reverses, and

the size of the matching increases by one edge.

model missing edges by edges of innite weight, so that the

entire algorithm need only be described for a complete graph.

2.1 Augment and graft

Suppose that we are given a matching

𝑀

, perhaps not yet

maximum. The core mechanism of the algorithm is to identify

an augmenting path:

Denition 3.

We say that an edge is matched if it belongs

𝑀

or otherwise that it is unmatched, and we say that a

vertex is matched if it is the endpoint of any matched edge or

otherwise that it is unmatched. Thus, an alternating chain or

alternating path is a sequence of adjoining edges which alter-

nate between being matched and unmatched. An augmenting

path is an alternating path whose rst and last vertices are

both unmatched.

With such a path in hand, one can produce a new matching

by inverting which edges in the path belong to the matching.

The number of edges in the new matching is one larger than

that of the old.

Denition 4.

This inversion procedure is called augmenting

𝑀along the augmenting path.

Example 5.See Figure 1 for a depiction of augmentation.

The meat of the algorithm is then a search for augmenting

paths, which begin and end at unmatched vertices. The data

structure which powers this is an alternating tree:

Denition 6.

An alternating tree is a tree whose root is un-

matched, and whose edges alternate between unmatched and

matched as they descend from the root. We refer to the even-

and odd-depth tree vertices respectively as positive and nega-

tive, and we write 𝑇+and 𝑇−for these subsets of vertices.1

Denition 7.

The inductive operation used to assemble such

an alternating tree is called grafting.

Let

𝑀

be an intermediate

matching, and let

𝑇

be an alternating subtree of the ambient

graph 𝐺. Select a pair of edges 𝑒and 𝑓, as in

𝑢 𝑣 𝑤

𝑒𝑓,

Some authors refer to positive, negative, and unmatched vertices respec-

tively as outer,inner, and exposed.

2Some authors call this operation grow [Kol09].

𝑟 𝑠 𝑡

𝑢 𝑣

𝑤𝑥

𝑞

𝑒

𝑓𝑔

⇓

𝑟 𝑠 𝑡

𝑢 𝑣

𝑤𝑥

𝑞

𝑒

𝑓𝑔

⇓

𝑟 𝑠 𝑡

𝑢 𝑣

𝑤𝑥

𝑞

𝑒

𝑓𝑔

Figure 2: Begin by grafting a matched edge 𝑓along edge

𝑒onto an alternating tree 𝑇rooted at 𝑟. This creates an

augmenting path (middle, red) formed from a branch

of 𝑇and an edge 𝑔not in 𝑇. Then augment through

this path to produce a maximum matching. Note that

edges participating in the tree carry arrow heads (point-

ing toward the leaves), edges participating in the partial

matching are bold, and the remaining edges are dotted.

with the additional properties that

(1) 𝑢belongs to 𝑇, but 𝑣and 𝑤do not.

(2) If 𝑢has a parent in 𝑇, the edge to that parent is in 𝑀.

(3) 𝑓belongs to 𝑀, but 𝑒does not.

We then dene the graft of this edge pair onto

𝑇

to be the union

𝑇′=𝑇∪ {𝑒, 𝑓 }

. The rst property of the edge pair ensures

that 𝑇′is a tree, and the others ensure that 𝑇′is alternating.

Remark 8 ([

Kuh10

], [

CCPS09

, Proposition 5.7]).Used together,

these operations make up the Hungarian algorithm, Algo-

rithm 1, for producing maximum matchings on bipartite graphs.

Example 9.We illustrate using an alternating tree to nd a

maximum matching on a bipartite graph in Figure 2.

2.2 Contract and expand blossom

We now trade the bipartite assumption for two new tree op-

erations. Consider the situation of Figure 3. The alternating

tree

𝑇

is “maximally grafted”, but no edge emanating from its

positive vertices reaches an unmatched vertex outside of

𝑇

, so

the algorithm of Algorithm 1 cannot make progress. Nonethe-

less, an augmenting path exists: starting at

𝑟

, one can proceed

A distributed blossom algorithm for minimum-weight perfect matching

Algorithm 1: Hungarian algorithm

Data: Bipartite graph 𝐺, intermediate matching 𝑀

Result: Maximum matching on 𝐺

while true do

𝐺𝐿∪𝐺𝑅←a vertex 2–coloring of 𝐺;

𝑇←an unmatched vertex in 𝐺𝐿;

while true do

if there is an 𝑒=(𝑣, 𝑤 )with 𝑣∈𝑇∩𝐺𝐿,

𝑤∈𝐺𝑅,∉𝑀then

augment 𝑇along 𝑒;

break;

else if there is an 𝑒=(𝑣, 𝑤 )with 𝑣∈𝑇∩𝐺𝐿,

𝑤∈𝐺𝑅∩𝑀then

𝑚←match edge for 𝑤;

graft 𝑚onto 𝑇using 𝑒;

else

return;

end

down the lower branch, cross vertically along

𝑒

to the upper

branch, walk backwards through the tree to

𝑢

, and nally cross

𝑓

𝑞

. These cycles, where an edge not in

𝑇

joins two of its

positive vertices, are the essential new complication of the

non-bipartite case. Edmonds’s rst fundamental observation

was that all of the vertices within such a cycle are well-suited

to constructing an augmenting path, and the second was that

incorporating this into the search algorithm permits one to

use it on an arbitrary graph.

Denition 10.

Let

𝑀

be an intermediate matching on

𝐺

, and

let

𝑣∈𝐺

be a vertex. By an alternating cycle rooted at

𝑣

, we

mean an odd-length alternating path

𝐶⊆𝐺

of distinct edges

leading from

𝑣

and returning to

𝑣

We say that we contract a

blossom from

𝐶

when we contract (the full subgraph spanned

by)

𝐶

to a point to produce a new graph

𝐺′=𝐺/𝐶

. We refer

to the vertex

𝐵

𝐺′

which is the image of

𝐶

as the blossom

or the macrovertex.

The graph

𝐺′

inherits a matching

𝑀′

dened through three cases:

(1) If 𝑣is matched in 𝑀,𝐵inherits that match in 𝑀′.

(2)

The matched edges in

𝑀

internal to

𝐶

are discarded, as

they’ve been contracted out of 𝐺′.

(3)

All other matched edges in

𝑀

do not interact with

𝐶

, so

𝑀′inherits them verbatim.

Example 11.In Figure 4 we illustrate macrovertex contraction.

Remark 12.Note that, even if

𝐺

is singly edged (i.e., is not a

multigraph), this need not be the case for the derived graph

𝐺′

after contracting a cycle

𝐶⊆𝐺

to a macrovertex

𝐵∈𝐺′

If there are two distinct vertices

𝑐, 𝑐′∈𝐶

both with edges to

a third vertex

𝑑∉𝐶

, then

𝐵

inherits two distinct edges with

target 𝑑.

In particular,

𝐶

begins and ends with unmatched edges, lest

𝑣

participate

in two matched edges.

4Some authors refer instead to the alternating cycle as the blossom.

𝑟 𝑠 𝑡

𝑢 𝑣

𝑤𝑥

𝑞

𝑓

𝑒

Figure 3: A non-bipartite scenario, where edge 𝑒joins

two positive vertices. From the view of Algorithm 1, it

is illegal to augment along the edge 𝑓because 𝑢is not

positive, hence the path through 𝑇to its root 𝑟is not al-

ternating. However, the edge 𝑒could be used to produce

an augmenting path, in red.

Denition 13.

Conversely, suppose that we are given an

intermediate matching

𝑁′

on a graph

𝐺′

, where

𝐺′

was origi-

nally contracted from a graph

𝐺

along an alternating cycle

𝐶

The matching

𝑁′

can then always be lifted to a matching

𝑁

𝐺

, called the expansion of

𝑁′

along

𝐶

. Namely, note that the

macrovertex participates in at most one matched edge in

𝑁′

which can be identied uniquely with an edge in

𝐺

incident

on some vertex

𝑤∈𝐶

. By rotating the alternating pattern of

matches within

𝐶

so that the successive pair of unmatched

edges is joined at

𝑤

, and otherwise inheriting the matched

edges from 𝑁′, we obtain a matching on 𝑁.

Example 14.We illustrate match expansion in Figure 5.

Remark 15 ([

Edm65b

], [

CCPS09

, Theorem 5.10]).As promised,

we use these operations to extend Algorithm 1 to cover non-

bipartite graphs. We also modify the termination condition:

given a maximally-grafted alternating tree

𝑇⊆𝐺

, if it does

not admit any exiting edges along which we may augment,

we additionally search for unmatched edges between positive

vertices in

𝑇

. If such an edge is present, then we use it to form a

minimum alternating cycle

𝐶

within

𝑇

, and contract that cycle

to form a new graph

𝐺′

with matching

𝑀′

. By contracting

𝑇

along

𝐶

, we also produce a new alternating tree

𝑇′

𝐺′

and we proceed to run the matching algorithm from this new

state.

When this recursion returns, we either lift the modied

matching on

𝐺′

to a modied matching on

𝐺

(via macrovertex

expansion) and restart the outer loop, or we proceed to try the

next unmatched vertex as a root.

Remark 16.Representing a contracted graph in memory is

somewhat onerous. In particular, the algorithm described in

Remark 15 may involved nested contractions, where a vertex

becomes contracted into a macrovertex, which in turn becomes

contracted into another macrovertex, and so on. We defer

discussion of this point to Section 3.4, where we will describe

it in full in the setting most relevant to this paper.

5Some authors call this the derived graph and derived state.

Eric C. Peterson and Peter J. Karalekas

𝑟 𝑠 𝑡

𝑢 𝑣

𝑤𝑥

𝑞

𝑓

𝐵

⇓

𝑟 𝑠 𝑡

𝑢 𝑣

𝑤𝑥

𝑞

𝑓

𝐵

Figure 4: Continuing from Figure 3, we contract the cy-

cle formed by the edge 𝑒into a macrovertex 𝐵. This

causes 𝑓to be attached to a positive vertex in 𝐺′, and

hence it participates in an augmenting path. Note that

edges in the contracted cycle are curved solid lines.

2.3 Reweight

Finally, Remark 15 can be extended to produce maximum

matchings of minimum weight by housing it in a “primal-dual

update” scheme [

DFF56

]. Speaking very loosely, the dual step

sorts the edges not yet considered by the amount of weight

their participation would incur, and the primal step consists

of Remark 15 as applied to these minimally-sifted graphs.

Denition 17.

The internal weight of a (macro)vertex is a

numeric value managed by the dual step. The adjusted weight

of an edge is its weight after subtracting the internal weights

of its two endpoints and those of any macrovertices to which

they belong. The weightless subgraph

𝐺◦

is then the maximal

subgraph with the same vertices but retaining only edges of

adjusted weight zero.

Remark 18 ([

CCPS09

, Theorem 5.20]).The internal weight of

a vertex may be negative. However, if the edge weights of a

graph are all nonnegative, then so are the algorithm’s internal

weights and adjusted edge weights.

Denition 19.

Let

𝐺

be an edge-weighted graph with inter-

nal vertex weights,

𝑀

an intermediate matching on

𝐺◦

, and

𝑇

an alternating tree in

𝐺◦

. The reweighting of

𝑇

is an update

to the internal weights of

𝐺

given by increasing the internal

weights of the positive vertices

𝑇+

and decreasing the internal

weights of the negative vertices

𝑇−

by the amount given by

the minimum of the following three sets:

𝑡

𝑢 𝑣

𝑤𝑥

𝑝

𝑟

𝐵

⇓

𝑡

𝑢 𝑣

𝑤𝑥

𝑝

𝑟

Figure 5: Beginning with a scenario similar to that of

Figure 4, but with 𝐵in a negative position, we demon-

strate the eect of macrovertex expansion. The edges

within the cycle are tagged as matched edges so as to

provide an alternating path from the root to the leaf,

and edges not along that path are ejected from the tree.

Graft/augment candidates

The adjusted edge weights of

edges in 𝐺joining vertices in 𝑇+to vertices not in 𝑇.

Contract candidates

The adjusted edge weights of edges in

𝐺

, scaled down by half, joining vertices in

𝑇+

to each other.

Expand candidates

The internal weights of vertices in

𝑇−

which are macrovertices.

This enlarges 𝐺◦while maintaining the weightlessness of 𝑇.

The edge-weighted blossom algorithm is then given by

applying the non-bipartite blossom algorithm to

𝐺◦

, with the

additional step that the alternating subtree should attempt a

reweight operation before the loop gives up and moves on to

the next candidate root vertex.

Example 20.We illustrate a sample run of this algorithm in

Figure 6.

2.4 The main loop

Altogether, these operations make up the serial blossom algo-

rithm, Algorithm 2, for producing minimum-weight maximum

matchings on edge-weighted graphs.

Remark 21.To simplify the outer loop slightly, we have as-

sumed while writing Algorithm 2 that

𝐺

is fully connected

with an even number of vertices. This means that all of the

vertices will participate in a maximum (perfect) matching, and

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Adistributedblossomalgorithmforminimum-weightperfectmatchingEricC.Peterson∗EigenwareBerkeley,CA,USApeterson.eric.c@gmail.comPeterJ.Karalekas∗EigenwareBerkeley,CA,USApeter@karalekas.comABSTRACTWedescribeadistributed,asynchronousvariantofEdmonds’sexactalgorithmforproducingperfectmatchingsofminimumweig...

展开>> 收起<<

A distributed blossom algorithmfor minimum-weight perfect matching.pdf

共16页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A distributed blossom algorithmfor minimum-weight perfect matching

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: