## TAU Combinatorics Seminar 2020/21

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

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.