A fixed-parameter perspective on \#BIS
From MaRDI portal
Publication:5111872
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)
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
Cites work
- scientific article; zbMATH DE number 5595162 (Why is no real title available?)
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- A complexity classification of spin systems with an external field
- Computational complexity of counting problems on 3-regular planar graphs
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- FPTAS for \#BIS with degree bounds on one side
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Fundamentals of parameterized complexity
- Generalized model-checking over locally tree-decomposable classes
- Homomorphisms are a good basis for counting small subgraphs
- Large networks and graph limits
- On the complexity of \(k\)-SAT
- Parameterized algorithms
- Parametrized complexity theory.
- Randomized Approximations of Parameterized Counting Problems
- The Parameterized Complexity of Counting Problems
- The relative complexity of approximate counting problems
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Cited in
(10)- A graph polynomial for independent sets of bipartite graphs
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Stabilizing bisets
- Bicolored independent sets and bicliques
- Counting independent sets in cocomparability graphs
- FPTAS for \#BIS with degree bounds on one side
- A fixed-parameter perspective on \#BIS
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Approximately counting locally-optimal structures
- \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
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)
