Counting edge-injective homomorphisms and matchings on restricted graph classes

DOI10.4230/LIPICS.STACS.2017.25zbMATH Open1402.68087arXiv1702.05447MaRDI QIDQ4636623FDOQ4636623

Marc Roth, Holger Dell, Radu Curticapean

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

zbMATH Keywords

parameterized complexitycounting complexityline graphsmatchingshomomorphisms

Mathematics Subject Classification ID

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 (5)

• Compactors for parameterized counting problems
• Parameterized counting matching and packing: a family of hard problems that admit FPTRAS
• Counting subgraphs in somewhere dense graphs
• Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
• Title not available (Why is that?)

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)