The complexity of the existence of an m-cycle in a planar graph with n nodes

G is a flat graph with n nodes.
What is the difficulty of the following problems?

  • A: Does G contain an m-cycle? (m-cycle is a simple cycle with m nodes, m
  • B: the difficulty of counting all m-cycles in G.
  • What is the complexity of A and B if G is an arbitrary given graph?

Pointing to books and documents is also helpful ...

+3
source share

Source: https://habr.com/ru/post/1778578/


All Articles