Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Counting Cycles on Planar Graphs in Subexponential Time

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study the problem of counting all cycles or self- avoiding walks (SAWs) on triangulated planar graphs. We present a subexponential \(2^{O(\sqrt{n})}\) time algorithm for this counting problem. Among the technical ingredients used in this algorithm are the planar separator theorem and a delicate analysis using pairs of Motzkin paths and Motzkin numbers. We can then adapt this algorithm to uniformly sample SAWs, in subexponential time. Our work is motivated by the problem of gerrymandered districting maps.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Algorithm 1
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. The algorithm in [4] is applicable for grid graphs only, and it was explicitly calculated that the number of self avoiding walks connecting two diagonal corners in a \(19 \times 19\) grid graph is 1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844, which is \(> 10^{88}\). Our algorithm for planar graphs is based on a recursive, thus different, approach.

  2. It is known that asymptotically we have \(\left|{\mathcal {L}}_{A} \right|\le O(3^{|E_{A}|})\).

  3. For simplicity in stating our results, we are not using optimal constants, see [11, 12, 16] for more details.

References

  1. Tiernan, J.C.: An efficient search algorithm to find the elementary circuits of a graph. Commun. ACM 13(12), 722–726 (1970)

    Article  MathSciNet  Google Scholar 

  2. Tarjan, R.: Enumeration of the elementary circuits of a directed graph. SIAM J. Comput. 2(3), 211–216 (1973)

    Article  MathSciNet  Google Scholar 

  3. Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1), 77–84 (1975)

    Article  MathSciNet  Google Scholar 

  4. Bousquet-Mélou, M., Guttmann, A.J., Jensen, I.: Self-avoiding walks crossing a square. J. Phys. A Math. Gen. 38(42), 9159 (2005)

    Article  MathSciNet  Google Scholar 

  5. Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790–810 (2010)

    Article  MathSciNet  Google Scholar 

  6. Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86–111 (2015)

    Article  MathSciNet  Google Scholar 

  7. Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169–188 (1986)

    Article  MathSciNet  Google Scholar 

  8. Najt, E., Deford, D., Solomon, J.: Complexity and geometry of sampling connected graph partitions.2019. arXiv preprint arXiv:1908.08881

  9. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)

    Article  MathSciNet  Google Scholar 

  10. Miller, G.L.: Finding small simple cycle separators for 2-connected planar graphs. J. Comput. Syst. Sci. 32(3), 265–279 (1986)

    Article  MathSciNet  Google Scholar 

  11. Alon, N., Seymour, P., Thomas, R.: Planar separators. SIAM J. Discret. Math. 7(2), 184–193 (1994)

    Article  MathSciNet  Google Scholar 

  12. Spielman, D.A., Teng, S.-H.: Disk packings and planar separators. In: Proceedings of the Twelfth Annual Symposium on Computational Geometry, pp. 349–358 (1996)

  13. Har-Peled, S.: A simple proof of the existence of a planar separator.2011. arXiv preprint arXiv:1105.0103

  14. Aigner, M.: Motzkin numbers. Eur. J. Comb. 19(6), 663–675 (1998)

    Article  MathSciNet  Google Scholar 

  15. Motzkin, T.: Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products. Bull. Am. Math. Soc. 54(4), 352–360 (1948)

    Article  MathSciNet  Google Scholar 

  16. Djidjev, H.N., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Inf. 34(3), 231–243 (1997)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Sciences Department, University of Wisconsin–Madison, 1210 W Dayton Street, Madison, 53706, WI, USA

    Jin-Yi Cai & Ashwin Maran

Authors
  1. Jin-Yi Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ashwin Maran
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors wrote and reviewed the main manuscript text.

Corresponding author

Correspondence to Ashwin Maran.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Support for this research was provided by the Office of VCRGE at UW-Madison with funding from WARF.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cai, JY., Maran, A. Counting Cycles on Planar Graphs in Subexponential Time. Algorithmica 86, 656–693 (2024). https://doi.org/10.1007/s00453-023-01182-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-023-01182-4

Keywords

Search

Navigation