...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Treewidth with a Quantifier Alternation Revisited
【24h】

Treewidth with a Quantifier Alternation Revisited

机译：重用量词替换的树宽

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we take a closer look at the parameterized complexity of existsorall SAT, the prototypical complete problem of the class Sigma_2^p, the second level of the polynomial hierarchy. We provide a number of tight fine-grained bounds on the complexity of this problem and its variants with respect to the most important structural graph parameters. Specifically, we show the following lower bounds (assuming the ETH): - It is impossible to decide existsorall SAT in time less than double-exponential in the input formula's treewidth. More strongly, we establish the same bound with respect to the formula's primal vertex cover, a much more restrictive measure. This lower bound, which matches the performance of known algorithms, shows that the degeneration of the performance of treewidth-based algorithms to a tower of exponentials already begins in problems with one quantifier alternation. - For the more general existsorall CSP problem over a non-boolean domain of size B, there is no algorithm running in time 2^{B^{o(vc)}}, where vc is the input's primal vertex cover. - existsorall SAT is already NP-hard even when the input formula has constant modular treewidth (or clique-width), indicating that dense graph parameters are less useful for problems in Sigma_2^p. - For the two weighted versions of existsorall SAT recently introduced by de Haan and Szeider, called exists_korall SAT and existsorall_k SAT, we give tight upper and lower bounds parameterized by treewidth (or primal vertex cover) and the weight k. Interestingly, the complexity of these two problems turns out to be quite different: one is double-exponential in treewidth, while the other is double-exponential in k. We complement the above negative results by showing a double-exponential FPT algorithm for QBF parameterized by vertex cover, showing that for this parameter the complexity never goes beyond double-exponential, for any number of quantifier alternations.
机译：在本文中，我们仔细研究了 exists forall SAT的参数化复杂度，即Sigma_2 ^ p类的原型完全问题，多项式层次结构的第二级。关于这个问题及其相对于最重要的结构图参数的变体的复杂性，我们提供了许多严格的细粒度界限。具体来说，我们显示了以下下限（假设ETH）：-无法在输入公式的树宽中确定 exists forall SAT的时间小于双指数。更重要的是，我们对公式的原始顶点覆盖范围建立了相同的界线，这是一个更为严格的度量。这个下限与已知算法的性能相匹配，表明基于树宽的算法的性能退化为指数塔已经开始于一个量词交替的问题。 -对于大小为B的非布尔域上更普遍的 exists forall CSP问题，没有算法在时间2 ^ {B ^ {o（vc）}}中运行，其中vc是输入的原始顶点覆盖。 - exists forall SAT即使输入公式具有恒定的模块化树宽（或集团宽度），也已经具有NP难度，这表明密集图参数对于Sigma_2 ^ p中的问题不太有用。 -对于de Haan和Szeider最近引入的 exists forall SAT的两个加权版本，称为 exists_k forall SAT和 exists forall_k SAT，我们给出了由树宽（或原始顶点覆盖）参数化的紧密上下限，并且重量k。有趣的是，这两个问题的复杂度完全不同：一个是树宽的双指数，而另一个是k的双指数。我们通过显示由顶点覆盖参数化的QBF的双指数FPT算法，补充了上述负面结果，表明对于任何数量的量词替换，此参数的复杂度都不会超过双指数。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号