Parity problems in planar graphs

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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. This completely settles the question regarding the complexity of modular computation of the number of spanning trees in planar graphs. The techniques used rely heavily on algebraic-topology. In the spirit of counting problems modulo 2k, we also exhibit a highly parallel ⊕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.

Original languageEnglish (US)
Title of host publicationProceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007
Pages222-235
Number of pages14
DOIs
StatePublished - Oct 2 2007
Externally publishedYes
Event22nd Annual IEEE Conference on Computational Complexity, CCC 2007 - San Diego, CA, United States
Duration: Jun 13 2007Jun 16 2007

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other22nd Annual IEEE Conference on Computational Complexity, CCC 2007
CountryUnited States
CitySan Diego, CA
Period6/13/076/16/07

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Parity problems in planar graphs'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Kulkarni, R., & Roy, S. (2007). Parity problems in planar graphs. In Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007 (pp. 222-235). [4262766] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2007.23