Counting restricted homomorphisms via Möbius inversion over matroid lattices

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

Authors: 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

Recommendations

• Parameterized counting of partially injective homomorphisms
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Counting homomorphisms to trees modulo a prime
• Counting homomorphisms to trees modulo a prime
• Matroid invariants and counting graph homomorphisms

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?)
• A proof of the CSP dichotomy conjecture
• A second threshold for the hard‐core model on a Bethe lattice
• An approximation trichotomy for Boolean \#CSP
• Approximating the Permanent
• Computational complexity of Holant problems
• Computational complexity of counting problems on 3-regular planar graphs
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Counting matchings of size \(k\) is \#W[1]-hard
• Holographic Algorithms
• Holographic algorithms by Fibonacci gates
• Homomorphisms are a good basis for counting small subgraphs
• Homomorphisms of derivative graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Möbius functions of lattices
• On the Structure of Polynomial Time Reducibility
• On the foundations of combinatorial theory I. Theory of M�bius Functions
• Operations with structures
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Parameterized Complexity of Counting Problems
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• The complexity of counting in sparse, regular, and planar graphs
• The complexity of satisfiability problems
• The parameterized complexity of \(k\)-biclique

Cited In (9)

• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Matroid invariants and counting graph homomorphisms
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• Counting and Computing Join-Endomorphisms in Lattices
• Counting problems in parameterized complexity
• Counting edge-injective homomorphisms and matchings on restricted graph classes
• Parameterized counting of partially injective homomorphisms
• Counting induced subgraphs: a topological approach to \#W[1]-hardness
• 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)