Approximately counting locally-optimal structures
作者：
Highlights：
• Approximately counting maximal independent sets in a bipartite graph is #SAT-hard.
• Replacing “maximal” by “maximum” yields #MAX-BIS, which is conjectured to be easier.
• Normally “maximum” problems are harder to solve than “maximal” problems, not easier.
• Approximately counting minimal separators in a bipartite graph is also #SAT-hard.
• How often is the usual pattern reversed in approximate counting?
摘要
•Approximately counting maximal independent sets in a bipartite graph is #SAT-hard.•Replacing “maximal” by “maximum” yields #MAX-BIS, which is conjectured to be easier.•Normally “maximum” problems are harder to solve than “maximal” problems, not easier.•Approximately counting minimal separators in a bipartite graph is also #SAT-hard.•How often is the usual pattern reversed in approximate counting?
论文关键词：Complexity,Approximate counting,Bipartite graphs,Maximal independent sets,Minimal separators
论文评审过程：Received 12 May 2015, Accepted 6 April 2016, Available online 14 April 2016, Version of Record 10 June 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.04.001
