Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

DOI10.4230/LIPICS.ESA.2017.63zbMATH Open1442.68075arXiv1706.08414OpenAlexW2673671271MaRDI QIDQ5111752FDOQ5111752

Marc Roth

Publication date: 27 May 2020

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"obius 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'asz 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"obius function over a geometric lattice only depends on the rank of its arguments. We use the general theorem to classify the complexity of counting locally injective homomorphisms as well as homomorphisms that are injective in the r-neighborhood for constant r. Furthermore, we show that the former has "real" FPT cases by considering the subgraph counting problem restricted to trees on both sides. Finally we show that the dichotomy for counting graphically restricted homomorphisms readily extends to so-called linear combinations.

Full work available at URL: https://arxiv.org/abs/1706.08414

zbMATH Keywords

parameterized complexitycounting complexitymatroidshomomorphismsdichotomy theorems

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of matroids and geometric lattices (05B35) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• The complexity of computing the permanent
• Holographic algorithms by Fibonacci gates
• Holographic Algorithms
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of satisfiability problems
• The Parameterized Complexity of k-B<scp>iclique</scp>
• The complexity of counting homomorphisms seen from the other side
• An approximation trichotomy for Boolean \#CSP
• Approximating the Permanent
• The complexity of counting in sparse, regular, and planar graphs
• Computational complexity of counting problems on 3-regular planar graphs
• Computational Complexity of Holant Problems
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Homomorphisms of derivative graphs
• The Parameterized Complexity of Counting Problems
• Möbius functions of lattices
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Operations with structures
• Homomorphisms are a good basis for counting small subgraphs
• Title not available (Why is that?)
• Counting Matchings of Size k Is $\sharp$ W[1]-Hard
• A second threshold for the hard‐core model on a Bethe lattice
• A Proof of the CSP Dichotomy Conjecture

Cited In (7)

• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Counting and Computing Join-Endomorphisms in Lattices
• Parameterized counting of partially injective homomorphisms
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting Answers to Existential Questions

This page was built for publication: Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111752)