A fixed-parameter perspective on \#BIS
DOI10.4230/LIPICS.IPEC.2017.13zbMATH Open1443.68125MaRDI QIDQ5111872FDOQ5111872
Authors: Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, John Lapinskas 
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
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
- Large networks and graph limits
- 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 (10)
- A graph polynomial for independent sets of bipartite graphs
- Stabilizing bisets
- \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
- 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
- Bicolored independent sets and bicliques
- Approximately counting locally-optimal structures
- FPTAS for \#BIS with degree bounds on one side
- 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)
