omputing PfaÆans
Meena Mahajan y
The Institute of Mathematial Sienes, Chennai, INDIA.
meenaims.ernet.in
P. R. Subramanya, V. Vinay z
Dept. of Computer Siene & Automation,
Indian Institute of Siene, Bangalore, INDIA.
fsubbu,vinaygsa.iis.ernet.in
November 21, 2003
Keywords: PfaÆan, mathing,ombinatoris, algorithm,NC.
Abstrat
The PfaÆan of an oriented graph is losely linked to Perfet Mathing. It is also
naturallyrelated tothedeterminant ofanappropriately denedmatrix. This relation
between PfaÆan and determinant is usually exploited to give a fast algorithm for
omputingPfaÆans.
WepresenttherstNCalgorithmforomputingthePfaÆan. (Previousdeterminant-
basedmethodsomputeditinNConlyuptotheorretsign,whilepreviouspolynomial-
time algorithms did not lend themselves to parallelization.) Our algorithm is om-
pletely ombinatorial innature. Furthermore, it is division-free and works over arbi-
trary ommutative rings. Over integers, we show that it an be implemented in the
omplexitylass GapL.This upperboundwasnot known before, and establishesthat
omputingthePfaÆan forintegerskew-symmetrimatries isompleteforGapL.Our
proof tehniques generalize the reent ombinatorial haraterization of determinant
[MV97℄.
As aorollary, we showthat underreasonableenodingsofa planargraph,Kaste-
leyn's algorithm [Kas67 ℄ for ounting the number of perfet mathings in a planar
graphis alsoin GapL.
Anextendedabstratdesribingtheseresultsappearedin theProeedingsoftheFifth AnnualInterna-
tional Computingand Combinatoris ConfereneCOCOON1999, in theSpringer-VerlagLeture Notes in
ComputerSieneseriesVolume1627,pp.134{143.
y
Partofthisworkwas donewhenthisauthor wassupportedbytheNSFgrantCCR-9734918onavisit
toRutgersUniversityduringsummer1999.
z
This work was initiatedwhen thisauthor was visitingDIMACS at RutgersUniversityduring summer
1998.
The main results of this paperare
1. anew ombinatorialharaterization of the PfaÆan of anoriented graph, and
2. the rst NC algorithm foromputing the PfaÆan, based onthis haraterization, and
3. pinpointing the omputationalomplexity of PfaÆan as omplete for the lass GapL.
Ourombinatorialharaterisationandalgorithmaresimilarinspirittoareentresultof
Mahajan&Vinay[MV97℄whogiveaombinatorialalgorithmforomputingthedeterminant
ofamatrix. See[Rot01℄forauniedpresentationof[MV97℄andthiswork,alongwithvarious
extensions.
Our algorithm pinpoints the omputational omplexity of PfaÆans: we establish that
omputing the PfaÆan of a graph is omplete for the omplexity lass GapL. GapL is the
lassof funtionsthat anbeexpressed asthediereneinthenumberof aeptingpathsof
twonondeterministilogspaemahines(i.e. thediereneof two℄Lfuntions). Thisdenes
a spae analog of the important ounting lasses GapP and ℄P. It is known that taking the
diereneoftwo℄Lfuntionsisequivalenttoomputingthedeterminantofanintegermatrix
[Vin91, Dam91, Val92, Tod91℄. In other words, GapL is also the lass of funtions that are
logspaereduible toomputing the determinant ofan integer matrix. GapL isontainedin
NC 2
,the lass of funtionsomputable by polynomialsize iruits of log 2
n depth.
PfaÆans are a well-studied objet in algebra (see e.g. [Lan65℄), and play an important
role in mathing theory [LP86℄. They are intimately onneted to determinants. In fat,
PfaÆans an be onsidered to be more fundamental than determinants, in the sense that
determinants are merely the bipartite speial ase of a general sum over mathings, see for
instane [Knu96, Rot01℄. In partiular, for a matrix A of dimension n with n 0 or 1
(mod4)
det(A)=Pf
0 A
A T
0
!
implying that omputingthe PfaÆan ishard forGapL.
However, no mathing upper bound was known till now. It is known that the square
of the PfaÆan of anoriented graph is equal to the determinant of a related matrix. Thus,
omputing the PfaÆan orret up to the sign is known to be in NC. This is, however, not
adequatetoimplyaGapLalgorithmas(1)wedonotknowifGapLislosedundersquareroots
(ofpositiveintegers),and(2)thisdoesnotgivetheorretsignofthePfaÆan. Thisdoesnot
even implyanyNCalgorithmforthesign. ThePfaÆan(inludingthesign)anbeomputed
in polynomial time [Bar83, GM94℄ using ross-eliminations (akin to Gaussian elimination
for determinants) and hoosing pivot elements arefully, see also [Von99℄. However, this
method suers the same drawbak as Gaussian eliminationof not lending itself to eÆient
parallelization. In [GM94℄ the authors expliitly state that urrent tehniques whih allow
determinant omputationsto be performed in NC donot appear to generalize to PfaÆans,
and that noNC algorithmfor PfaÆans isknown. Thesubsequent determinantalgorithmof
[MV97℄ uses tehniques that do generalize to PfaÆans, yielding the algorithmdesribed in
this work . Our algorithmis thus the rst to plae PfaÆans inside NC, and more preisely,
in GapL.It follows thatomputing integerPfaÆans exatly haraterizes the lass GapL.
The importane of omputing the sign annot be underestimated. As pointed out in
[GM94℄, the omputation of the PfaÆan an be substituted by that of the determinant
(followedbyasquare-rootoperation)inthesolutionofexisteneversionsofvariousproblems,
buttosolvetheorrespondingexatvalueproblem(seeeg[CGM92℄),omputingthePfaÆan
beomesessential. Thealgorithmof[MV00℄isaaseinpoint: itrequiresalinearombination
of ertain PfaÆans and thusannot be implemented in NC unless the PfaÆan with its sign
an be omputed inNC.
OneofthemotivationsforthisworkistounderstandtheomplexityofPerfetMathing.
Perfet Mathingisnot knowntobeinNC,butisknowntobeinRNC[MVV87℄. Thisresult
hasbeenreentlyimprovedbyAllender,ReinhardtandZhou[ARZ99℄whoshowthatPerfet
Mathingisinthe lassSPL (non-uniformly). (SPL isthatsublass ofGapLwherefuntions
take the value 0or 1. Refer to [ARZ99℄ fordetails.) Interestingly,[ARZ99℄makeuse of the
Mahajan-Vinay low sequenes [MV97℄ritially toestablishtheir result.
PfaÆansarisenaturallyinthestudyofmathings;thePfaÆanofanorientedgraphisjust
thesumoverallpossibleperfetmathingsexeptthateahmathinghas anassoiatedsign
aswell, ditated by the orientation. This givesit aavour similarto that ofa determinant.
In the absene of the sign, itwould alulatethe numberof perfet mathings ina graph,a
problemthatiswell-knowntobeompletefor℄P[Val79℄. Also,inthe aseofspeialgraphs,
it isknown that the graph may be oriented in suh a way that allthe terms of the PfaÆan
turnouttobepositive. This obviouslymeansthattherewould benoanellationandhene
the PfaÆan would ount the number of perfet mathings in the underlying graph. Suh
orientationsof graphs are alled PfaÆan orientations.
It is easy to onstrut graphs whih do not admit a PfaÆan orientation; K
3;3
is one
suh graph. A elebrated result of Kasteleyn [Kas67℄ proves that all planar graphsadmit a
PfaÆan orientation. This result wassubsequently improved by [Lit74℄ who showed that all
K
3;3
-free graphsadmit a PfaÆan orientation. Findingsuh an orientation was shown to be
inNCbyVazirani[Vaz89℄. Inthispaper, wepartiallyimproveVazirani'sresulttoshowthat
for planar graphspresented by reasonable enodings, aPfaÆan orientation an be found in
deterministilogspaeL. Combiningthis withour ombinatorialalgorithmforPfaÆans, we
thus show that under reasonable enodings of planar graphs, the problem of ounting the
numberof perfet mathings inaplanargraphisinGapLaswell. Theproblemofextending
our result to K
3;3
-free graphs remains to be investigated. Reent work in [MV00℄ uses
our PfaÆan algorithmand the results of [GL99℄ to extend this result in another diretion:
under reasonable enodings, ounting the number of perfet mathings in a graph of small
(logarithmi)genus isin NC.
In setion 2, a few denitions and preliminaries are stated. In setion 3, we set up the
ombinatorialframework forPfaÆans. Setion4fouses onthe ombinatorialalgorithmfor
omputingPfaÆans. Weshowinsetion5thatndingPfaÆanorientationsofplanargraphs
is inL, and heneounting the numberof perfet mathings in aplanar graph isin GapL.
1
Ourmaintheoremissimilar inspiritto Theorem1in [MV97℄,thoughthereareessentialdierenesin
theproof.
LetD be annn matrix. S
n
isthe permutationgroup onf1;2;:::;ng (denoted [n℄). The
permanent and determinant of D, per(D) and det(D),are dened as,
per (D)= X
2Sn Y
i d
i(i)
det (D)= X
2Sn
sgn() Y
i d
i(i)
where sgn() is 1 if has an odd number of inversions, +1 otherwise. An equivalent
denition of the sign of a permutation is in terms of the number of yles in its yle
deomposition.
We assoiate with the matrix Dthe graphG
D
,whih isthe omplete direted graphon
nverties(withself-loops),havingthematrixelementsasedgeweights. Wedenotebywt(e)
the weight of edge e. Every permutation 2 S
n
an be deomposed into a set of yles in
G
D
. These yles are non-interseting (i.e. simple), disjoint and they over every vertex in
the graph, i.e. these are yle overs. The sign of a yle over is dened in terms of the
number of even length yles onstituting it. The sign is +1 if there are an even number of
suh yles, else it is 1.
A low in G
D
is a walk that starts at some vertex (alled head), visits verties larger
thanthe headany numberof times,and returnstothehead. Thisyle inG
D
isnot always
a simpleyle. Formally,
Denition 1 [MV97℄
1. Alow isanorderedsequene of edgesC =he
1
;e
2
;:::;e
m
isuhthate
i
=hv
i
;v
i+1 iand
e
m
= hv
m
;v
1 i, v
1 6= v
j
for j 2 f2;3;:::;mg and v
1
=minfv
1
;:::;v
m
g. The vertex v
1
is alled the head of the low and denoted h(C). The length of the low is jCj = m,
and the weight of the low is Q
m
i=1 wt(e
i
) and isdenoted wt(C). [Note: C =hei where
e=hv;vi, i.e. a self-loop, is also a low, of length one.℄
2. A low sequene is an ordered sequene of lows C =(C
1
;:::;C
k
) suh that h(C
1 )<
:::<h(C
k ) and
P
k
i=1 jC
i j=n.
Kasteleyn[Kas67℄introduedthe useofPfaÆanstoountthenumberofdimeroverings
ofalattiegraph. WedenemathingsandPfaÆansmoreformally. Weonsideronlysimple
graphs (withno multiple edges)without self-loops.
Denition 2 Given a simple loopless undireted graph G=(V;E) with V =f1;2;:::;ng:
1. A mathing M is a subset of the edges of G suh that no two edges have a vertex in
ommon. That is, a mathing is a set ME(G)suh that
[(i
1
;j
1 );(i
2
;j
2
)2M^(i
1
=i
2 )℄,j
1
=j
2
2. AmathingMisaperfetmathingifeveryvertexi2V(G)oursastheend-point
of some edge in M.
edges.
Thusa perfet mathingisa partitionof the vertiesof Ginto n
2
unorderedpairs, where
eahpair is anedge. Wewillin the sequel proveour results for graphswith integerweights
onedges, although our resultsan easilybe seen tohold over arbitrary ommutativerings.
Given an undireted graph G with no loops or multiple edges and with integer weights
onthe edges, assignorientationsto edgesof G toget adireted graph
~
G. The Tutte Matrix
assoiated with
~
Gis the skew-symmetri adjaeny matrix dened as
A
s (
~
G)
ij
= wt(i;j) if hi;ji isan edge in
~
G
= wt(i;j) if hj;ii isan edge in
~
G
= 0 if (i;j)is not an edge inG
Here wt(i;j)refers tothe weight of the undireted edge (i;j) inG.
LetD beaskew-symmetri matrixrepresenting anorientation
~
G ofanundiretedgraph
G. Let be a permutation inS
n
. We an think of as representing the perfet mathing
fh(1);(2)i,h(3);(4)i,:::;h(n 1);(n)ig. Several permutationsanorrespondtothe
same mathing beause the edges inthe mathing are neither oriented nor ordered (infat,
thereare exatly2 n
2
( n
2
)!distintpermutationsrepresenting eahmathing). The weightof
the permutation isdened aswt()= Q
n
2
i=1 d
(2i 1)(2i)
Consider a perfet mathing M in G. Irrespetive of whih permutation one hooses
to represent M, the term sgn()wt() as omputed with respet to
~
G is invariant 2
. This
invariant an be written as p(M) = sgn(M)wt(M). Thus orienting the graph G assigns
a sign to eah perfet mathing. The PfaÆan of the oriented graph sums up these signed
weightsof perfet mathings.
Formally,
Denition 3 Given a skew-symmetri matrix D, or equivalently, an orientation
~
G of an
undireted graph G overn verties,
The weight of a permutation 2S
n
with respet to D is dened as
wt()= n
2
Y
i=1 d
(2i 1)(2i)
The PfaÆanterm p(M) of a perfet mathingM is dened tobe sgn()wt(), where
2 S
n
is any permutation satisfying M = fh(1);(2)i, h(3);(4)i, :::;h(n
1);(n)ig.
2
Why? Let and 0
both representM. If diers from 0
only in one edge beingipped, then the
signsofthepermutations aredierentbutso aretheirweights(reallthat D isskew-symmetri). If and
0
dier only in the arrangementof edges, then the number of transpositions to onvert to 0
is even,
andthereforetheirsignsarethesame. Ifmorethanoneedgeisipped,and/orthearrangementofedgesis
dierent,theargumentanbeextended.
The PfaÆan of D (or equivalently,of G) is dened as
Pf(D)= X
M p(M)
where the sum ranges overall perfet mathings M.
The anonial permutationfor any mathing M, denoted
M
, isthe permutationwhere
edges are from smaller to larger verties and are listed in inreasing order of the smaller
vertiesineahedge,i.e.
M
(2l 1)<
M
(2l)forl =1;:::; n
2
,and
M
(1)<
M
(3)<:::<
M
(n 1). Using these, the PfaÆan may be dened as
Pf(D)= X
M
sgn(
M
)wt(
M )
where the sum ranges overall perfet mathings M.
ConsiderthegraphgiveninFigure1. Theedgeweightsarerepresentedbyindeterminates
x
a
;x
b
;x
;x
d
;x
e
. Ifalledgesareorientedfromtheirsmallerendpointtotheirlargerendpoint,
then the assoiated matrix D is
D= 2
6
6
6
4
0 x
a x
b x
e
x
a
0 x
0
x
b x
0 x
d
x
e
0 x
d 0
3
7
7
7
5
Possible
Mathings
(12)(3 4)
(14)(2 3)
(13)(2 4)
Terms
+1:x
a :x
d
+1:x
e :x
1:x
b :0
Pf(D)=x
a x
d +x
x
e
Eah PfaÆan term orresponds to a possible perfet mathing in the graph. The non-
vanishing terms orrespond tofeasible perfet mathings.
2 3
1 4
e
c
a b d
Figure1: AnExample Graph
2 3
1 4
Figure 2: An Oriented Example Graph
Fig 2 imposes another orientation on the graph in Fig 1. Assuming that the weights of
allthe edgesinthe graphare equalto+1, this amountstoassigning+1 tox
b
;x
;x
e
and 1
tox
a and x
d
,and results inthe matrixD givenbelow. Now, omparingper(D),det(D) and
Pf(D),we have
D= 2
6
6
6
4
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
3
7
7
7
5
per (D)=2
det(D)=4
Pf(D)=2
Linear algebra yieldsthe followingproperties of skew symmetrimatries D.
IfD has aneven number of rows, then det(D)=(Pf(D)) 2
.
Denition 4 The Gap-Path funtion is dened as follows:
Input : A direted ayli graph G with integer weights on its edges; three speial verties
s, t
+
and t of G.
Output : The funtion f dened below.
f = X
: s;t
+ wt()
X
: s;t
wt()
where iterates over all paths from s to t
+
, over all s to t paths, and wt() or
wt() is the weight of the path (i.e. the produt of the weights of all the edges on the
path).
GapLispreiselythelassoffuntionsthatanbeformulated(usingonlylogarithmispae)
inthisfashion. Equivalently,GapLonsistsofthosefuntionsthatarethediereneoftwo℄L
funtions,where℄L is theounting lassfor NL.Asstated earlier,GapLisalso, equivalently,
the lass of languages logspae reduible to omputing the integer determinant. GapL is
known to be ontained in NC; thus problems in GapL, Gap-Path inluded, have parallel
algorithms requiring O(n
1
) proessors and O(log
2
n) parallel time, for some onstants
1
and
2 .
The Mahajan-VinayGapLalgorithmforthe determinant[MV97℄formulatesthe determi-
nantinthe rst way desribed above. This GapLalgorithman be usedtoompute det(D),
viz. [Pf(D)℄
2
. However, this does not immediately yield a GapL algorithm even for the
absolute value of the PfaÆan itself, beause GapL is not known to be losed under square
roots.
Let F
1
and F
2
be perfet mathings in a graph G. Their superposition, F
1 [F
2
, is the
graph obtained by inludingall losed walks along edges alternately fromF
1
and F
2
. Start
atavertexand walkalong itsmathed edgeinF
1
. Next,walk alonganadjaentedge inF
2 .
If this loses a yle, pik an unvisited vertex and start the losed walks on the remaining
verties. Else,ontinue walkingtillthereare nomoremathededges. F
1 [F
2
isayle over
of G where eah yle is an alternating yle and has even length. Note that eah yle in
F
1 [F
2
an beroutedineitherof twopossiblediretions. GeneralizingKasteleyn's notation
for yle overs on the regular 2-D lattie, we all the two possible routings lokwise and
anti-lokwise. By lokwise routing we mean that routing where the rst vertex is the
smallestvertex inthe yle and the rst edge of a yle is piked from F
1 .
Suppose we impose an orientation on the edges of G toget adireted graph
~
G. A yle
C inF
1 [F
2
,whenroutedinany partiularway,may traverse some edgesaordingtotheir
orientation in
~
G and some edges in a diretion opposite to their orientation. An edge e on
yle C is said to be properly oriented with respet to a routing of C if this routing of C
traverses e aording toits orientation in
~
G.
A routing of C is said to have aneven orientation with respet to
~
G if, in that routing
of C, the number of properly oriented edges is even. Otherwise, the routing of C has an
orientationof both routings(lokwise oranti-lokwise)of suhayle isthe same. Hene
forsuperpositionyles werefertothe orientationof theyle itselfratherthanof arouting
of the yle. (For instane, for the graph of Figure 1 routed as inFigure 2, the yle aed
has odd orientationbeauseif weroute theyle edges intheorder e d a, thenthe three
edges e,d,a are properlyoriented. Similarly,if we route the yle edges in the order e a
d, then only the edge is properly oriented. The yle edb is evenly oriented if routed as
edband oddlyoriented if routed as ebd.)
3 A Combinatorial Setting for PfaÆans
In this setion, we build the ombinatorialframework for PfaÆans using a variant of low
sequenes. This yieldsa ombinatorialharaterisation of PfaÆans, whih wewill utilizeto
develop a ombinatorialalgorithmfor omputingPfaÆans.
We rst state some results whih are essentially rephrasings of or easy derivations from
standard material; see for instane [Lit74, Kas67℄. For ompleteness, we sketh proofs as
well.
The following is a variant of a standard lemma (See Lemma 8.3.1 from [LP86℄) for the
ases when the edges have arbitraryinteger weights.
Lemma 5 Let
~
G be an arbitrary orientation of an undireted graph G. Let F
1
and F
2 be
two perfet mathings of G. Let k be the number of evenly oriented alternating yles in
F
1 [F
2
. Then,
p(F
1 )p(F
2
)=( 1) k
wt(F
1
)wt(F
2 )
Sketh of Proof: F
1 [F
2
onsistsofylesofevenlength. ConsidertheasewhenF
1 [F
2
onsistsofjustonenon-trivialyleC. ChoosethelokwiseroutingofC. RepresentF
1 and
F
2
by those permutations and respetively, where the edges in C are listed in the order
in whih they appear in this lokwise routing, and the other edges are listed identially.
Now it is lear that to go from the permutation to the permutation , we need an odd
number of transpositions. Sothe signs of these permutationsare opposing.
(For instane, let F
1
= (1;2)(3;4)(5;6)(7;8) and F
2
= (1;6)(2;3)(4;5)(7;8). The yle
123456 in F
1 [F
2
implies
=
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
!
and =
1 2 3 4 5 6 7 8
2 3 4 5 6 1 7 8
!
.
In order toonvert to, 1has to be moved rightover ve verties.)
As regardsthe weights, the edgesfor trivialyles ontributethe same tothe weights of
both permutations, and so the produt is idential to the produt of the weights of these
edges in the mathings. A non-trivial yle ontributes the remaining weight with a 1
thrown in for eah edge traversed wrongly. So, if the number of wrongly traversed edges is
odd (i.e. the yle is oddly oriented with respet to
~
G), then the net ontribution is a 1
over and above the weights of the mathings. i.e. wt()wt() = wt(F
1
)wt(F
2
). This
1 willnullify the orresponding 1 inthe produt of the signs. On the other hand, if the
numberof edgestraversedwrongly iseven, then wt()wt()=wt(F
1
)wt(F
2
),and the 1
in the sign is not nullied.
1 2 1 2
wt(F
1
)wt(F
2
). It iswhen C is evenly oriented that a 1is introdued, i.e. p(F
1 )p(F
2 )=
wt(F
1
)wt(F
2 ).
Extendingthisargument,itisevidentthatifthereareseveralnon-trivialylesinF
1 [F
2 ,
then a 1 is introdued by eah evenly oriented yle. This proves the lemma.
The rst idea used for omputing the PfaÆan eÆiently is to ompute the signs of all
PfaÆan terms with respet to a anonial orientation hosen as follows: Given a graph
H and an orientation
~
H whose PfaÆan is to be omputed, let D be the skew-symmetri
adjaenymatrix A
s (
~
H). Given any skew-symmetri matrixA, thereisaunique undireted
graph G, with appropriate edge weights, suh that orienting eah edge of G in the forward
diretion (fromits smallerendpoint toitslarger endpoint)givesan oriented graph G f
with
skew-symmetri adjaeny matrixA. Consider the graphG anditsorientationG f
obtained
as above fromthe matrix D. Then Pf(
~
H) = Pf(D) = Pf(G f
), and we ompute the signs of
PfaÆan terms as inPf(G f
) instead of diretly inPf(H).
The seond idea is to ompute all these signs with respet to some referene mathing
(possibly ofzero weight). Wehoose the referene mathingI orrespondingtothe identity
permutation. And we use anonial permutations to represent eah mathing. Consider a
mathingM and its superposition with I.
Using Lemma5, we an showthe following.
Corollary 6
sgn(
M
)=( 1) k
where k isthe number of yles in M[I that are evenly oriented with respet to G f
.
Proof:From Lemma 5, we have
sgn(
M
)wt(
M
)wt(
I
) =[sgn(
M
)wt(
M
)℄[sgn(
I
)wt(
I )℄
=p(M)p(I)
=( 1) k
wt(
M
)wt(
I )
Therefore, sgn(
M
)=( 1) k
.
The standard way to haraterize the sign of a PfaÆan term isby the number of evenly
oriented yles. We show below that the number of yles plus the number of properly
oriented edges alsoharaterizes the sign.
Lemma 7 Let M be a partition of [n℄ into n
2
unordered pairs and
M
be its anonial
permutation. Let I be the referene partitionorresponding to the identity permutation. Let
M[I have l yles, and let C denote the yle over obtained by the lokwise routing of
eah yle in M[I. The sign of M in the PfaÆan is
sgn(
M
)=( 1)
jfhi;ji : hi;ji 2 C;i<jgj + l
Let C have k even yles and m odd yles with respet to the forward orientation;
l =k+m. Dene E =fhi;ji:hi;ji2C;i<jg, the set of properlyoriented edges. Let the
ontributionstojEjfromeahofthe even andoddoriented ylesbee
i ando
j
for1ik
and 1j m. Thus jEj= P
k
i=1 e
i +
P
m
j=1 o
j
. Notethat eah e
i
iseven and eaho
j
isodd.
ThusjEj+l= P
k
i=1 e
i +
P
m
j=1 o
j
+k+m= P
k
i=1 e
i +
P
m
j=1 (o
j
+1)+kk mod2. Now the
result follows fromCorollary 6.
Corollary 8 Let Mbe a partition as above and I be the identity permutation. The sign of
M in the PfaÆan is
sgn(
M
)=( 1)
jM2j+jM3j+l
where l is the number of yles in M[I, C is the orientation of M[I with eah yle
routed in the lokwisesense and, M
2
and M
3
are disjoint subsets of M dened as,
M
2
=fhi;2ji : hi;2ji 2 M\C; i<2j g
M
3
=fhi;2j 1i : hi;2j 1i 2 M\C; i>2j 1 g
Proof: Lemma7 tells us that we need to keep trak of the parity of properly oriented (i.e.
forward) edgesinthe lokwise routingofyles inM[I. Instead here,letusfous onthe
edges of M alone, and hold an edge of M responsible for the following I edge. Eah edge
of M ontributes 0, 1 or 2 forward edges to M[I. For instane, suppose the lokwise
routing enounters edge hi;2j 1i from M, where i<2j 1. Then it also enounters the
edge h2j 1;2ji from I, and both these edges are properly oriented. The other ases an
be argued similarly.
The table below shows the partition of the edges of M into 4 sets. So, to evaluate the
parity of forward edges, it suÆes to keep trak of the edges of M
2
and M
3
, while M
1 and
M
4
an be ignored.
Part Edge of M ondition number of
as inC forward
edges inC
M
1
forward edge ending in odd vertex hi;2j 1i i<2j 1 2
M
2
reverse edge endingin odd vertex hi;2j 1i i>2j 1 1
M
3
forward edge ending in even vertex hi;2ji i<2j 1
M
4
reverse edge endingin even vertex hi;2ji i>2j 0
We now introdue a new ombinatorial objet alled plows whih we will use in our
ombinatorialsetting for PfaÆans. (Plows expand to PfaÆan Closed Walks and p-edge
stands for PfaÆan-edge.)
Denition 9 A pair of edges E =(e
1
;e
2
) isa p-edge if for somei2[1;n℄, either
1. e
1
=hi;2ji for somej and e
2
=h2j;2j 1i, or
1 2
Figures3 & 4belowindiatethe ases whenapairof onseutiveedges forms ap-edge.
Aplowisalow withits ordered sequeneof edges being P =hE
1
;E
2
;:::;E
m
i where
eah E
i
is a p-edge. The length of the plow, denoted jPj, is 2m. A plow traversal
begins from its smallest vertex (alled the head).
A plow sequene is an ordered sequene of plows, P = hP
1
;:::;P
l
i with heads in
stritly inreasing order, and with P
l
i=1 jP
i j=n.
The sign of a plow sequene is the parity of the number of evenly oriented plows
with respet to G f
.
The weight of a p-edge E = (e
1
;e
2
) is the weight of the edge e
1
in its forward
diretion, i.e. if e
1
= (i;j), its weight is w
ij
if i < j and w
ji
otherwise. The seond
edge, e
2
, always ontributes a 1 to the weight of E. The weight of a plow is the
produt of the p-edge weights. Theweight of aplow sequene isthe produt of the
weights of its plows.
2j-1 2j
i . . .
Figure 3: Seleting hi;2ji from i.
. . .
2j-1 2j
i
Figure4: Seleting hi;2j 1ifrom i.
Thus, if aplowsequene P atuallyrepresents aperfet mathing M,thenitsweightis
wt(
M
), and its sign is the sign of
M
. The results of Lemma 7 and Corollary 8 generalize
toplowsequenes aswell; generalising Lemma7 gives usthe following Lemma:
Lemma 10 Let P be a plow sequene with l plows. Its sign is given by
sign(P)=( 1)
jfhi;ji : hi;ji 2 P; i<jgj + l
That is, the sign of a plow sequene is the parity of the number of plows in it plus the
number of edges traversed in the forward diretion.
Using plow sequenes, we prove a novel and powerful haraterization of the PfaÆan.
This providesthe basis for our ombinatorialalgorithmforomputing PfaÆans.
Theorem 11 Let D be a skew-symmetri matrix. Its PfaÆan is givenby:
Pf(D)=
X
W:pl ow sequene
sgn(W)wt(W)
withaperfetmathing. Weneedtoshowthat plowsequenes thatare notyle oversdo
not ontributetothe summation. Weestablishaninvolutionon the set of plowsequenes.
Non-yle overs get mapped onto non-yle overs of opposite signs. The xed points of
the involution are the yle overs.
Our tehnique would be to pair a plow sequene with another having the same set of
edges but with anopposite sign. Consequently, they anel eah other'sontributionto the
summation.
Note that all plows are, by denition, even in length. However, a given sequene ould
have anodd length simple yle in a plow asshown in Fig 5 &6. To pair suh sequenes,
pik the plow with the smallest head that has an odd simple sub-yle. Walk down this
plowfromitshead,untilyourealizethatyouhavegonearoundanoddyle. Simplyreverse
the orientationof allthe edgesinthis yle. This denes anewplowsequene. Conversely,
startingwiththenewsequene,ourmappingwillonsiderthesame(sub-)yleandreversing
its edges willgive usthe oldplowsequene; so they pair. Their total ontribution is zero,
sinereversinganoddnumberofedgeshangestheparityofthenumberofproperlyoriented
edgesand soontributesanegativesign. The plows inFigures5 &6are anexampleof the
above bijetion.
Figure5: Plowwith odd sub-yle Figure6: Plowwith odd sub-ylereversed
We are left with plow sequenes in whih all sub-yles in all plows are even. Let
P = hP
1
;:::;P
k
i be suh a plow sequene. Pik the smallest i suh that P
i+1 to P
k are
disjointsimpleyles. Ifi=0,thenP isayle overandP mapsontoitself. Else, traverse
P
i
tillone of the followinghappens,
1. We hit avertex that meets one of P
i+1 toP
k .
2. We hit avertex that ompletes an even lengthsimple yle inP
i .
Let v be this vertex. Note that, these two onditions are mutually exlusive beause of
the way we have traversed P
i
. We never hit a vertex that simultaneously satises both the
onditions.
Case 1:Suppose v touhes P
j
, forsome j 2 fi+1;:::;kg. Letw bethe partner ofv in
I. (If v is odd, then w =v+1, else w =v 1.) Either the predeessor or the suessor of
v inP
j
has to bew. But inP
i
,w must bethe suessor of v; ifw had been the predeessor
of v inP
i
, then wewould have stopped our traversal at witself.
The orientation of the (v;w)edge in P
j
gives rise to two ases.
j i j
stik P
j
intoP
i
at v. Formally,map P toa plow sequene
P 0
=hP
1
;:::;P
i 1
;P 0
i
;P
i+1
;:::;P
j 1
;P
j+1
;:::P
k i
P 0
i
is obtained from P
i
by inserting into it the simple yle P
j
at the rst ourrene
of v. Figure7 illustratesthis ase.
(b) If the edge in P
j
is from w to v: (v,w) has opposite orientations in P
i
and P
j . We
annot stik P
j
into P
i
as is, beause then P
i
would lose the alternating property; it
would use two edges from the referene mathing onseutively. So rst reverse the
orientationofalledges inP
j
,and then insertthis plowintoP
i
atthe rstourrene
of v. Figure8 shows the mapping.
P i
w v
h v
w P j h’
w v
h
h’
P’ i
Figure 7: P
i
and P
j
have (v,w)oriented the same way.
P i
w v
h P j
v w
h’ h
v
w h’
P’ i
Figure8: P
i
and P
j
have (v,w) oriented dierently.
Case 2: Suppose v ompletes a simple yle P in P
i
. P must be disjoint from all the
later yles. Again, letw be the partnerof v inI. In P
i
, w must be the suessor of v; if w
had been the predeessor of v in P
i
, then a simple even yle would have been deteted at
w before v and we would have stopped our traversal at witself.
Wemodify the plowsequene P by plukingout P from P
i
and introduingitas anew
plow. P's position will be to the right of P
i
as the head of P
i
would be smaller than that
of P. Let h 0
be the smallest vertex withinP. There are now two sub-ases to onsider:
(a) In P
i
, h ours at the start of a p-edge: In this ase, P forms a syntatially valid
plow. We just plae P in the sequene tothe right of P
i
inthe appropriate position
ditated by P's head. Reall that in a valid plow sequene, heads of plows must
be instritly inreasing order. This ondition uniquely determinies the positionof P.
Formally,map P toa plow sequene
P 0
=hP
1
;:::;P
i 1
;P 0
i
;P
i+1
;:::;P
j 1
;P;P
j
;:::P
k i
P 0
i
is obtained from P
i
by deleting P from it, and the index j is suh that h(P
j 1 )<
h 0
= h(P) < h(P
j
). This resulting sequene will satisfy Case 1(a) and applying the
transformationthere will give bak P.
(b) InP
i , h
0
oursin the middleof a p-edge: Inthis ase,P doesnotformasyntatially
valid plow. However, the simple yle P 0
obtained by reversing all edges of P does,
sine nowwean start a traversal fromh 0
alternately usingarbitrary edges and edges
from I. (Note that we have splied and hanged the p-edges of P.) Again, as in the
preeding ase, the position of P 0
inthe plowsequene is uniquely determinedby h 0
,
and we map the plow sequene to
P 0
=hP
1
;:::;P
i 1
;P 0
i
;P
i+1
;:::;P
j 1
;P 0
;P
j
;:::P
k i
where P 0
i
and j are as before. This resulting sequene will satisfy Case 1(b) and
applying the transformationthere willgive bak P.
We need to argue the orretness of these mappings. It should be lear that the new
sequenes map bak to the original sequenes and hene the mappingis an involution. We
now show that the mapped plow sequenes have opposing signs, and as their weights are
idential, they anel eahother's ontribution.
Reallthatthe signisharaterizedbythenumberofplowsandthe numberof properly
oriented edges. In nding the mapped sequenes, we hange the parity of the number of
plows. The parity of the number of properly oriented edges remains unhanged, beause
the reversal of a plowor aneven length sub-yle preserves this. Thus, the mapped plow
sequenes indeedhave opposingsigns.
Plow sequenes arising from the superposition of the identity permutation with some
perfet mathing map onto themselves. Theseare the sole survivors.
4 A Combinatorial Algorithm for PfaÆans
In this setion we desribe a ombinatorial algorithmfor omputing the PfaÆan. We on-
strutalayereddireted ayligraph H
D
withthreespeial verties s,t
+
and t ,andshow
that the PfaÆan of D is preisely the Gap-Path funtion (reall denition 4) evaluated on
this graph. In this model of omputation,all s ; t
+
(s ; t ) paths of positive (negative)
sign in H
D
are in1-1 orrespondene with plow sequenes of positive(negative)sign.
H
D
has thevertexset, fs;t
+
;t g[f[p;h;u;i℄jp2f0;1g;h;u2[1;n℄;i2f0;:::;n 1gg.
A path from s to [p;h;u;i℄ indiates that in the plow sequene being onstruted along
urrent vertex on the plow and i is the number of edges seen so far. An s ; t
+
(s ;t )
path orresponds to aplowsequene havinga positive (negative) sign.
H
D
hasn layersand layerihasvertiesof theform[ ; ; ;i℄. The edgesfromlayer(2j-1)
tolayer 2j are xed and independent of D. The edges inH
D are:
1. hs;[0;h;h;0℄ifor h=2i 1, wherei2[1;
n
2
℄; edge weightis 1.
2. h[p;h;u;2i℄;[p;h;v;2i+1℄i,v >h, v >u, i2[0;
n
2
1℄;edge weight isd
uv .
3. h[p;h;u;2i℄;[p;h;v;2i+1℄i,v >h, v <u, i2[0;
n
2
1℄;edge weight isd
vu .
4. h[p;h;2j 1;2i 1℄;[p; h;2j;2i℄iif 2j 1>h,2i<n; edge weight is1.
5. h[p;h;2j;2i 1℄;[p;h;2j 1;2i℄iif 2j 1>h,2i<n; edge weight is1.
6. h[p;h;h+1;2i 1℄;[p;h 0
;h 0
;2i℄iif h 0
>h, h 0
is odd, 2i<n; edge weight is1.
7. h[0;h;h+1;n 1℄;t i and h[1;h;h+1;n 1℄;t
+
iif h=2i 1,i2[1;
n
2
℄; edgeweight
is 1.
Theorem 12 GivenaskewsymmetrimatrixD,letH
D
bethegraphdesribedabove. Then,
Pf(D)= X
: s ; t
+ wt()
X
: s ; t
wt()
Proof: We show a one-to-one orrespondene between s ; t
+
(s ; t ) paths and plow
sequenes of positive (negative)sign. Then,from Theorem 11the resultis immediate.
We utilizeour haraterization of the sign of a PfaÆan term asstated in Lemma10.
LetW =hP
1
;:::;P
k
ibeaplowsequene. Leth
i
betheheadofplowP
i ,n
i
thenumber
of forward edges in P
i , p
i
= (i+ P
i
j=1 n
j
)mod2 the parity of the partial plow sequene
hP
1
;:::;P
i
i,andm
i
thetotalnumberofedgesofthepartialplowsequenehP
1
;:::;P
i i. The
path we onstrut for W goes through the verties [p
i
;h
i+1
;h
i+1
;m
i
℄. We use an indutive
argumentto prove our result.
Suppose, aftertraversinghP
1
;:::;P
i
i,weare atthevertex [p
i
;h
i+1
;h
i+1
;m
i
℄. Inorderto
establishthe indutiveargument, itsuÆes toshowthat starting the traversal of P
i+1 from
this vertex, we willorretly reah[p
i+1
;h
i+2
;h
i+2
;m
i+1
℄.
LetP
i+1
=hh
i+1
;v
1
;:::;v
l
i. AsP
i+1
isavalidplow,thereisanedgefrom[p
i
;h
i+1
;h
i+1
;m
i
℄
to [p
i
;h
i+1
;v
1
;m
i
+ 1℄ in H
D
. As we traverse P
i+1
, there will be verties of the form
[p;h
i+1
;v
j
;m
i
+j℄ where p is the parity of p
i
and the number of forward edges upto v
j
in P
i+1
. When we reah the lastvertex v
l
=h
i+1
+1of P
i+1
, we would have hanged signs
as many as n
i+1
1 times. The last edge of any plow is always wrongly oriented and we
reah [p
i+1
;h
i+2
;h
i+2
;m
i+1
℄. Lemma 10tells usthat this is the proper way to alulate the
sign of a plow.
At layern, depending onwhether p
n
is +1 or 1,H
D
willhave anedge to t
+ ort .
To show the other diretion, onsider a path s ; t
+
. If we were to list out the path,
it will be a non-dereasing sequene with respet to the seond omponent of eah vertex.
omponent. The numberofparityhangesalongthissegmentwillexatlyequalthe number
offorward edgesalongthe pathplus one. This generatesa plowsequene orrespondingto
the s ;t
+
path and of even orientationparity. Similarly,eah s;t path orresponds to
a plowsequene of odd orientation parity.
Using simple dynami programming tehniques we an evaluate Pf(D) in polynomial
time. Thealgorithmproeedsin nstages, whereinthe i th
stage we omputethe sum of the
weighted paths from s to any vertex x in layer i. Layer n has verties t
+
and t , and we
ompute the dierene of the weighted paths from s to t
+
and t . This algorithmlooks at
anedge in H
D
one and hene isa polynomial-timealgorithm(O(n 4
) ring operations).
ThereareNCalgorithmsforevaluatingtheGap-Pathfuntionusingstandarddivide-and-
onquer tehniques. Hene, to evaluate Pf(D), a parallel algorithm would be to onstrut
a desription of H
D
as desribed above, and then use a parallel algorithm for Gap-Path.
When D has integerentries, the entire parallelalgorithmis in GapL.Thuswe have:
Theorem 13 Computing thePfaÆan of a skew-symmetrimatrix overintegers isin GapL.
Corollary 14 ComputingthePfaÆanof askew-symmetrimatrixoverintegersisomplete
for GapL underuniform projetions, even when the matrix isrestrited to have entries from
f 1;0;+1g.
When the entries of Dare fromanarbitraryommutativering,wean stilluse the same
algorithms,butweassumethatringoperationsareunitost. Withthismodel,thealgorithm
for omputing PfaÆan has omplexity as desribed below.
Theorem 15 ThePfaÆanof askew-symmetrinn matrixoveranyommutativeringan
be omputed byan arithmeti iruit with O(n 4
)gates and depth O(logn). The gates of the
iruitare of twotypes: (1) unboundedfaningatesomputingring addition,and(2) bounded
faningates omputing ring multipliation. Alternatively, the PfaÆanan be omputed byan
OROW PRAM performing O(n 6
) work and running in O(log 2
n) parallel time, assuming
unit ost per ring operation.
Complete proofs of the above theorems is omitted here beause they are idential to
analogous results about determinants appearing in [MV97℄. For more details about the
eÆient parallelimplementations and the GapLimplementation,see Setions 6.1 and 6.2 in
[MV97℄, where similaralgorithmsfor ounting alllow sequenes (the denition of sign and
weightisslightlydierent)are desribed; see also[Rot01℄foradierentNC algorithmbased
onthe same ombinatorialharaterisation of Theorem 11.
5 Finding PfaÆan orientations for Planar graphs
Counting the number of perfet mathings ina graph viaPfaÆans requires:
1. Finding a PfaÆan orientation of the graph. An orientation of a graph is said to be
PfaÆan if it gives the same sign to allperfet mathings.
undireted graph are +1.
We knowhow todothe latter fromthe previous setion. We alsoknowthat the general
problemof ounting thenumberofperfetmathingsinagraphis℄P-Complete. Inthis se-
tion,weshowthatbyrestritingourselvestoplanargraphs,weanndPfaÆanorientations
in GapL.This means that ounting perfet mathingsin planargraphs is inGapL.
We follownotationfrom [Kas67℄. A superposition yle is aneven length yle C whih
lies in the superposition of any two perfet mathings i.e. an even length simple yle for
whih G V(C) has a perfet mathing. Let G be an undireted graph, and onsider an
orientation of it yielding an oriented graph
~
G. The orientation is said to be admissible if
every superposition yle has an odd orientation in
~
G.
Lemma 16 [Kas67℄ Admissible orientations assign the same sign to all perfet mathings,
i.e. they are PfaÆan.
Admissible orientations ensure that eah PfaÆan term is positive, and hene the PfaÆan
orretly omputes the number of perfet mathings inthe graph.
Weshowthatanadmissibleorientation ofaplanargraph anbefound inGapLby using
a variantof Kasteleyn's algorithm.
Lemma 17 Given a planar graph G along with
1. a planar ombinatorial embedding, and
2. an ordering of the faes suh that eah fae has an edge not shared with any of the
earlier faes,
nding an admissible orientation of G is logspae reduible to the problem of evaluating a
parity tree.
Proof: We rst desribe, without proof, Kasteleyn's algorithm [Kas67℄ to unover an ad-
missible orientation. Assume that the planar graph is so enoded that the faes seen so far
forma simple onneted omponent. Start with any fae and dothe following,
1. Orient allunoriented edges exept one arbitrarily.
2. For the last edge, pik an orientation so that the yle bounding the fae has odd
orientationparity when traversed lokwise.
3. Continueif thereare unorientedfaesremaining. Pik anadjoiningfaesuhthat this
faetogether withthe otherorientedfaesformasimplyonneted region. Gotostep
1.
Planar graphs have the property that no edge is ommon to more than two faes. We
utilize this property inour logspae redution.
Suppose we are given the faes of the input planar graph. We an order them in many
ways as per the requirements of Kasteleyn's algorithm. Atually, the real requirement of
region,butthateahfaehasatleastone edgenotsharedwiththe earlierfaes. Oneway of
ndingsuhanorderingofthefaes,givenanyplanarombinatorialembedding,isdesribed
in[LP86℄; xany faeF (say the innitefae), and listfaesindereasingorder of distane
from F. Letus assume that any suh ordering isxed, say C
1
;C
2
;:::;C
k
. With respet to
thisorderingandKasteleyn'ssheme,eahfaeanbeuniquelyassoiatedwithanedgethat
has to have a spei orientation in order to maintain odd orientation parity. We denote
suh an edge as the ritial edge for the fae with respet to the fae ordering. Figure 9
providesan illustrationof ritialedges assoiated with faes.
e 1 C 1
e 1
e 2 C 2 e 2
e 3 C i
e 3
e 4 e 5 C k
. . . . . .
dependent edge critical edge
Figure9: CritialEdges assoiated with eahyle
Consider ayle C
i
inFig9. Thereanbethreetypesofedges onC
i
thatdetermine the
orientationof its ritialedge.
1. Non-ritialedges whose orientations were xed inyles C
j
,j <i.
2. Critialedges from the earlier yles C
j
, j <i.
3. Unoriented (or fresh) edges other than the ritial edge of C
i .
Wehavereformulatedtheproblemof ndinganadmissibleorientation ofaplanargraph
to one of nding the orientations of ritial edges so that eah fae has an odd number of
properly oriented edges. Let us pik a yle and nd the orientation for its ritial edge.
Wemust examine the orientationsof allother edges of this yle; they are of three typesas
desribed above.
Oriented non-ritial edges: As their orientations are xed, we need know the parity
of those amongthem that are properly oriented.
Oriented ritial edges: The orientations of these are xed in earlier yles. The
dierene being that we need to reompute them. One omputed, we take their
parity.
Fresh (unoriented) edges: We orient these lokwise, and hene we need to know the
parity of suh edges.
theproperlyoriented edgesinthe yle. Duringthisomputation,onenounteringaritial
edge of anearlieryle, its orientationis the outome of another parityomputationon the
edges onstituting its yle. This struture repeats along every ritial edge to give us a
omputation graph. We shall show that this graph is atually a tree where every internal
node is a parity node. Figure10 illustratesthis struture.
non-critical edges
...
... ...
critical edges
e 1 e 2
e 3
Figure 10: Parity Tree fornding the orientationof ritial edges onyles
Let e
j
be the ritialedge of anearlier faeC
j
appearingin faeC
i
(i.e. j <i). Finding
e
j
's orientation requires us to do a parity on the properly oriented edges in C
j
. Consider
some other ritial edge e
l
alsoappearing in C
i
. The omputation path from C
i
along the
paritynodeorrespondingtoe
l
willneverenounter e
j
. Thisisbeauseourinputisaplanar
graph,andheneanedgeisommontoatmosttwofaes. Therefore, allpathsfromaparity
node are non-interseting, and we haveour parity tree.
We need to show that this is a logspae redution. Note that we are assumingthat the
input is niely enoded. Determining whether the urrent edge of a fae is ritial, non-
ritial orfresh an be easilydone inlogspae by sanning the preeding input. Therefore,
given aparity node of the tree, we an identify the inomingars to itwithin logspae.
Wedeviate fromKasteleyn's shemeof identifying theritial edgeonayle. Wemake
the rst unoriented edge on a yle as the ritial edge. By doing this, things are simpler
beause we now do not need to spend valuableomputational resoures to identify the last
edge onthe yle.
We nowshow that parity tree evaluationis not aproblem of high omplexity; infat,
Lemma 18 Parity Tree Evaluation an be done in logspae.
Proof: Parity is assoiative and ommutative. Evaluating the parity of a sequene of ele-
mentsrequiresonetorememberonlytheparityoftheelementsseensofar. Hene,theparity
tree an be ollapsed. The parity of the leaves is therefore that of the tree. Systematially
ndingthese leaves an be done by a logspaemahine.
Theorem 19 Given a planar graph G along with
1. a planar ombinatorial embedding, and
2. an ordering of the faes suh that eah fae has an edge not shared with any of the
earlier faes,
ounting the number of perfet mathings in G an be done within GapL.
6 Disussion
We have desribed the rst NC algorithm for omputing the PfaÆan with its sign. This
algorithmis entirelyombinatorialin nature. What is more, this algorithm isdivision-free.
Is there any algebraiharaterisation of the sign, perhaps using divisions, that may yield
an algebrai NC algorithm for the problem? This and similar questions are also raised in
[Rot01℄.
Wehaveshownthat given a\reasonable"enoding ofaplanargraph,ounting the num-
ber of perfet mathings in it is in GapL. However, aepted versions of \reasonableness"
dier. What would be more satisfying is to know the omplexity of ounting the number
of perfet mathings in a graph, given that the graph is planar. While this is learly still
in NC, it is not immediatelylear that this is still in GapL. Note that given a planar om-
binatorialembedding,extrating anenoding suitable forthe algorithmof Setion5 an be
done in nondeterministi logspae NL. Further, a reent paper [AM00℄ shows that a planar
ombinatorialembeddingan befound, if one exists, in symmetrilogspaeSL. However, it
is not known if the harateristi funtionsof NL languages are omputable inGapL.
A relatedquestionthat immedatelyarisesis: whatisthe omplexity ofplanaritytesting
itself? CanthisbedoneinGapL?The bestknown upperboundsofar(paralleldeterministi
algorithm)isthatplanaritytestinganbedoneonaCRCWPRAMinO(logn)time[RR94℄,
and hene is in AC 1
. This algorithm alsoonstruts a planar embedding, if one exists. The
paper [AM00℄ further shows that planarity testing is sandwihed between the omplexity
lassesdeterministilogspaeandsymmetrilogspae,and inthenon-uniformsettingwhere
theselassesoinide,isompleteforthatlass. Howeveritsexatomplexityintheuniform
setting isstill not known.
For most problems, the deision, searh and ounting versions are ordered that way in
inreasingdiÆulty. Forperfetmathings,whenwerestritour attention toplanargraphs,
the order is reversed: ounting is easy (readNC), deisionis easybut onlybeauseone an
ount, and searh is not even known to be in NC. This is a baing situation; learly, one
expets anNC algorithmforsearh. Iftheplanar graphis furtherrestrited tobe bipartite,
searh is also known to be inNC [MN95℄. This result was reently extended tosmall genus
bipartitegraphs[MV00 ℄. However, wedonotknowofanyapproahtoremovingthebipartite
ondition.
Of ourse, the big question still remains open: what exatly is the omplexity of both
the deision and ounting versions of perfet mathings in generalgraphs?
TheauthorswouldliketothankGunterRoteforveryhelpfulommentsonanearlierversion
of the paper. The presentation in the urrent version is heavily inuened by extensive
disussions the rst author had with Jaikumar Radhakrishnan and Kasturi Varadarajan.
Thanks are alsodue to anonymous referees, whose remarks helped immenselyin improving
the presentation.
Referenes
[AM00℄ Eri Allender and Meena Mahajan. The omplexity of planarity testing. In
Pro. SymposiumonTheoretial Aspetsof Computing(STACS).LNCSvol.1770.
Springer, 2000. Toappear in Information and Computation.
[ARZ99℄ E.Allender, K.Rheinhardt, and S. Zhou. Isolation,mathing and ounting: uni-
form and nonuniform upper bounds. Journal of Computer and System Sienes,
59:164{181,1999.
[Bar83℄ F Barahona. Balaning signed toroidal graphs in polynomial time. Preprint,
University of Chile, 1983.
[CGM92℄ PMCamerini,GGalbiati,andFMaÆoli. Randompseudo-polynomialalgorithms
forexat matroidproblems. Journal of Algorithms,13:258{273, 1992.
[Dam91℄ C. Damm. DET=L (#L )
. Tehnial Report Informatik{Preprint 8, Fahbereih
Informatikder Humboldt{Universitatzu Berlin,1991.
[GL99℄ AGalluioand MLoebl. Onthe theoryof PfaÆanorientationsI: Perfet math-
ings and permanents. TheEletroni Journal of Combinatoris, R6,1999.
[GM94℄ G Galbiati and F MaÆoli. On the omputation of PfaÆans. Disrete Applied
Mathematis, 51:269{275,1994.
[Kas67℄ P W Kastelyn. Graph theory and rystal physis. In F Harary, editor, Graph
Theory and Theoretial Physis, pages 43{110.Aademi Press, 1967.
[Knu96℄ D E Knuth. Overlapping PfaÆans. The Eletroni Journal of Combinatoris,
3(2):R5,1996.
[Lan65℄ SLang. Algebra. Addison-Wesley, Reading,MA, 1965.
[Lit74℄ CH CLittle. AnextensionofKasteleyn's methodof enumeratingthe 1-fatorsof
planar graphs. In Combinatorial Mathematis, Pro. 2 nd
Australian Conferene,
pages 63{72.D.Holton,Leture Notes in Mathematis, 403, 1974.
[LP86℄ L Lovasz and M Plummer. Mathing Theory. North-Holland, 1986. Annals of
Disrete Mathematis 29.
Journal on Computing, 24:1002{1017, 1995.
[MV97℄ M. Mahajan and V Vinay. Determinant: ombinatoris, algo-
rithms, omplexity. Chiago Journal of Theoretial Computer Siene
http://www.s.uhiago.ed u/pu bli atio ns/ jt s, 1997:5, de 1997. Prelim-
inary version in Proeedings of the Eighth Annual ACM-SIAM Symposium on
Disrete AlgorithmsSODA 1997,730{738.
[MV00℄ M. Mahajan and K. Varadarajan. A new NC-algorithm for nding a perfet
mathinginplanarandboundedgenusgraphs.InProeedingsoftheThirty-Seond
AnnualACM Symposium onTheoryof Computing(STOC),pages351{357,2000.
[MVV87℄ KMulmuley,U Vazirani,andVVazirani. Mathingisaseasyasmatrixinversion.
Combinatoria,7(1):105{131,1987.
[Rot01℄ Gunter Rote. Division-free algorithms for the determinant and the pfaÆan: Al-
gebraiand ombinatorial approahes. In H. Alt, editor, Computational Disrete
Mathematis: Advaned Letures, volume LNCS 2122, pages 119{135. Springer,
2001.
[RR94℄ V.Ramahandranand J.Reif. Planaritytestingin parallel. Journal of Computer
and System Sienes, 49:517{561, 1994.
[Tod91℄ S.Toda. Countingproblemsomputationallyequivalenttothedeterminant.Teh-
nialReport CSIM 91-07, Deptof CompS &InformationMathematis, Univ of
Eletro-Communiations,Chofu-shi, Tokyo,1991.
[Val79℄ L.G.Valiant.Theomplexityofomputingthepermanent.TheoretialComputer
Siene, 8:189{201, 1979.
[Val92℄ L. G. Valiant. Why is boolean omplexity theory diÆult? In M. S. Paterson,
editor,Boolean Funtion Complexity. Cambridge University Press, 1992. London
MathematialSoiety Leture Notes Series 169.
[Vaz89℄ VVazirani.NCalgorithmsforomputingthenumberofperfetmathingsinK
3;3 -
free graphs and related problems. Information and Computation, 80(2):152{164,
1989.
[Vin91℄ VVinay. Counting auxiliarypushdown automataandsemi-unbounded arithmeti
iruits. In Proeedings of 6th Struture in Complexity Theory Conferene, pages
270{284,1991.
[Von99℄ Jan Vondrak. Implementation and testing of a new algorithm for the Max-Cut
problem. Master's thesis,Charles University, Prague,1999.
