Parameterized counting of partially injective homomorphisms

DOI10.1007/s00453-021-00805-yOpenAlexW3138370239WikidataQ114229329 ScholiaQ114229329MaRDI QIDQ2032353

Marc Roth

Publication date: 11 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00805-y

zbMATH Keywords

Möbius functiongraph homomorphismscounting problemsparameterized complexity theorymatroid lattices

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A dichotomy for real weighted Holant problems
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Combinatorics and complexity of partition functions
• The complexity of computing the permanent
• Holographic algorithms: from art to science
• The complexity of counting homomorphisms seen from the other side
• Counting induced subgraphs: a topological approach to \#W[1-hardness]
• Strong computational lower bounds via parameterized complexity
• An approximation trichotomy for Boolean \#CSP
• A note on the graph isomorphism counting problem
• Counting trees in a graph is \(\# \text{P}\)-complete
• Counting \(H-\)colorings of partial \(k-\)trees
• From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
• Computational complexity of counting problems on 3-regular planar graphs
• Parameterized counting of trees, forests and matroid bases
• Parametrized complexity theory.
• On tree width, bramble size, and expansion
• \(A\,V^ 2\) algorithm for determining isomorphism of planar graphs
• Homomorphisms of derivative graphs
• Tight lower bounds for certain parameterized NP-hard problems
• Parameterized counting problems
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• The statistics of dimers on a lattice
• Approximating the Permanent
• Holographic Algorithms
• The Complexity of Enumeration and Reliability Problems
• On the Structure of Polynomial Time Reducibility
• Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
• 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 the k -Biclique Problem
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Size Bounds for Factorised Representations of Query Results
• Counting Answers to Existential Questions
• Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
• Zeros of Holant problems: locations and algorithms
• Counting Matchings of Size k Is $\sharp$ W[1-Hard]
• Dimer problem in statistical mechanics-an exact result
• The complexity of satisfiability problems
• Parameterized Algorithms
• [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• Computational Complexity
• On the complexity of \(k\)-SAT

This page was built for publication: Parameterized counting of partially injective homomorphisms