License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.63
URN: urn:nbn:de:0030-drops-78311
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7831/
Roth, Marc
Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
Abstract
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 H_1,...,H_l to a big host graph G with the restriction that the coefficients correspond to evaluations of the Möbius function over the lattice of a graphic matroid. This generalizes the idea of Curticapean, Dell and Marx [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 provide a complete parameterized complexity dichotomy for counting such homomorphisms, that is, we identify classes of patterns for which the problem is fixed-parameter tractable (FPT), including an algorithm, and prove that all other pattern classes lead to #W[1]-hard problems. The main ingredients of the proof are the complexity classification of linear combinations of homomorphisms due to Curticapean, Dell and Marx [STOC 17] as well as a corollary of Rota's NBC Theorem which states that the sign of the Möbius function over a geometric lattice only depends on the rank of its arguments. 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 complexity assumptions. To prove this we show in an intermediate step that the subgraph counting problem remains #P-hard when both the pattern and the host 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.
BibTeX - Entry
@InProceedings{roth:LIPIcs:2017:7831,
author = {Marc Roth},
title = {{Counting Restricted Homomorphisms via M{\"o}bius Inversion over Matroid Lattices}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {63:1--63:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7831},
URN = {urn:nbn:de:0030-drops-78311},
doi = {10.4230/LIPIcs.ESA.2017.63},
annote = {Keywords: homomorphisms, matroids, counting complexity, parameterized complexity, dichotomy theorems}
}
|
Keywords: |
|
homomorphisms, matroids, counting complexity, parameterized complexity, dichotomy theorems |
|
Collection: |
|
25th Annual European Symposium on Algorithms (ESA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.09.2017 |
