TAU Combinatorics Seminar 2020/21

When: Sunday, October 25, 10am
Speaker: Lior Gishboliner, ETH Zurich
Title: Counting Subgraphs in Degenerate Graphs


We consider the problem of counting the number of copies of a fixed graph $H$ in an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has bounded degeneracy. This forms a rich class of graphs, which includes for example all non-trivial minor-closed classes (and in particular planar graphs).

Bera, Pashanasangi, and Seshadhri recently raised the question of characterizing the graphs $H$ such that counting $H$-copies in a bounded-degeneracy input graph can be done in linear time. In this work we fully resolve this question, as well as the analogous questions for counting $H$-homomorphisms and induced $H$-copies. A recent result of Bressan shows that one can count $H$-homomorphisms in a bounded-degeneracy graph in time $O(n^{\tau(H)})$, where $\tau$ is a suitable width parameter, called DAG treewidth. In particular, $H$-homomorphisms can be counted in linear time if $\tau(H) = 1$. We show that this sufficient condition is also necessary, namely that $H$-homomorphisms can be counted in linear time if and only if $\tau(H) = 1$. We then use this to resolve the aforementioned problem of Bera, Pashanasangi, and Seshadhri. Our proofs rely on several new ideas for proving hardness results in the context of subgraph-counting.

This is a joint work with Yevgeny Levanzov and Asaf Shapira.