Counting edge-injective homomorphisms and matchings on restricted graph classes
DOI10.1007/S00224-018-9893-YzbMATH Open1429.68080OpenAlexW2898827567WikidataQ114230787 ScholiaQ114230787MaRDI QIDQ2321927FDOQ2321927
Authors: Radu Curticapean, Holger Dell, Marc Roth 
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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Approximating the permanent of graphs with large factors
- Complexity of generalized satisfiability counting problems
- Computational complexity of Holant problems
- Computational complexity of counting problems on 3-regular planar graphs
- Counting matchings of size \(k\) is \#W[1]-hard
- Counting restricted homomorphisms via Möbius inversion over matroid lattices
- Dimer problem in statistical mechanics-an exact result
- Disjoint triangles of a cubic line graph
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Finding, minimizing, and counting weighted subgraphs
- Forbidden induced subgraphs for line graphs
- Generalized model-checking over locally tree-decomposable classes
- Holographic Algorithms
- Holographic algorithm with matchgates is universal for planar \#CSP over Boolean domain
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Holographic algorithms: from art to science
- Homomorphisms are a good basis for counting small subgraphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Large networks and graph limits
- Maximum cut on line and total graphs
- On the power of parity polynomial time
- Parametrized complexity theory.
- The Parameterized Complexity of Counting Problems
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The complexity of computing the permanent
- The complexity of counting homomorphisms seen from the other side
- The complexity of counting in sparse, regular, and planar graphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The strong perfect graph theorem
- Tight lower bounds for certain parameterized NP-hard problems
- Understanding the Complexity of Induced Subgraph Isomorphisms
- When is the evaluation of conjunctive queries tractable?
Cited In (2)
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)
