Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices

DOI10.4230/LIPIcs.ESA.2017.63zbMath1442.68075arXiv1706.08414OpenAlexW2673671271MaRDI QIDQ5111752

Marc Roth

Publication date: 27 May 2020

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

zbMATH Keywords

homomorphismsmatroidsparameterized complexitycounting complexitydichotomy theorems

Mathematics Subject Classification ID

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

Related Items

Unnamed Item, Unnamed Item, Parameterized counting of partially injective homomorphisms, Counting Answers to Existential Questions, Counting edge-injective homomorphisms and matchings on restricted graph classes, Counting induced subgraphs: a topological approach to \#W[1-hardness]

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• An approximation trichotomy for Boolean \#CSP
• Möbius functions of lattices
• Holographic algorithms by Fibonacci gates
• Computational complexity of counting problems on 3-regular planar graphs
• Homomorphisms of derivative graphs
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Computational Complexity of Holant Problems
• Approximating the Permanent
• 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
• Counting Unlabelled Subtrees of a Tree is #P-complete
• The Parameterized Complexity of Counting Problems
• A second threshold for the hard‐core model on a Bethe lattice
• Homomorphisms are a good basis for counting small subgraphs
• A Proof of the CSP Dichotomy Conjecture
• Counting Matchings of Size k Is $\sharp$ W[1-Hard]
• The Parameterized Complexity of k-B<scp>iclique</scp>
• The complexity of satisfiability problems
• Operations with structures
• [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]