Counting edge-injective homomorphisms and matchings on restricted graph classes
DOI10.4230/LIPICS.STACS.2017.25zbMATH Open1402.68087arXiv1702.05447MaRDI QIDQ4636623FDOQ4636623
Authors: Radu Curticapean, Holger Dell, Marc Roth 
Publication date: 19 April 2018
Full work available at URL: https://arxiv.org/abs/1702.05447
Recommendations
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Counting matchings of size \(k\) is \#W[1]-hard
- Parameterized counting of partially injective homomorphisms
- Weighted counting of \(k\)-matchings is \#W[1]-hard
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (7)
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Compactors for parameterized counting problems
- Counting problems in parameterized complexity
- Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
- Parameterized counting of partially injective homomorphisms
- Counting subgraphs in somewhere dense graphs
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
This page was built for publication: Counting edge-injective homomorphisms and matchings on restricted graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636623)
