A fixed-parameter perspective on \#BIS

DOI10.4230/LIPICS.IPEC.2017.13zbMATH Open1443.68125MaRDI QIDQ5111872FDOQ5111872

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

Publication date: 27 May 2020

Recommendations

• A fixed-parameter perspective on \#BIS
• FPTAS for \#BIS with degree bounds on one side
• \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard

zbMATH Keywords

approximate countingindependent setsparameterised 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)

Cites Work

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

Cited In (4)

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

This page was built for publication: A fixed-parameter perspective on \#BIS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111872)