发帖
雷达卡
摘要翻译：
在困难组合问题的实例中，有各种方法可以利用“隐藏结构”来允许比一般非结构化或随机实例更快的算法。对于SAT及其计数版本#SAT，隐藏结构在可分解性和强大的后门集方面得到了利用。可分解性可以根据与给定CNF公式相关联的图的树宽来考虑，例如，通过将子句和变量视为图的顶点，并使一个变量与它出现的所有子句相邻。另一方面，CNF公式的强后门集合是一组变量，使得对该集合的每个可能的部分赋值都将公式移动到一个固定的类中，对于该类(#)SAT可以在多项式时间内求解。本文将上述两种方法结合起来。特别地，我们研究了在CNF公式类W_t中寻找一个小强后门集的算法问题，其关联图的树宽最多为T。主要结果是肯定的：（1）在给定一个CNF公式F和两个常数k，T\ge0的情况下，有一个三次算法，它要么找到一个最多2^k大小的强W_t-backdoor集，要么得出F不存在最多k大小的强W_t-backdoor集。（2）对于任意一对常数k,t\ge0,在给定CNF公式F的情况下，有一个三次算法计算F的满足赋值个数或得出sb_t(F)>k。这里，sb_t(F)表示F的最小强W_t-后门集的大小。我们的结果的意义在于，它们允许我们在算法上利用公式中的一个隐藏结构，这是两种方法（可分解性，后门）中的任何一种都无法单独访问的。树宽1之上的后门尺寸1（即，sb_1(F)=1)已经包含任意大树宽和任意大循环割集的公式。
---
英文标题：
《Strong Backdoors to Bounded Treewidth SAT》
---
作者：
Serge Gaspers and Stefan Szeider
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Data Structures and Algorithms 数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Computational Complexity 计算复杂度
分类描述：Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
涵盖计算模型，复杂度类别，结构复杂度，复杂度折衷，上限和下限。大致包括ACM学科类F.1（抽象设备的计算）、F.2.3（复杂性度量之间的权衡）和F.4.3（形式语言）中的材料，尽管形式语言中的一些材料可能更适合于计算机科学中的逻辑。在F.2.1和F.2.2中的一些材料可能也适用于这里，但更有可能以数据结构和算法作为主要主题领域。
--
一级分类：Computer Science 计算机科学
二级分类：Discrete Mathematics 离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：Mathematics 数学
二级分类：Combinatorics 组合学
分类描述：Discrete mathematics, graph theory, enumeration, combinatorial optimization, Ramsey theory, combinatorial game theory
离散数学，图论，计数，组合优化，拉姆齐理论，组合对策论
--
---
英文摘要：
There are various approaches to exploiting "hidden structure" in instances of hard combinatorial problems to allow faster algorithms than for general unstructured or random instances. For SAT and its counting version #SAT, hidden structure has been exploited in terms of decomposability and strong backdoor sets. Decomposability can be considered in terms of the treewidth of a graph that is associated with the given CNF formula, for instance by considering clauses and variables as vertices of the graph, and making a variable adjacent with all the clauses it appears in. On the other hand, a strong backdoor set of a CNF formula is a set of variables such that each possible partial assignment to this set moves the formula into a fixed class for which (#)SAT can be solved in polynomial time. In this paper we combine the two above approaches. In particular, we study the algorithmic question of finding a small strong backdoor set into the class W_t of CNF formulas whose associated graphs have treewidth at most t. The main results are positive: (1) There is a cubic-time algorithm that, given a CNF formula F and two constants k,t\ge 0, either finds a strong W_t-backdoor set of size at most 2^k, or concludes that F has no strong W_t-backdoor set of size at most k. (2) There is a cubic-time algorithm that, given a CNF formula F, computes the number of satisfying assignments of F or concludes that sb_t(F)>k, for any pair of constants k,t\ge 0. Here, sb_t(F) denotes the size of a smallest strong W_t-backdoor set of F. The significance of our results lies in the fact that they allow us to exploit algorithmically a hidden structure in formulas that is not accessible by any one of the two approaches (decomposability, backdoors) alone. Already a backdoor size 1 on top of treewidth 1 (i.e., sb_1(F)=1) entails formulas of arbitrarily large treewidth and arbitrarily large cycle cutsets.
---
PDF链接：
https://arxiv.org/pdf/1204.6233
京公网安备 11010802022788号
