Counting Patterns in Degenerate Graphs in Constant Space

Balagopal Komarath, Anant Kumar, Akash Pareek

For a fixed pattern graph, we study the algorithmic complexity of counting homomorphisms, subgraph isomorphisms, and induced subgraph isomorphisms into an $n$-vertex, $d$-degenerat…