Paper Info
Title
Space-Efficient Counting in Graphs on Surfaces
Abstract
We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2k, for constant k. On the other hand, we show that for any other modulus and in the non-modular case, our problem is as hard in the planar case as for the case of arbitrary graphs. The techniques used are algebraic topological that may be useful in many other problems involving planar or higher genus graphs – such as higher genus graph recognition in Logspace. In the spirit of counting problems modulo 2k, we also exhibit a highly parallel $$\oplus {\bf L}$$algorithm for finding the value of a permanent modulo 2k. Previously, the best known result in this direction was Valiant’s result that this problem lies in P. We also show that we can count the number of perfect matchings modulo 2k in an arbitrary graph in P. This extends Valiant’s result for the permanent, since the Permanent may be modeled as counting the number of perfect matchings in bipartite graphs.
Year
DOI
Venue
2009
10.1007/s00037-009-0266-4
Computational Complexity
Keywords
Field
DocType
planar case,57m15,known result,. counting problems,homology groups,planar graphs,non-modular case,par- ity l,permanent. subject classification. 05c85,arbitrary graph,perfect matchings modulo,permanent modulo,bipartite graph,planar graph,higher genus graph,problems modulo,68r10.,spanning tree
Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Counting problem,Book embedding,Cograph,Pathwidth,1-planar graph,Mathematics,Strong perfect graph theorem
Journal
Volume
Issue
ISSN
18
4
1420-8954
Citations 
PageRank 
References 
3
0.42
6
Authors
3
Name
Order
Citations
PageRank
Mark Braverman130.42
Raghav Kulkarni217219.48
Sambuddha Roy321919.23