Counting edge-injective homomorphisms and matchings on restricted graph classes
From MaRDI portal
(Redirected from Publication:2321927)
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)
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
Cites work
- scientific article; zbMATH DE number 7075922 (Why is no real title available?)
- scientific article; zbMATH DE number 3290993 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- 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)
