@techreport{TR-IC-04-03,
number = {IC-04-03},
author = {Alberto Alexandre Assis Miranda and
ClĂˇudio Leonardo Lucchesi},
title = {Pfaffian Graphs},
month = {April},
year = {2004},
institution = {Institute of Computing, University of Campinas},
note = {In English, 25 pages.
\par\selectlanguage{english}\textbf{Abstract}
It is well known that, in general, the problem of determining
the number of perfect matchings of a graph is NP-hard. Some
graphs, called Pfaffian, have a special type of orientation
that is also called Pfaffian. Given a Pfaffian orientation of
a graph G, the number of perfect matchings of G may be
evaluated in polynomial time. Two (not necessarily Pfaffian)
orientations are similar if they differ by a cut. Similarity
is an equivalence relation on the collection of orientations of
a graph. If an orientation is Pfaffian then every similar
orientation is also Pfaffian.
\par
For any Pfaffian matching covered graph G, the number of
similarity classes of Pfaffian orientations of G is equal to
$2^b$, where b denotes the number of bricks of the tight cut
decomposition of G.
\par
The following four problems are polynomially equivalent, that
is, given a polynomial algorithm for any of the four problems
it is then possible to find polynomial algorithms for the other
three problems: (i) determine whether or not a graph is
Pfaffian, (ii) determine whether or not a given orientation of
a graph is Pfaffian, (iii) determine whether or not a graph is
Pfaffian, in case it is Pfaffian, find a Pfaffian orientation
for the graph, and (iv) determine the number of similarity
classes of Pfaffian orientations of a graph.
}
}