Publication Overview

Marc Roth

Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

We present a framework for the complexity classification of parameterized counting problems that can be formulated as the summation over the numbers of homomorphisms from small pattern graphs to a big host graph with the restriction that the coefficients correspond to evaluations of the Moebius function over the lattice of a graphic matroid. This generalizes the idea of Curticapean et al [STOC 17] who used a result of Lovász stating that the number of subgraph embeddings from a graph H to a graph G can be expressed as such a sum over the lattice of partitions of H. In the first step we introduce what we call graphically restricted homomorphisms that, inter alia, generalize subgraph embeddings as well as locally injective homomorphisms. We then provide a complete complexity dichotomy (FPT / #W[1]) for counting such homomorphisms including an algorithm for the (fixed parameter) tractable cases. The main ingredients of the proof are the complexity classification of linear combinations of homomorphisms due to Curticapean et al [STOC 17] as well as a corollary of Rota's NBC Theorem which states that the sign of the Moebius function over a geometric lattice only depends on the rank of its arguments. After that we apply the general theorem to the problem of counting locally injective homomorphisms from small pattern graphs to big host graphs yielding a concrete dichotomy criterion. It turns out that - in contrast to subgraph embeddings - counting locally injective homomorphisms has "real" FPT cases, that is, cases that are fixed parameter tractable but not polynomial time solvable under standard assumptions. To prove this we show in an intermediate step that the subgraph counting problem remains #P-hard when both graphs are restricted to be trees. We then investigate the more general problem of counting homomorphisms that are injective in the r-neighborhood of every vertex. As those are graphically restricted as well, they can also easily be classified via the general theorem. Finally we show that the dichotomy for counting graphically restricted homomorphisms readily extends to so-called linear combinations.

Published in: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria
Year: 2017
Pages: 63:1--63:14