Pfaffian graphs and related problems

• Grant number: 05/04426-6
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: September 01, 2006
• End date: October 31, 2009
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cláudio Leonardo Lucchesi
• Grantee: Alberto Alexandre Assis Miranda
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

This project's goal is to define some Pfaffian graphs related problems complexity class (P, NP, co-NP, NP-complete, etc). Pfaffian graphs are the graph whose edges can be oriented such that each conformal circuit with an even number of vertices has an odd orientation. No characterization is known for any Pfaffian graphs. It is not even known whether the problem of determining if a given graph is Pfaffian is in NP or in co-NP. However, the problem has a polynomial time solution when it is restricted to bipartite graphs. The Pfaffian bipartite graph characterization was proved by Little thirty years ago. However, only during the last few years polynomial time algorithms for this problem were discovered, by McCuaig and, independently, by Robertson, Seymour and Thomas. Also, every planar graph is Pfaffian. These are the only graph classes, until today, for which a polynomial time algorithm to decide whether a graph is Pfaffian is known. The work developed during the candidates master included the study of the Pfaffian bipartited graph recognition algorithm. The candidate's master dissertation presents a new correctness proof to the algorithm. This proof is different to the two previously know proofs. Now, during the PhD, open problems about Pfaffian graphs are intended to be researched. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

MIRANDA‚ A.A.A.; LUCCHESI‚ C.L.. Recognizing near-bipartite Pfaffian graphs in polynomial time. DISCRETE APPLIED MATHEMATICS, v. 158, n. 12, p. 1275-1278, 2010. (05/04426-6)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

MIRANDA, Alberto Alexandre Assis. Pfaffian graphs and related problems. 2009. Doctoral Thesis - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.