Counting edge-injective homomorphisms and matchings on restricted graph classes
DOI10.1007/S00224-018-9893-YzbMATH Open1429.68080OpenAlexW2898827567WikidataQ114230787 ScholiaQ114230787MaRDI QIDQ2321927FDOQ2321927
Holger Dell, Marc Roth, Radu Curticapean
Publication date: 27 August 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7008/
Recommendations
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- Counting matchings of size \(k\) is \#W[1]-hard
- Weighted counting of \(k\)-matchings is \#W[1]-hard
- Parameterized counting of partially injective homomorphisms
- The complexity of counting in sparse, regular, and planar graphs
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)
Cites Work
- Title not available (Why is that?)
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Dimer problem in statistical mechanics-an exact result
- Title not available (Why is that?)
- The complexity of computing the permanent
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Parametrized complexity theory.
- Holographic Algorithms
- Title not available (Why is that?)
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- The strong perfect graph theorem
- When is the evaluation of conjunctive queries tractable?
- The complexity of counting homomorphisms seen from the other side
- Complexity of generalized satisfiability counting problems
- The complexity of counting in sparse, regular, and planar graphs
- Computational complexity of counting problems on 3-regular planar graphs
- Computational Complexity of Holant Problems
- Holographic algorithms: from art to science
- Tight lower bounds for certain parameterized NP-hard problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- The Parameterized Complexity of Counting Problems
- Approximating the permanent of graphs with large factors
- Maximum cut on line and total graphs
- Forbidden induced subgraphs for line graphs
- Generalized model-checking over locally tree-decomposable classes
- On the power of parity polynomial time
- Title not available (Why is that?)
- Homomorphisms are a good basis for counting small subgraphs
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Finding, minimizing, and counting weighted subgraphs
- Counting Matchings of Size k Is $\sharp$ W[1]-Hard
- Holographic algorithm with matchgates is universal for planar #CSP over boolean domain
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Disjoint triangles of a cubic line graph
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 Q2321927)
