A fixed-parameter perspective on \#BIS
From MaRDI portal
Publication:5111872
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
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
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- 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
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- FPTAS for \#BIS with degree bounds on one side
- Fundamentals of parameterized complexity
- Generalized model-checking over locally tree-decomposable classes
- Homomorphisms are a good basis for counting small subgraphs
- 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?)
- 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
Cited in
(10)- 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
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- A graph polynomial for independent sets of bipartite graphs
- FPTAS for \#BIS with degree bounds on one side
- Approximately counting locally-optimal structures
- \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- Bicolored independent sets and bicliques
- Stabilizing bisets
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)
