Parity problems in planar graphs

Mark Braverman; Raghav Kulkarni; Sambuddha Roy

doi:10.1109/CCC.2007.23

Parity problems in planar graphs

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 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 2^k, 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 2^k, we also exhibit a highly parallel ⊕L algorithm for finding the value of a Permanent modulo 2^k. Previously, the best known result in this direction was Valiant's result that this problem lies in P.

Original language	English (US)
Title of host publication	Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007
Pages	222-235
Number of pages	14
DOIs	https://doi.org/10.1109/CCC.2007.23
State	Published - 2007
Externally published	Yes
Event	22nd Annual IEEE Conference on Computational Complexity, CCC 2007 - San Diego, CA, United States Duration: Jun 13 2007 → Jun 16 2007

Publication series

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

Other

Other	22nd Annual IEEE Conference on Computational Complexity, CCC 2007
Country/Territory	United States
City	San Diego, CA
Period	6/13/07 → 6/16/07

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2007.23

Cite this

@inproceedings{7c04e11ae40d47899501f506318ce16d,

title = "Parity problems in planar graphs",

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.",

author = "Mark Braverman and Raghav Kulkarni and Sambuddha Roy",

year = "2007",

doi = "10.1109/CCC.2007.23",

language = "English (US)",

isbn = "0769527809",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "222--235",

booktitle = "Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007",

note = "22nd Annual IEEE Conference on Computational Complexity, CCC 2007 ; Conference date: 13-06-2007 Through 16-06-2007",

}

Braverman, M, Kulkarni, R & Roy, S 2007, Parity problems in planar graphs. in Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007., 4262766, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 222-235, 22nd Annual IEEE Conference on Computational Complexity, CCC 2007, San Diego, CA, United States, 6/13/07. https://doi.org/10.1109/CCC.2007.23

TY - GEN

T1 - Parity problems in planar graphs

AU - Braverman, Mark

AU - Kulkarni, Raghav

AU - Roy, Sambuddha

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34748867980&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34748867980&partnerID=8YFLogxK

U2 - 10.1109/CCC.2007.23

DO - 10.1109/CCC.2007.23

M3 - Conference contribution

AN - SCOPUS:34748867980

SN - 0769527809

SN - 9780769527802

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 222

EP - 235

BT - Proceedings - Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007

T2 - 22nd Annual IEEE Conference on Computational Complexity, CCC 2007

Y2 - 13 June 2007 through 16 June 2007

ER -

Parity problems in planar graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this