数理解析研究所講究録
第 1799 巻 2012 年 1-12

1

2011 年度冬の LA シンポジウム [1]完全マッチング数え上げの
高速な指数時間アルゴリズムについて
泉泰 介 *

和田山正$\dagger$る [7]. 上記の困難性のため，完全マッチング計数問
題は主に 1) 近似アルゴリズムの設計，2)(高速な)与えられたグラフにおける完全マッチングの個数 指数時間アルゴリズムの設計，の 2 アプローチからの計数することは数え上げ問題における代表的な困 研究されている．本研究は，特に同問題に対する指概要

難問題であり，グラフを 3-正則二部グラフに制限し 数時間アルゴリズムの設計に着目する．
たもとでも $\#P$ -完全であることが知られている．本二部グラフに対する完全マッチング計数 (すなわ
研究は，3-正則二部グラフの完全マッチング計数問 ち，パーマネントの計算) のための指数時間アルゴ

題に対する，$\tilde{O}(2^{5n/12})$時間の多項式メモリスペース

リズムとして最もよく知られているものは，Ryser
アルゴリズムを提案する．このアルゴリズムは，グ によるアルゴリズムである [21]. このアルゴリズム
ラフの閉路空間およびカット空間に対する符号理論 は，包除原理を利用することで，完全マッチングの的な解釈に基づいており，線形符号における主符号 個数を項数の閉じた多項式で表現できるという$2^{n/2}$と双対符号の間の関係式 (マックウィリアムス恒等式 を利用して完全マッチング計数問題をカットの$)$重み分布計算に帰着することで高速なアルゴリズムを実現している．

1

事実を利用しており，その計算時間は$\tilde{O}(2^{n/2})$,

メ

モリ使用量は poly $(n)$ ビットである 1. Ryser のアル
ゴリズム以降 計算時間がを下回る二部グ$\tilde{O}(2^{n/2})$

ラフの完全マッチング計数アルゴリズムについては

はじめに入力として与えられたグラフ $G$ に対して，その完

全マッチングの個数を計数する問題は数え上げ問題
において重要な意味を持つ基本問題である．特に，が二部グラフの場合における完全マッチングの計数
行列の 0-1 パーマネントの計算と等価であは，ることが知られている．パーマネント計算は統計物$G$$n\cross n$

長い間考えられていなかったが，2002 年に Bax とFranklin による期待計算時間 $\tilde{O}(2^{n/2-o(n)})$ , メモリ
使用量 poly $(n)$ ビットの乱択アルゴリズムが示された [2]. このアルゴリズムは Servedio と Wan により計算時間$\tilde{O}((2-\epsilon)^{n/2})$の決定性アルゴリズムに改良されている [22]. ここで$\epsilon$

はグラフの辺密度 $m/n$

により決まる値である．特にグラフが 3-正則の場合，となり，Servedio と Wan のアルゴリズム$\epsilon=.0.002$

は時間計算量 $\tilde{O}(1.4135^{n})$ となる．多項式メモリス

理学等で重要な応用を持つが，その計算は $\#P$-完全 ペースのアルゴリズムとしては，この結果が 3-正則と呼ばれる困難問題のクラスに属しており [24],の多項式時間で値を計算することはほぼ絶望視されている．また，この困難性はグラフを 3-正則二部グ
ラフに制限したもとでも成立することも知られてい
$n$

$*$

$\dagger$

名古屋工業大学大学院情報科学研究科
第

$1$

著者に同じ

二部グラフに対する現時点での最速アルゴリズムである．指数メモリスペースを利用することを許した

場合，3-正則グラフのパス幅の上界が $n/6$ であるという事実 [9] と，木幅に対する固定パラメータ容易$1o^{-}(f(n))$ は，通常のオーダ記法から $f(n)$ に対する対数オーダの因子 (すなわち polylog $(f(n))$ ) を省略した記法である．

2時

マッチング計数問題と線形符号の関係について述べ

本研究では，グラフの完全マッチング計数に対する新たなアプローチを提案する．提案する手法の基る．この節において完全マッチング計数問題のカット重み分布への帰着を与える．6 節ではカット重み
時間アルゴリズムを与分布の計算を行う盤となるアイデアは，入力として与えられたグラフ

える．最後に 7 節において本論文の結果のまとめをに対応する閉路空間およびカット空間を線形符号と述べる．

見なすことで，符号理論における手法を利用して完
全マッチング計数問題をカット空間の重み分布計算に帰着することである．より具体的には，提案手法
は以下の 3 つの事実から構成されている．

2

アルゴリズム [1] と組み合わせることで，$\tilde{O}(2^{n/6})$

間のアルゴリズムを得ることができる．

.

任意のグラフ $G$$\tilde{O}(2^{5n/12})$

関連研究

前節で述べた通り，完全マッチングの数え上げにに対して，定数個の頂点および ついては，近似アルゴリズムの設計，および (指数$G$ と完全
高々 $n+1$ 本の辺を追加することで，マッチングの個数が等しい奇グラフ$\hat{G}$を構成で時間) 厳密アルゴリズムの両面から研究されてきた．
二部グラフに限定した場合の結果については既に述べているので，本節では，一般のグラフおよび二部
グラフ以外のグラフクラスに対する完全マッチング
計数問題，およびその計算困難性についての話題をことで， と完全マッチングの個数が等しい奇きる．また，任意の二部グラフ に対して，定数個の頂点および高々 $n+5$ 本の辺を追加する
$G$

$G$

.
.

グラフ

$\tilde{G}$を構成できる．

述べる．

二部グラフの完全マッチング計数がパーマネント
計算との関連から比較的古くより研究されてきたこッチングの数が，閉路空間における重み $m-n/2$ とに対し，一般のグラフに対する完全マッチングのの符号語 (すなわち，辺数 $m-n/2$ の閉路空間
計数については自明なアルゴリズム (頂点集合の均中の要素) の数に等しい．
等二分割を全列挙するアルゴリズム) より真に高速な閉路空間およびカット空間の間に主双対関係が アルゴリズムについてはあまり検討されていなかっあり，符号理論における主符号および双対符号 た．しかし，近年，Bj\"orklund と Husfeldt により [5],頂点数 , 辺数 $m$ の奇グラフにおいては，完全マ$n$時間の多項式メモリスペースアルゴリズム，
時間の指数メモリスペースアルゴ
クウィリアムスの恒等式) を利用することで，閉 およびリズムが示されて以降，急速にその計算量が改善さ路空間における重み $m-n/2$ の符号語数の計算をカット空間の重み分布計算に帰着することが れている．Koivisto は指数メモリスペースアルゴリの間の重み分布に関して成立する関係式 (マッ$O(\tilde{2}^{n})$$\tilde{O}(1.733^{n})$可能である．

上記は一般のグラフにたいして成立する事実である．本研究では，それに併せて，3-正則二部グラフ
に対するカット空間の重み分布を，多項式メモリス
ペース
時間で計算するアルゴリズムを提案する．このことは同時間，同メモリ使用量で 3-正則二部グラフに対する対する完全マッチングの数え$\tilde{O}(2^{5n/12})$ズムにおける上記の計算量を$\tilde{O}(1.618^{n})$時間に改善

し [17], Nederlof は多項式メモリスペースアルゴリズ

ムの上界を $\tilde{O}(1.942^{n})$ に改善している [18]. Nederlof

はまた，サイズ の独立点集合を持つグラフについ時間で動作するアルゴリズムを示していて，る [19]. ごく最近，Bj\"orklund により，上記のアルゴ$i$$\tilde{O}(2^{n-i})$

リズムすべての性能を上回る，$\tilde{O}(1.414^{n})(=\tilde{O}(2^{n/2})$

時間，多項式メモリスペースのアルゴリズムが示された [4].
本論文の構成は以下の通りである．まず，次節に制限されたグラフクラスに対する多項式時間厳密て関連研究を述べたのち，3 節にて線形符号に関す
アルゴリズムの構成についてもいくつかの研究が試る基本的な事項を述べる．4 節および 5 節にて完全上げが可能であることを意味する．

3
みられている．代表的な結果として，平面グラフに対する多項式時間完全マッチング計数アルゴリズム [16]ベクトルにより張られる線形部分空間と見なすことができる．なお，一般には各行が一次独立でないよ
うな生成行列 $M$ も考えることができ，そのような
場合 $C$ の次元は より小さくなる (すなわち，符号が挙げられる．この結果は，制限された種数を持つ
グラフ [10,23], 制限された木幅を持つグラフ [1] な$n$どに一般化されている．また，コーダルグラフとそのサブクラスについての計算困難性の考察が Okamoto

語の個数が減少する). 線形符号 $C$ の符号語の個数$C$ が $M$ の行ベクトルにより張られるを $|C|$ で表す．

ら [20] によって行われている．

線形部分空間をであることから，$|C|=2^{rank(M)}$ と完全マッチング計数問題に対する近似計算は，大 なる． の次元が であるような符号語長 $m$ の線形
きく分けて 2 つのアプローチが考えられている．$-$ 符号を特に $(m,d)$ -線形符号と呼ぶ．
$C$

つ目はマルコフ連鎖モンテカルロ法 (MCMC 法) を利用するアプローチであり，Jerrum らによる同問題
への多項式時間乱択近似スキーム (FPRAS) が代表的なアルゴリズムとして知られている [13,14]. この
結果は Beza’kova’ らにより計算時間が改善されている [3]. 二つ目のアプローチは行列式の計算への帰着に基づく手法である [11,15,6]. この路線における現在最良の結果は Chien らによる計算時間 $O(1.2^{n})$の近似アルゴリズムであり [6], 多項式時間乱択近似$d$

線形符号 $C$ に含まれる任意の符号語 $w\in C$ について $w^{T}H=0$ を満たす $m\cross$ ( $m-$ rank $(M)$ ) 行

列 $H$ を，符号 $H$ の検査行列と呼ぶ．生成行列 $M$ と検査行列 $H$ の間には双対関係があり，検査行列 $H$

において，任意のについて定義より $v^{T}M=0$ である．すなわ$M$がち，の検査行列となる．このように定義さを生成行列として定めた符号$C^{\perp}$$v\in C^{\perp}$$C^{\perp}$

れる符号$C^{\perp}$

は元の符号 $C$ の双対符号と呼ばれる．

の任
なお， を符号 $C$ の任意の符号語， をスキームが構成可能であるかどうかは現時点では未 意の符号語とすると，定義より明らかに $v^{T}v^{\perp}=0$解決の問題である．
が成立する．すなわち主符号の符号語と双対符号の完全マッチング計数に対する時間アルゴ 符号語は直交しており，このことから双対符号は主リズムの存在性についての研究は，Dell らによる結 H 号の直交補空間をなす事がわかる．
果 [8] が知られている．この結果では SAT に対するある符号語における 1 の個数を，その符号語の重指数計算量仮説 (ETH) [12] を仮定した場合 2,1 の みとよぶ．以降，符号 $C$ における重み の語の個数
個数が $m$ 個であるような疎行列の 0-1 パーマネント を $A_{C}(k)$ で表す．各重みを持つ符号語の個数を並べ計算が $\Omega(exp(m/\log m))$ の時間下限を持つことが示 て得られるベクトル $\{A_{C}(k)\}$ を符号 $C$ の重み分布$v^{\perp}$$v$$C^{\perp}$$\tilde{O}(2^{o(n)})$

$|$

$k$

$|$

されている．

と呼ぶ．また，重み分布 $A_{C}(O),$ $A_{C}(1),$$1$$\ovalbox{\tt\small REJECT}$

符号理論からの準備

2 元有限体 F2 上の $n\cross m$ 行列 $M$ によって生成される線形符号 $C$ とは，以下の集合によって定められの重み分布多項式と呼ぶ．
主符号 $C$ と双対符号の重み分布多項式の間には，以下のような関係が成立することが知られて$C^{\perp}$$1$

い$t\backslash$

る $n$ 次元ベクトルの集合である．
$\not\in$$J*$る．

理 1(マックウィリアムスの恒等式) 語長 $m$ の線

7 // 符号に対する重み分布多項式 $F_{C}(x)$ , およびその双対符号の重み分布多項式に対して，$\acute$$\dagger\dagger$$C=\{Mv|v\in F_{2}^{n}\}$$($このとき，行列 $M$ は符号言い換えると，線形符号

$C$

$C$

$C$

$C^{\perp}$$F_{C^{\perp}}(x)$の生成行列と呼ばれる．1 下の関係が成立する．
$\iota$$\grave\lambda$-

は，生成行列 $M$ の各行$F_{C}(x)= \frac{1}{|C^{\perp}|}(1+x)^{m}F_{C}\perp(\frac{1-x}{1+x})$2 実際には．ETH をより弱めた仮説である，SAT 解の個数の計数が指数時間かかるという仮説 (#ETH) を仮定している．

$A_{C}(m)$こ対する母関数 $F_{C}(x)= \sum_{w=0}^{m}A_{C}(z)x^{w}$ を，符号

$C$
$1$

3

$\cdots$4
この恒等式について係数比較をすることで，主符すことができる．よって，以降の議論では，グラフ号と双対符号の重みについての以下の関係式を得るのカット空間および閉路空間を線形符号の一種と見ことができる．なし，特に断り無く符号理論の用語を用いる．また，「カット空間 (あるいは閉路空間) の符号語」という$m$$A_{C}(i)= \frac{1}{\perp}\sum K_{m}(j, i)A_{C}\perp(j)$$|C|_{j=0}$

言葉は，それに対応するカット辺の集合 (あるいは対応する全域部分偶グラフ) のことを指す場合がある．

以下はカット空間および閉路空間の間の関係とし

ここで $K_{m}0,i)$ は Krawtcbouk 多項式と呼ばれる式てよく知られている事実である．

であり

事実 1 カット空間および閉路空間は互いに相手の直$K_{m}.(j,i)= \sum_{k=0}^{m}(-1)^{k}(\begin{array}{l}ik\end{array})(\begin{array}{l}-mij-k\end{array})$

交補空間である．
と定義される．

4

カット空間および閉路空間

この事実は，任意のカットは閉路を構成する辺を偶数回横切る (すなわち，偶数個の共通辺を持つ) ことから直感的に理解できる．符号理論的な観点から見た場合，この事実はカット空間に対応する線形符

本節では行列，ベクトルの要素および計算はすべ 号および閉路空間に対応する線形符号の間に主双対て F2 上の演算であるとする．無向グラフ $G=(V, E)$に対して，その接続行列$M_{G}$

は以下のように定義さ$C(G)$ をの閉関係があることを意味する．以降，を同カット
路空間に対応する線形符号とし，$G$$C^{\perp}(G)$空間に対応する線形符号とする．

れる．

$A_{G}(i,j)=\{\begin{array}{l}1if i \text{が} i \text{の} \ovalbox{\tt\small REJECT} \text{点}0 \text{それ}\iota\grave An\end{array}$

今， の頂点の部分集合 $S\subset V$ を表す 次元の
0-1 指標ベクトル vs を考える．このとき，よく知ら. vs は頂点$m$ 次元ベクトルれた事実として，$G$

5

カット重み分布を利用した完全マッチングの数え上げ

51

一般のグラフの場合$n$$M_{G}$

集合 $V$ を $S$ と $V-S$ に分割するカットの辺集合を連結グラフ $G=(V, E)$ の完全マッチングの数え上げを考える．以降の議論では $|V|=n,$ $|E|=m$ とし，また は偶数であるとする (奇数の場合は明らかに完全マッチングは存在しない). 頂点 $v\in V$ の表す．よって，グラフ の接続行列を生成行列とし$G$ のカット辺集合に対応すて得られる線形符号は，る指標ベクトルすべてからなる空間と一致する．以下，この符号に対応する線形部分空間をカット空間 次数を $d(v)$ で表すとする．このとき，以下の定理が
$G$

$n$

とよぶ．

成立する．
における単純閉路に対応する $m$ 次元指標ベクト$G$ の完全マッを奇グラフとする．このとき，
ルすべてを行ベクトルとして並べた行列を，タイセッ 補題 1
ト行列と呼び，タイセット行列の行ベクトルの一次 チングの個数は閉路空間 $C(G)$ における重み $m-n/2$結合で表せる線形部分空間のことを閉路空間と呼ぶ． の符号語の個数に等しい．
$G$

$G$

閉路空間は，全頂点の次数が偶数であるような全域の各頂点
証明,Vn-l に対する次数
部分グラフ (の辺集合を表す指標ベクトル) すべてか$d(v_{0})-1,d(v_{1})-1,$ $\cdots,d(v_{n-1})-1$ である
らなる空間である．カット空間と同様に，閉路空間 系列がような の全域部分グラフ $G’=(V, E’)$ を考える．
もタイセット行列により定義される線形符号と見な
$G$

$G$

$v_{0}\cdot,v_{1},v_{2},$$\cdots$

5
このとき，辺の補集合により誘導される部分グラフ
における全頂点の次数は 1, すなわち完全
マッチングとなる．また， 上の任意の完全マッチ$(V, E\backslash E’)$$G$

ングに対して，その辺の補集合は明らかに次数系列$d(v_{0})-1,$ $d(v_{1})-1,$ $\cdots,d(v_{n-1})-1$を持つ．すなわち，そのような次数系列を持つ全域部分グラフと完
全マッチングは一対一対応づけられる．よって，証明は，任意の重み $m-n/2$ の符号語 について，そ
$v$

へ

$G$

れに対応するグラフ $G(v)$ の頂点次数系列が $d(v_{0})-$

1, $d(v_{1})-1,$$\cdots,$$G$となることを示せば十$d(v_{n-1})-1$

図 1:

分である．

$\hat{G}$の構成例

証明は背理法による． を重み $m-n/2$ の符号語と$v$$G(v)$ の次数系列を
し，

ある頂点

$d_{0}’,$$d_{1}’,$とする．今，$\cdots,$ $d_{n-1}’$:
補題
2 任意の連結なグラフ $G$ に対して， は奇グ$\hat{G}$$v_{k}$

についてその次数$d_{k}’\hslash^{\backslash }\backslash \backslash d(v_{k})-1$に一致

しないと仮定する．閉路空間の定義より， は偶数 ラフであり，また と の完全マッチングの個数は等 しい．
である また， が奇グラフであることより，
ならば明らか -:.
は奇数である．よって，
p- 明 まず， が奇グラフであることを示す． のに $d_{k}’<d(v_{k})-1$$\hat{G}$$G$$d_{k}’$

$:)$

$G$

$d(v_{k})$$d_{k}’\neq d(v_{k})-1$$\equiv$$\hat{G}$$\pi$である．このとき，$m-n/2= \sum_{i=0}^{n-1}(d(v_{i})-1)$
なので，明らかに $G(v)$
中に別のある頂点 が存在し，その次数は $d(v_{j})-1$となる
より大きい． は偶数であるため$\hat{v}_{2}$$f$$\sum_{i=0}^{n-1}(d_{i}’-1)=$

頂点は 1 であり，また， 中のすべての偶数次数の頂点は への辺が追加されることにより奇数次数となるため，証明は の次数が奇数であること，すな$d_{j}’>d(v_{j})$わち， 中における偶数頂点の個数が偶数であるこが，これは明らかに矛盾である．以上より示された．
とを示せば十分である．握手補題より全頂点の次数
口の総和は必ず偶数となるので， における奇数次数補題 1 は， が奇グラフの場合にのみ成立する命 の頂点は偶数個存在する． の頂点数は偶数である
題であるが，一般のグラフに $G$ ついては，同定理を 6ので， における偶数次数の頂点数は偶数個存在す
$G$

$]$

$]$

$\hat{v}_{1}$$v_{j}$$j$$\hat{v}_{1}$$d_{j}’$$G$$\dot{j}_{1}$

$($

$G$

$\iota$

$G$

$G$

$t$

$G$

る．以上より示された．
適用可能な形にグラフを変形させることができる．
$G=(V, E)$ を任意の連結なグラフとし， 中におけと次にの完全マッチングの個数が一致する$G’$
る偶数次数の頂点の集合をとする．いま，以下 ことを示す． において追加された頂点は およびのようにして得られるグラフ
であり，このうちは次数 1 である．よって，を考える．
の完全マッチングにおいて， に接続するマッチ
頂点集合 に新たな頂点を追加する．す$j_{(}$$G$$V$$V^{even}$.
.

$\hat{G}$$\overline{i}$$\hat{v}_{1}$$\hat{G}=(\hat{V},\hat{E})$$\zeta$$\hat{v}_{2}$$\hat{v}_{2}$$\hat{G}$$\acute{C\cdot}$$\hat{v}_{2}$

$V$

なわち

$\hat{v}_{1},\hat{v}_{2}$$\hat{V}=V\cup\{\hat{v}_{1},\hat{v}_{2}\}$

ング辺は

.

$d$

チングから辺$\overline{7}$

新たに追加した 2 頂点
た， と $G$ 中のすべての偶数次数の頂点に辺を$\hat{v}_{1},\hat{v}_{2}$引く，すなわち，$\hat{E}=E\cup\{(v,\hat{v}_{1})|v\in V^{even}\}\cup$.

$\hat{G}$$(\hat{v}_{1},\hat{v}_{2})$$\hat{G}$を取り除いたグラフは必ず $G$$\hat{G}$$\supset$

マッチングと $G$ の完全マッチングの間に一対一対応

マの 関係を定義することが可能であり，結果として $G$$\tau\supset$とと

上記の変形の例を図 1 に示す．この変形により得られるグラフの一通りのみであり， の完全マッ間に辺を引き，まの’ 完全マッチングとなる．このことより， の完全$\hat{v}_{1}$$\{(\hat{v}_{1},\hat{v}_{2})\}$$(\hat{v}_{1} ,\hat{v}_{2})$$\hat{G}$の完全マッチングの個数は一致する$\square$

上記補題およびマックウィリアムスの恒等式より，に対して，以下の補題が成立する．以 下の定理を得ることができる．
,$A^{\backslash }$6
定理 2 任意のグラフ $G$ に対して， のカット
重み分布 $A_{C\perp}((0),A(1),$ $\cdots A_{C\perp}(m)$成を示す．構成は，補題 3 より，$O(f(n))$ 時間で計算するアルゴリズムが存在するとの偶奇によって場合分けされる．

き， の完全マッチングの個数は $O(f(n)+$ poly $(n))$
時間で計算可能である．

$|V_{1}^{even}|$

以下， に対応するグラフ$G$$\hat{G}$

$n$

.
.

頂点の連結なグラフの接続行列はランク $n-1$

であることが知られているため，$|C(\hat{G})|=2^{n-1}$ である．また，マックウィリアムス恒等式に現れるすべての値は $O(n)$ ビットで表現可能であることは容易に確かめることができ，その四則演算も の多項式時間で実行可能である．よって，マックウィリア
ムス恒等式を利用したの計算は の多項口式時間で可能であり，定理が成立する

52

および

ならば，頂点集合$\{0,1\})$ それぞれに対して，新たな頂点

.

に対して，
する．また， i,l と$i\in\{0,1\}$

および.

$\hat{G}$が一般には二部グラフとならないという問題点がある．この問題を解決するため，本節では任意の二部
グラフ $G$ からの，完全マッチングの個数を保存するを二部グラフとして，

における偶数次数の頂点集合をそれぞれおよびに興味があるので，$|V_{1}|=|V_{2}|$が奇数の場合$V_{1-i},$$\tilde{v}_{i,1}$

ば，$\tilde{v}_{1-i,3},\tilde{v}_{i,4}$$i\in\{0,1\}$を追加する．

に対して$\tilde{v}_{\dot{*},1}$$\sim$$V_{i}^{even}$と$\tilde{v}_{1-i,2},\tilde{v}_{i,3}$と$\tilde{v}_{2,3}$と$\tilde{v}_{1-i,4}$を接続する．

から任意の $|V_{i}^{even}|-1$ 個の頂点をと接続しなかっ選び，と接続する．
と接続する．
た頂点は，$\tilde{v}_{1-i,2}$$\tilde{v}_{1-i,2}$$\tilde{v}_{1-i,3}$$\tilde{G}$に対して，以下の定理を得ることができる．

,$\hslash$$|$

題 4 任意の連結なグラフ $G$ に対して， は奇グ$\tilde{G}$ラフであり，またであることを仮定$\tilde{G}$と $G$ の完全マッチングの個数は

等 しい．

補題 3

定理 3 任意のグラフ$|V_{2}^{even}|$を辺で接続$V_{i}(i\in$ならば，頂点集合,
それぞれに対して，新たな頂点ならを追加する．さらに，してよい．ここで，以下の補題が成り立つ．
と

,

$|$

$V_{1}^{even}$とする．今は，完全マッチングを持つような$|V_{1}^{even}|$$\tilde{v}_{i,2}$

上記の構成の例を図 2 に示す．グラフ$V_{1}$$\tilde{v}_{1-1,1}$$|V_{i}^{even}|\geq 3$

さらにが可能である．

$G$$|V_{2}^{even}|$$\tilde{v}_{1,3}$の構成を与える．この構成を用いる$G=(V_{1}, V_{2}, E)$$V_{i}(i\in$

中のすべての頂点$V_{:}^{even}$を辺で接続する．また，ことで，二部グラフの完全マッチングの数え上げを二部グラフのカット重み分布の計算に帰着すること$V_{2}^{even}$と$\tilde{v}_{1-i,1}$$|V_{i}^{even}|\geq 1$$\{0,1\})$

前節に述べた帰着では， が二部グラフの場合，$V_{2}$$V_{1-i},$

01,2 を追加する．

$\tilde{v}_{1-i,2}$$\tilde{G}$が偶数の場合$|V_{\dot{*}}^{even}|\geq 2$$|V_{1}^{even}|$

二部グラフの場合

二部奇グラフの構を接続する．

$n$$G$$|V_{2}^{even}|$$\tilde{v}_{1-}$$n$$A_{C(\dot{G})}(n)$$(\tilde{V}_{1},\tilde{V}_{2},\tilde{E})$$|V_{1}^{even}|(=|V_{2}^{even}|)$

$G$

証明

$\tilde{G}=$の偶奇は一致する．

重
. み分布

$G$

に対して， のカット$\tilde{G}$$A_{C^{\perp}(G^{-})}(0),$ $A_{C^{\perp}(G^{-})}(1),$ $\cdots A_{C^{\perp}(\tilde{G})}(m)$を{1, 2} $O(f(n))$ 時間で計算するアルゴリズムが存在するとが奇数のとき，任意の$d(v)$ はつねに偶数なので，について，き， の完全マッチングの個数は $O(f(n)+poly(n))$に含まれ# 間で計算可能である．
は奇数である．
る頂点の次数は奇数なので，結果として
証明は補題 2, および定理 2 とほぼ同様である．
が奇数であることを意味する． が偶数の場合も
証明

$|E|$

$i$

$\in$

$\sum_{v\in V_{:}^{R}}$。

$\sum_{v\in V\backslash V_{:}^{wen}}d(v)$$G$$V\backslash V_{i}^{even}$$|$$|V\backslash V_{i}^{even}|$$|E|$同様に示すことができる

口$\doteqdot$

7は正確に 2 通り $(S$ と$V\backslash S$

を入れ替えても同じカットセットを表す) 存在するため，彩色のパタン数の半分が実際のカットの個数に対応する．なお，以降の議論では，しばしばグラフの一部分のみを彩色することを考える．頂点の部分集合 $V’\subseteq V$ に対して
$V’$ へののみ 1 あるいは の色を割り当てることを，分的な) 彩色と呼ぶこととする．また，頂点 の
隣接頂点の集合を $N(v)$ で表す．
今，重み のカットを計数したいとする．提案す

$G$

$0$

$\ell\beta$

$v$

$k$

るアルゴリズムの背景となるアイデアは， への部$V_{1}$$\tilde{\nu}_{2,2}\tilde{v}_{2,3}\tilde{v}_{2,4}$

分的な彩色を固定した下で，カットの重みが となるようなグラフ全体への彩色 (すなわち，残りの頂点巧への部分的な彩色) のパタン数を の多項式時$k$$\tilde{G}$

$n$

図 2:

6

$\tilde{G}$の構成例

間で計数可能であるという事実である．以下，そのアイデアの詳細を述べる．

今，ある彩色 $X$ が巧に与えれられているとする．

3-正則二部グラフに対するカッ は 3-正則二部グラフなので， に含まれる各頂$N(v)$ 中の頂点はすべて琶に属して点 に対して，
ト重み分布の計算$G$$V_{2}$$v$

おり，彩色済みである．そのため， に接続してい$v$

本節では，3-正則二部グラフに対するカット重み
る 3 本の辺がカットに属するかどうかは， の彩色分布の計算を行う
時間のアルゴリズムに$v$$\tilde{O}(2^{5n/12})$

ついて述べる．以降ではまず，$\tilde{O}(2^{n/2})$

時間で重み分布を計算するアルゴリズムを示したのち，それを改良して所望のアルゴリズムを得る．

$N(v)$ がどのようによってのみ決定される．ここで，に彩色されているかについては，以下の 2 つの場合が存在する．

1. $N(v)$ 中の頂点がすべてが同じ値で彩色されて

6.1$\tilde{O}(2^{n/2})$

いる．

時間アルゴリズム

本節では，連結な 3-正則二部グラフに対して時間でカット重み分布を計算するアルゴリ
ズムを提案する．
入力として与えられる 3-正則連結二部グラフを

2. $N(v)$ 中の頂点のうち 2 点が同じ値で，残り一点が異なる値で彩色されている．

$\tilde{O}(2^{n/2})$$G=(V_{1}, V_{2}, E)$

以降，前者に当てはまるような を 3-頂点と呼び，後者に当てはまるような を 2-頂点と呼ぶ．直感的
$v$

$v$

とする．3-正則であることより， には，ある頂点$|V_{1}|=|V_{2}|$ である．カットは$|E|=3n/2$ であり，
$V=V_{1}\cup V_{2}$ の部分集合 $S$ で表せる$(S$ との$V\backslash S$

が 3-頂点であるということは，を的確に彩色することで隣接辺のうち 3 本または 0
$v$

$v$

本をカット辺に含めることが可能であるということ

間の辺がカット辺となる) ので，以降はあるカットのであり，2-頂点であるということは，接続辺のうち選択を頂点の (proper でない) 2-彩色として考える． 2 本または 1 本をカット辺に含めることが可能であに含まれる頂点は値 1 に彩色，に含まれる るということである．図 3 に巧への部分的な彩色の頂点の彩色は値 O に彩色されていると見なす．なお， 例を示す．この例において，2 頂点数および 3 頂点
$S$

$V\backslash S$

グラフが連結であることから，彩色によるカットの 数の数はそれぞれ 2, 4 である． への 3-頂点 (2-頂表現を用いた場合，あるカットセットに対する彩色 点 V について，その隣接辺のうち 3 辺 (2 辺) がカッ$V_{1}$$)$

8
補題 5 $G=(V_{1}, V_{2}, E)$ を 3-正則 2 部グラフとす

る．2-頂点の個数力$\grave\grave$$z$であるような防への彩色のパタン数を $Q(z)$ とすると，重み$A_{C^{\perp}(G)}(k)$$k$のカットの個数について以下の式が成立する．

$A_{C^{\perp}(G)}(k)$\copyright 2-頂貞$\otimes$か頂点$= \frac{1}{2}\sum_{z=0}^{n/2}(Q(z)\sum_{(j_{3},j_{2})\in P(k,z)}(\begin{array}{ll}n/2- zj_{3} \end{array}) (\begin{array}{l}zj_{2}\end{array}))$彩色$\bullet$$O$$\iota$

彩色$0$

この補題から，カット重み分布を求める以下のよ
図 3:$V_{1}$

への部分的な彩色，および 2-頂点と魯頂点の例

うなアルゴリズムを得ることができる．

1.

$V_{1}$のすべての彩色を列挙し，$Q(O),Q(1),$ $\cdots,$ $Q(n/2)$ を計算する．

を彩色するとき， は多数
派に彩色されていると呼ぶ．
への部分的な彩色 $X$ が与えられたもとでの 2ト辺に含まれるように

$v$

$v$

2. 補題 5 の式に従って $A_{C(G)}(k)$ をすべての $k(0\leq$$k\leq m)$

について計算する．

$V_{1}$$|V_{1}|=n/2$ なので，の上界であるとする．
補題 5 の式に現れる数値はいずれも3-頂点の個数は $n/2-z$ であり，このとき，を持つので，任意の四則演算は の多項式時間で計頂点の個数が$2^{O(n)}$

$z$

$n$

$Q(z)$ の分布が与えられた算が可能である．よって，もとでの上式の計算は(1)$\{\begin{array}{l}3j_{3}+2j_{2}+(z-j_{2})=k0\leq j_{3}\leq n/2-z0\leq j_{2}\leq z\end{array}$$n$の多項式時間で可能である．

また， の頂点数は $n/2$ であるので，すべての彩色$V_{1}$

である．1 つのパタンの列挙およびそのパタンにおける 2-頂点の個数の計算は の多項式時間で計算可能である．また，列挙したパタンを記憶しておく必要はないので，この過程において使用されるメモリ量は の多項式サイズである．

パタンの個数は$2^{n/2}$$n$が存在するならば，3-頂点のうちの任意の 個，および 2-頂点のうちの任意のを多数派に彩色することで，サイズ のカットを得の組の集合をることができる．条件 1 を満たす
よって，このアルゴリズムはを満たす整数$j_{3}$

および$j_{2}$$j_{3}$$k$$j_{2}$$n$$j_{3},$$j_{2}$$P(k, z)=\{(j_{3},j_{2})|3j_{3}+$$P(k,z)$ とする (すなわち，$j_{2}=k-z,0\leq j_{3}\leq n/2-z,$ $0\leq j_{2}\leq z\})$ と，$V_{1}$

への彩色 $X$ のもとで，カット重みが$k$

メモリスペースで，サイズ$k$$\tilde{O}(2^{n/2})$

時間，多項式のカットの重み分布を計算する．

となるようなグラフ全体の彩色の個数は$G$ のカッ定理 4 $G=(V, E)$ を 3-正則グラフとする．

ト重み分布 $A_{C(G)}\perp(0),$ $A_{C^{\perp}(G)}(1),$ $\cdots A\perp(m)$ は時間，poly $(n)$ ビットのメモリ空間で計算可$\sum_{(j_{3},j_{2})\in P(k,z)}(\begin{array}{ll}n/2- zj_{3} \end{array}) (\begin{array}{l}zj_{2}\end{array})$$\tilde{O}(2^{n/2})$

能である．

に正確に一致する．ここで，上記の式は およびの関数なので，その値は巧への彩色によって決まる 2-頂点数 のみに依存して決定される．すなわち， 62 分布 $Q(z)$ の高速な計算への異なる 2 つの彩色 $X,$ $Y$ に対して，その 2前節において提案したアルゴリズムのボトルネッ
頂点数が等しければ，上式の値は $X,$ $Y$ ともに等し ク (は， の彩色の全列挙による分布 $Q(z)$ の計算でくなる．よって，以下の補題を得ることができる．
$z$

$k$

$z$

$V_{1}$$V_{1}$

9$X$ に対する，(2, 2)-頂点および 3, $3)-$ある．本節では，列挙の個数を削減することで，同 とを考える．
部分の高速化を行う．本節の高速化をここまでの議 頂点の集合をそれぞれ乃 $(X),T_{3}(X)$ とする．これ$($

論に組み合わせることで，最終的に$\tilde{O}(2^{5n/12})$らの頂点は $S$ の彩色内容によらず，それぞれ 2-頂時間の完全マッチング計数アルゴリズムを得ることがで 点，3-頂点となる．よって，以降は頂点集合 $T(X)=$きる．
が の彩色により 2-頂点，3$V_{2}\backslash (T_{2}(X)\cup T_{3}(X))$

頂点集合: $N(u)\cap$
であるような防の部分集合と定める．ま

頂点を共有しない，すなわち$N(v)=\emptyset$$S$を，集合中のどの 2 頂点も隣接 頂点のいずれになるかのみに注目する．我々の目的$S\subseteq V_{1}$は 2-頂点数力$\forall u,v\in S$となるように $S$ への部分的な彩色$\sim$$T(X)$ 中の集合のうち，を調整することであるので，と定める．定義より明らかに，$z-|T_{2}(X)|$ 個を 2-頂点にするような $S$ の彩色方法の各頂点は高々 1 つの $S$ に属する隣接頂点を持つ．

$T(X)$ 中の頂点のうを考える必要がある．これは，た，$V_{1}\backslash S=\hat{V}_{1}$$Q(z)$$V_{2}$

ち，2-頂点となるものの個数が 3-頂点となるもののの計算を高速化するための基本的なアイデ

アは前節とほぼ同様である．核となる事実は，吻への彩色を固定したもとで，2-頂点数が となるよう

個数より

$z$

な

$V_{1}$

への彩色パタン数 (すなわち$S$$(z-|T_{2}(X)|)-(|T(X)|-(z-|T_{2}(X)|))$

への彩色パタ

今，ある部分的な彩色 $X$ を$\hat{V}_{1}$(2)$=2z-|T(X)|-2|T_{2}(X)|$ン数) を多項式時間で計算できるということである．

に与えたと仮定する． 個だけ多くなるような彩色を考えるということと等$N(v)$ の彩色状況
このとき，巧の任意の頂点 は，
$v$

価である．

により以下のいずれかの場合に分類される．

$N(v)$ 中に含まれる中の任意の頂点 について，(2, 3)-頂点および (3, 2)-頂点の個数をそれぞれ$S$

1. $N(v)$ はすべて彩色済みであり，2 頂点である．

$v$$\delta_{2}(v)$$|\delta_{2}(v)-\delta_{3}(v)|=i$ であるような頂およびとし，
点 $v\in S$ の集合を Si (X) とする．ある頂点 $v\in S_{i}(X)$$\overline{\delta}_{3}(v)$2. $N(v)$ はすべて彩色済みであり，3-頂点である．
3. $N(v)$ のうち 1 頂点が に属しており，残りの2 点は異なる色で彩色されている．
$S$$N(v)$ における 2-頂点の個数が多くなるについて，ように を彩色するとき， を多数派で彩色するという．例えば， の 3 隣接頂点がそれぞれ (2, 3)-頂点，(3, 2)-頂点，(3, 2)-頂点のとき，彩色 が への
$v$

$v$

$v$

4. $N(v)$ のうち 1 頂点が に属しており，残りの2 点はいずれも色 1 で彩色されている．
$S$

5. $N(v)$ のうち 1 頂点が に属しており，残りの2 点はいずれも色 0 で彩色されている．

$0$

$v$

多数派の彩色となる．
$S$ に対する
巧に彩色 $X$ が与えられているもとで，$S$$T(X)$
ある彩色 $Y$ を与えられたとする．このとき，

おいて生じる 2-頂点，み頂点の個数をそれぞれ
2 $(X, Y),$ $z_{3}(X, Y)$ とする．今，集合 Si (X) のうちあ$\}_{\overline{\llcorner}}$以降ケース 1 または 3 に属するような頂点を(2, 2)-頂点と呼ぶ．また，ケース 2, 4, 5 に属する頂点をそれぞれ (3, 3)-頂点，(3, 2)-頂点，(2, 3)-頂点と$(a, b)$ -頂点は， に含まれる隣接頂点が存在す呼ぶ．
るならば，それを 1 に彩色することで -頂点に，に彩色することでひ頂点になるということを意味している．また， に含まれる隣接頂点を持たない場

$lE$
$1$

の頂点が多数派で彩色されているとすると，Si (X)の定義より，
$1$

$S$

$a$

$z_{2}(X, Y)-z_{3}(X, Y)$$0$$=j_{1}+2j_{2}+3j_{3}-(|S_{1}(X)|-j_{1})$$S$$-2(|S_{2}(X)|-j_{2})-3(|S_{3}(X)|-j_{3})$合は，それは (2, 2) 頂点か (3, 3)-頂点のいずれかとなる．

$= \sum_{i=1}^{3}(2i\cdot j_{i}+i|S_{i}(X)|)$

今， への彩色$\hat{V}_{1}$2 頂点の個数が

$z$

$X$

(3)

が与えられたとき，最終的にとなるような $S$ の彩色を求めるこ$Y$ がグラh7 成立する．よって，式 2 および 3 より，$\grave\grave\grave$10
フ全体として 2-頂点を$z$個持つ彩色となるための必要十分条件は，

1.

$V_{1}$

2.

$S$$z_{2}(X, Y)-z_{3}(X, Y)$

中の任意の 1 頂点

を $S$ に加える．

に含まれる任意の頂点との距離が 4 以上，かつ少なくともある 1 頂点との距離が正確に 4 であるような$=2z-|T(X)|-2|T_{2}(X)|$$v$$V_{1}\backslash S$

内の頂点を選び， に加える．
$S$

3. 加えられる頂点が無くなるまでステップ 2 を繰$\Leftrightarrow\sum_{i=1}^{3}(2i\cdot j_{i}+i|S_{i}(X)|)$

り返す．

$=2z-|T(X)|-2|T_{2}(X)|$(4)

である．言い換えるならば，上記条件を満たすよ$j_{3}(0\leq i:\leq|S_{i}(X)|)$ に対して，Si (X)うな il,$(i\in\{1,2,3\})$ に含まれる頂点のうち任意の個を多$j_{2},$$i\dot{*}$

数派で彩色することで，2-頂点数が$z$であるような

巧の部分的な彩色を得ることができる．このことから， へと彩色 $X$ を与えたもとでの，2-頂点数が$\hat{V}_{1}$個となるような$V_{1}$$z$への部分的な彩色のパタン数は補題 6 上記アルゴリズムにより選択された集合について， 中の任意の 2 頂点は共通の隣接頂点は

$S$

$S$

$|S|\geq n/12-1$ である．
持たない．また，中の任意の 2 頂点力供通の隣接頂点を持たないことは，それらの距離が 4 以上離れていることか

証明

$S$

$|S|\geq n/12-1$ を示す．あるら明らかである．以降，

頂点 $u\in V_{1}$ に対して， からの距離が 2 であるよう$N_{2}(u)$ は， を $S$ に追な頂点の集合を $N_{2}(u)$ とする．
加することでそれ以降 に加えることができなくな
$u$

$u$

$S$

$\sum_{(j_{1},j_{2},j_{S})\in P’(X,z)}(\begin{array}{l}|S_{1}(X)|j_{1}\end{array})(\begin{array}{l}|S_{2}(X)|j_{2}\end{array})(\begin{array}{l}|S_{3}(X)|j_{3}\end{array})$

る頂点の集合である．手続きの実行において追加されとる順番に の頂点を並べた系列をと書ける．ここで $P’(X, z)$ は式 4 およびする．手続きの終了時点において にはもう新たな$|S_{i}(X)|(i\in\{1,2,3\})$ を満たすような整数の 3 項組
頂点が追加できないので，任意の頂点 $v\in V_{1}$ は，既$S$$u_{1},$ $u_{2},$$\cdots,$ $u_{|S|}$$0\leq j_{\dot{*}}\leq$

$S$

$($

il,

$j_{2},j_{3})$すべてからなる集合と定義している．

に $S$ に含まれている力$\searrow$$P’(X, z)$ のサイズは高々 $O(n^{3})$ であるので，上記の式は明らかに

$n$

ある

$i$

に対して $v\in N_{2}(u_{i})$であるかのいずれかである．よって，の多項式時間で計算が可能である．

よって，巧への可能なすべての彩色

$X$

について上

$Q(z)$ の分布を得ることが記の式を計算することで，(5)$|S|+| \bigcup_{i=0}^{|S|}N_{2}(u_{i})|=n/2$$i=0$ を除いて， が $S$ に追加されるとが成立する．
$u_{i}$

できる．

き，ある $u_{l}(0\leq l\leq i)$ に対して

$u_{i}$と$u_{l}$

確に 4 であることが成り立つので， と$u_{i}$

6.3 集合 の選択の距離が正$u_{l}$の間の距

離 4 のパス上にある巧中の頂点は， のおよびのいずれにも含まれる．すなわち，任意の $i>0$
前述のアルゴリズムでは， に対する部分的な彩がについてある が存在し，色を全列挙することで $Q(z)$ の分布を得ることができ成立する．よって，集合 N2 (tm),でるので，その計算時間はは，少なくとも $|S|-1$ 個の要素を重複して含んでいを$S$$N_{2}(u$$N_{2}(u_{l}$$\hat{V}_{1}$$l$$|N_{2}(u_{i})\cap N_{2}(u_{l})|\geq 1$$N_{2}(u_{1}),$ $\cdots N_{2}(u_{|S|})$$\tilde{O}(2^{|\hat{V}_{1}|})=\tilde{O}(2^{n/2-|S|})$

ある．そのため，できるだけサイズの大きい集合 $S$

選択して，アルゴリズムを実行することが望ましい．
以下に示す単純な手続きを利用することで，任意の 3-

ることがわかり，このことから，不等式$| \bigcup_{1=0}^{|.S|}N_{2}(u_{i})|\leq\sum_{i=0}^{|S|}|N_{2}(u_{i})|-|S|+1$

正則二部グラフに対して，少なくとも $|S|\geq n/12-1$となるような巧の部分集合 $S$ を構成することが可能である．

を得る．グラフが 3-正則二部グラフであることから，任意の$u_{i}$$|N_{2}(u_{i})|=6$ であるので，この
について，

11
不等式は

[2] E. T.’ Bax and J. Franklin.
A permanent algorithm with $exp[\omega(n^{1/3}/2\ln(n))]$ expected speedup for 0-1 matrices. Algorithmica,$32(1):157-162$ , 2002.

$| \bigcup_{i=0}^{|S|}N_{2}(u_{i})|\leq 5|S|+1$と変形でき，式 5 と組み合わせることで $n/2\leq 6|S|+$が成立する．これより $|S|\geq n/12-1$ を得る．口$1$

上記アルゴリズムで得られる集合$S$[3] I. Bez\’akov\’a, D.
, V. V. Vazirani,
and E. Vigoda. Accelerating simulated annealing for the permanent and combinatorial
counting problems. In Proc. of the 17th annual
ACM-SIAM symposium on Discrete algorithm(SODA), pages 900-907, 2006.
$\check{S}tefankovi\check{c}$を利用することで，以下の定理を得る．
定理 5 $Q(z)$ の分布は，$\tilde{O}(2^{5n/12})$時間，poly $(n)$ ビッ

トメモリ空間で計算可能である．
定理 2, 定理 5, および補題 5 を組み合わせること
で，以下の系が導かれる．

[4] A. Bj\"orklund. Counting perfect matchings as
fast as ryser. In Proc of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.
to appear.

系 13-正則二部グラフの完全マッチングの個数は，$\tilde{O}(2^{5n/12})$時間，poly$(n)$

ビットメモリ空間で計算可[5] A. Bj\"orklund and T. Husfeldt. Exact algorithms for exact satisfiability and number ofperfect matchings. Algonthmica, 52:226-249,
2008.

能である．

7

むすび

本論文では，完全マッチング計数問題に対する， [6] S. Chien, L. Rasmussen, and A. Sinclair. Clif符号理論からのアプローチに基づく新たなアルゴリ

ford algebras and approximating the perma-

ズムを提案した．提案アルゴリズムは，3-正則二部
グラフに対して，多項式メモリスペース，計算時間

nent. In Proc. of the 34th annual $ACM$ symposium on Theory of computing (STOC), pages
222-231, 2002.

$\tilde{O}(2^{5n/12})$を達成している．この結果は多項式メモリ

スペースのアルゴリズムとしては我々の知る限り最速である．提案手法では線形符号の双対性を利用して完全マッチングの数え上げをカットの重み分布計
算に帰着することで高速なアルゴリズムを得ている．

[7] P. Dagum and M. Luby. Approximating thepermanent of graphs with large factors. Theoretical Computer Science, 102:283-305, 1992.

この手法は数え上げ問題に対する新しいアプローチ[8] H. Dell, T. Husfeldt, and M. Wahl\’en. Exponential time complexity of the permanentand the tutte polynomial. In Proc. of the37th intemational colloquium conference on
A utomata, languages and progmmming, volume LNCS 6198, pages 426-437, 2010.

として興味深く，同様の手法の他の数え上げ問題への適用，および一般のマッチング計数への応用等，さらなる発展が考えられる．

参考文献[9] Fedor V. Fomin and Kjartan Hie. Pathwidthof cubic graphs and exact algorithms. Information Processing Letters, 97:191-196, March$1$[1] S. Arnborg, J. Lagergren, and D. Seese. Easy
problems for tree-decomposable graphs. J. Algorithms, 12:308-340, 1991.
$f$

2006.

12
[10] A. Galluccio and M. Loebl. On the theory of
pfaffian orientations. . perfect matchings andpermanents. Electronic Joumal of Combinatorics, 6, 1999.
$i$[11] C. D. Godsil and I. Gutman. On the matching
polynomial of a graph. In Algebraic Methods
in Graph Theory, pages 241-249. 1981.

on steiner tree and related problems. available at http: $//www$ . uib. no $/People/jne061/$

St inerfull. pdf, 2010.
$e$[20] Y. Okamoto, R. Uehara, and T. Uno. Count-ing the number of matchings in chordalIn
and chordal bipartite graph classes.
Proc. of 35th Intemational Workshop on
Graph-Theoretic Concepts in Computer Science $(WG)$ , pages 296-307, 2009.

[12] R. Impagliazzo, R. Paturi, and F. Zane. Whichproblems have strongly exponential complexity? Joumnal of Computer and System Sci- [21] H.J. Ryser. Combinatorial Mathematics. The
ences, $63(4):512-530$ , 2001.
Carus mathematical monographs. Mathematical Association of America, 1963.
[13] M. Jerrum and A. Sinclair. Approximating
the permanent. SIAM Joumal on Computing, [22] R. A. Servedio and A. Wan. Computing sparse
pemanents faster. Information Processing.
18:1149-1178, 1989.
Letters, 96:89-92, November 2005.
[14] M. Jerrum, A. Sinclair, and E. Vigoda. A
polynomial-time approximation algorithm for [23] G. Tesler. Matchings in graphs on nonthe permanent of a matrix with nonnegativeorientable surfaces. Joumal of Combinatrial
Theory Series $B,$ $78:198-231$ , 2000.
entries. $Joumd$ of the $ACM,$ $51:671-697$, 2004.
[15] N. Karmarkar, R. Karp, R. Lipton, L. Lov\’asz,
and M. Luby. A monte-carlo algorithm forestimating the permanent. SIAM Joumal on
Computing, 22:284-293, 1993.
[16] P. Kasteleyn.
Graph theory and crystal
physics. In Gmph Theory and Theoretical
Physics, pages 43-110. Academic Press, 1967.

[17] M. Koivisto. Partitioning into sets of boundedcardinality. In Proc. of 4th Intemational
Workshop on Parameterized and Exact Computation (IWPEC), volume LNCS 5917, pages
258-263, 2009.
[18] J. Nederlof. Inclusion excluion for hard problems, 2008.
[19] J. Nederlof.
Fast polynomial-space algorithms using mobius inversion: Improving[24] L.G. Valiant. The complexity of computing
the permanent. Theoretical Computer Science,$8(2):189-201$ , 1979.