2008/12/07 by Javaid Aslam, Aslam, Javaid · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0812.1385
Revisions: Some re-organization-- created a new Section 5 and minor revisions
openalex publication_date 2008/12/07 · openalex created_date 2017/09/15 · arxiv created 2017/10/30 · arxiv updated 2017/10/31 · openalex updated_date 2026/07/28
The distinguishing result of this paper is a P-time enumerable partition of all the potential perfect matchings in a bipartite graph. This partition is a set of equivalence classes induced by the missing edges in the potential perfect matchings. We capture the behavior of these missing edges in a polynomially bounded representation of the exponentially many perfect matchings by a graph theoretic structure, called MinSet Sequence, where MinSet is a P-time enumerable structure derived from a graph theoretic counterpart of a generating set of the symmetric group. This leads to a polynomially bounded generating set of all the classes, enabling the enumeration of perfect matchings in polynomial time. The sequential time complexity of this #P-complete problem is shown to be O(n45log n). And thus we prove a result even more surprising than NP = P, that is, #P=FP, where FP is the class of functions, f: \0, 1\^* → ℕ , computable in polynomial time on a deterministic model of computation.