scientific article; zbMATH DE number 7205197

DOI10.4230/LIPIcs.IPEC.2017.13zbMath1443.68125MaRDI QIDQ5111872

Fedor V. Fomin, Holger Dell, John Lapinskas, Radu Curticapean, Leslie Ann Goldberg

Publication date: 27 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

independent setsapproximate countingparameterised complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Counting independent sets in cocomparability graphs ⋮ Computing the number of induced copies of a fixed graph in a bounded degree graph ⋮ A fixed-parameter perspective on \#BIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Fundamentals of parameterized complexity
• Generalized model-checking over locally tree-decomposable classes
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• The relative complexity of approximate counting problems
• Computational complexity of counting problems on 3-regular planar graphs
• Parametrized complexity theory.
• FPTAS for #BIS with Degree Bounds on One Side
• A complexity classification of spin systems with an external field
• Randomized Approximations of Parameterized Counting Problems
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Parameterized Algorithms
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• On the complexity of \(k\)-SAT