Approximately counting locally-optimal structures

DOI10.1016/J.JCSS.2016.04.001zbMATH Open1342.68163OpenAlexW2149592811MaRDI QIDQ295655FDOQ295655

Authors: Leslie Ann Goldberg, Rob Gysel, John Lapinskas 

Publication date: 13 June 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.04.001

Recommendations

• Approximately Counting Locally-Optimal Structures
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• Approximately counting \(H\)-colorings is \(\#\)BIS-hard
• \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

zbMATH Keywords

complexityapproximate countingbipartite graphsmaximal independent setsminimal separators

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Cites Work

• Treewidth computation and extremal combinatorics
• On exact algorithms for treewidth
• Title not available (Why is that?)
• The relative complexity of approximate counting problems
• A New Algorithm for Generating All the Maximal Independent Sets
• The Complexity of Ferromagnetic Ising with Local Fields
• On Unapproximable Versions of $NP$-Complete Problems
• How easy is local search?
• Approximately Counting Locally-Optimal Structures
• Efficient enumeration of all minimal separators in a graph
• Listing all potential maximal cliques of a graph
• Tree decompositions with small cost
• A revisit of the scheme for computing treewidth and minimum fill-in
• Treewidth and minimum fill-in: Grouping the minimal separators
• The complexity of counting in sparse, regular, and planar graphs
• Graph theory
• The complexity of approximately counting tree homomorphisms
• Dominating Set Counting in Graph Classes
• Finding induced subgraphs via minimal triangulations
• Simple Local Search Problems that are Hard to Solve
• Exact Algorithms for Treewidth and Minimum Fill-In
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• Efficient Algorithms for Listing Combinatorial Structures
• Listing all Minimal Separators of a Graph
• Planar Graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Minimal Triangulation Algorithms for Perfect Phylogeny Problems
• Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph
• On the complexity of computing treelength

Cited In (5)

• Title not available (Why is that?)
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Counting minimal transversals of \(\beta\)-acyclic hypergraphs
• Approximately Counting Locally-Optimal Structures
• Counting independent sets in cocomparability graphs

This page was built for publication: Approximately counting locally-optimal structures

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