检索结果-内蒙古大学图书馆

31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

作者： Roth, Marc Wellnitz, Philip Univ Oxford Merton Coll Oxford England Cluster Excellence MMCI Saarland Informat Campus Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus SIC Saarbrucken Germany

ISBN: (纸本)9781611975994

Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where both graphs H and G stem from given classes of graphs: H is an element of H and G is an element of g. By this, we combine the structurally restricted version of this problem (where the class g = T is the set of all graphs), with the language-restricted version (where the class H = T is the set of all graphs). The structurally restricted version allows an exhaustive complexity classification for classes H: Either we can count all homomorphisms in polynomial time (if the treewidth of H is bounded), or the problem becomes #W[1]-hard [Dalmau, Jonsson, ***'04]. In contrast, in this work, we show that the combined view most likely does not admit such a complexity dichotomy. Our main result is a construction based on Kneser graphs that associates every problem P in #W[1] with two classes of graphs H and G such that the problem P is equivalent to the problem #HOM(H -> g) of counting homomorphisms from a graph in H to a graph in G. In view of Ladner's seminal work on the existence of NP-intermediate problems [***'75] and its adaptations to the parameterized setting, a classification of the class #W[1] in fixed-parameter tractable and #W[1]-complete cases is unlikely. Hence, obtaining a complete classification for the problem #Hom(H -> g) seems unlikely. Further, our proofs easily adapt to W[1] and the problem of deciding whether a homomorphism between graphs exists. In search of complexity dichotomies, we hence turn to special graph classes. Those classes include line graphs, claw-free graphs, perfect graphs, and combinations thereof, and F-colorable graphs for fixed graphs F. As a special case, we obtain an easy proof of the parameterized intractability result of the problem of counting k-matchings in bipartite graphs.

关键词： parameterized complexity theory counting problems graph homomorphisms Kneser graphs

来源：评论

学校读者我要写书评

暂无评论

Bridging the gap between theory and practice of approximate Bayesian inference

引用

COGNITIVE SYSTEMS RESEARCH 2013年 24卷 2-8页

作者： Kwisthout, Johan van Rooij, Iris Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav NL-6525 HR Nijmegen Netherlands

In computational cognitive science, many cognitive processes seem to be successfully modeled as Bayesian computations. Yet, many such Bayesian computations have been proven to be computationally intractable (NP-hard) for unconstrained input domains, even if only an approximate solution is sought. This computational complexity result seems to be in strong contrast with the ease and speed with which humans can typically make the inferences that are modeled by Bayesian models. This contrast-between theory and practice-poses a considerable theoretical challenge for computational cognitive modelers: How can intractable Bayesian computations be transformed into computationally plausible 'approximate' models of human cognition? In this paper, three candidate notions of 'approximation' are discussed, each of which has been suggested in the cognitive science literature. We will sketch how (parameterized) computational complexity analyses can yield model variants that are tractable and which can serve as the basis of computationally plausible models of cognition. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Bayesian inference Approximation NP-hard parameterized complexity theory Algorithms Computational explanation

来源：评论

学校读者我要写书评

暂无评论

parameterized Random complexity

引用

theory OF COMPUTING SYSTEMS 2013年第2期52卷 221-270页

作者： Andres Montoya, Juan Mueller, Moritz Univ Ind Santander Escuela Matemat Bucaramanga Colombia Univ Vienna Kurt Godel Res Ctr Vienna Austria

The classes W[P] and W[1] are parameterized analogues of NP in that they can be characterized by machines with restricted existential nondeterminism. These machine characterizations give rise to two natural notions of parameterized randomized algorithms that we call W[P]-randomization and W[1]-randomization. This paper develops the corresponding theory.

关键词： parameterized complexity theory Random complexity Probability amplification Derandomization parameterized counting complexity Uniqueness problems

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of basic decision problems for tree automata

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2013年第6期90卷 1150-1170页

作者： Charatonik, Witold Chorowska, Agata Univ Wroclaw Inst Comp Sci PL-50383 Wroclaw Poland Univ Wroclaw Math Inst PL-50384 Wroclaw Poland

There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized complexity allows us to find new bounds of their nonpolynomial time algorithmic behaviours. We present results of such a study for classical TA, rigid tree automata, TA with global equality and disequality and t-DAG automata. As parameters we consider the number of states, the cardinality of the signature, the size of the term or the t-dag and the size of the automaton.

关键词： classical tree automata rigid tree automata tree automata with global equality and disequality t-DAG automata parameterized complexity theory

来源：评论

学校读者我要写书评

暂无评论

parameterized Counting of Partially Injective Homomorphisms

引用

ALGORITHMICA 2021年第6期83卷 1829-1860页

作者： Roth, Marc Saarland Informat Campus SIC Cluster Excellence MMCI Saarbrucken Germany Univ Oxford Merton Coll Oxford England

We study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixedparameter tractable and #W[1]-complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS 16) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC 17). Moreover, we invoke Rota's NBC-Theorem to obtain an explicit criterion for fixedparameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs.

关键词： parameterized complexity theory Counting problems Graph homomorphisms Matroid lattices Mobius function

来源：评论

学校读者我要写书评

暂无评论

A multiparametric view on answer set programming

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2019年第1-3期86卷 121-147页

作者： Fichte, Johannes K. Kronegger, Martin Woltran, Stefan Tech Univ Dresden Dresden Germany Johannes Kepler Univ Linz Linz Austria TU Wien Vienna Austria

Disjunctive answer set programming (ASP) is an important framework for declarative modeling and problem solving, where the computational complexity of basic decision problems like consistency (deciding whether a program has an answer set) is located on the second level of the polynomial hierarchy. During the last decades different approaches have been applied to find tractable fragments of programs, in particular, also using parameterized complexity. However, the full potential of parameterized complexity has not been unlocked since only one or very few parameters have been considered at once. In this paper, we consider several natural parameters for the consistency problem of disjunctive ASP. In addition, we also take the sizes of the answer sets into account;a restriction that is particularly interesting for applications requiring small solutions as encoding subset minimization problems in ASP can be done directly due to inherent minimization in its semantics. Previous work on parameterizing the consistency problem by the size of answer sets yielded mostly negative results. In contrast, we start from recent findings for the problem WMMSAT and show several novel fixed-parameter tractability (fpt) results based on combinations of parameters. Moreover, we establish a variety of hardness results (paraNP, W[2], and W[1]-hardness) to assess tightness of our parameter combinations.

关键词： Answer set programming (ASP) parameterized complexity theory Multiparametric complexity Fixed-parameter tractability Multi parameterizations

来源：评论

学校读者我要写书评

暂无评论

Bounded fixed-parameter tractability and reducibility

引用

ANNALS OF PURE AND APPLIED LOGIC 2007年第1-3期148卷 1-19页

作者： Downey, Rod Flum, Joerg Grohe, Martin Weyer, Mark Humboldt Univ D-10099 Berlin Germany Univ Victoria Sch Math Stat & Comp Sci Wellington New Zealand Univ Freiburg Abt Math Logik D-79104 Freiburg Germany

We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family F. For every family F of functions, this yields a notion of F-fixed-parameter tractability. If F is the class of all polynomially bounded functions, then F-fixed-parameter tractability coincides with polynomial time decidability and if F is the class of all computable functions, F-fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There are interesting choices of F between these two extremes, for example the class of all singly exponential functions. In this article, we study the general theory of F-fixed-parameter tractability. We introduce a generic notion of reduction and two classes F-W[P] and F-XP, which may be viewed as analogues of NP and EXPTIME, respectively, in the world of F-fixed-parameter tractability. (C) 2007 Elsevier B.V. All rights reserved.

关键词： parameterized complexity theory reductions

来源：评论

学校读者我要写书评

暂无评论

Probabilistic parameterized Polynomial Time 1

引用

45th International Conference on Current Trends in theory and Practice of Computer Science (SOFSEM)

作者： Donselaar, Nils Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Montessorilaan 3 NL-6525 HR Nijmegen Netherlands

ISBN: (数字)9783030108014

ISBN: (纸本)9783030108014;9783030108007

We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout in [15,16]. We prove that this class, for which we propose the shorthand name PPPT, has a robust definition and is in fact equal to the intersection of the classes paraBPP and PP. This result is accompanied by a Cook-style proof of completeness for the corresponding promise class (under a suitable notion of reduction) for parameterized approximation versions of the inference problem in Bayesian networks, which is known to be PP-complete. With these definitions and results in place, we proceed by showing how it follows from this that derandomization is equivalent to efficient deterministic approximation methods for the inference problem. Furthermore, we observe as a straightforward application of a result due to Drucker in [8] that these problems cannot have polynomial size randomized kernels unless the polynomial hierarchy collapses to the third level. We conclude by indicating potential avenues for further exploration and application of this framework.

关键词： parameterized complexity theory Randomized computation Bayesian networks

来源：评论

学校读者我要写书评

暂无评论

parameterized approximability of the disjoint cycle problem

Parameterized approximability of the disjoint cycle problem

引用

34th International Colloquium on Automata, Languages and Programming

作者： Grohe, Martin Grueber, Magdalena Humboldt Univ Inst Informat Unter Linden 6 D-10099 Berlin Germany

ISBN: (纸本)9783540734192

We give an fpt approximation algorithm for the directed vertex disjoint cycle problem. Given a directed graph G with n vertices and a positive integer k, the algorithm constructs a family of at least k/p(k) disjoint cycles of G if the graph G has a family of at least k disjoint cycles (and otherwise may still produce a solution, or just report failure). Here p is a computable function such that k/p(k) is nondecreasing and unbounded. The running time of our algorithm is polynomial. The directed vertex disjoint cycle problem is hard for the parameterized complexity class W[1], and to the best of our knowledge our algorithm is the first fpt approximation algorithm for a natural W[1]-hard problem.

关键词： approximation algorithms fixed-parameter tractability parameterized complexity theory

来源：评论

学校读者我要写书评

暂无评论

parameterized Completeness Results for Bayesian Inference 11

Parameterized Completeness Results for Bayesian Inference

引用

International Conference on Probabilistic Graphical Models

作者： Bodlaender, Hans L. Donselaar, Nils Kwisthout, Johan Univ Utrecht Dept Informat & Comp Sci Princetonpl 5 NL-3508 TB Utrecht Netherlands Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Thomas van Aquinostr 4 NL-6525 GD Nijmegen Netherlands

We present completeness results for inference in Bayesian networks with respect to two different parameterizations, namely the number of variables and the topological vertex separation number. For this we introduce the parameterized complexity classes W[1]PP and XLPP, which relate to W[1] and XNLP respectively as PP does to NP. The second parameter is intended as a natural translation of the notion of pathwidth to the case of directed acyclic graphs, and as such it is a stronger parameter than the more commonly considered treewidth. Based on a recent conjecture, the completeness results for this parameter suggest that deterministic algorithms for inference require exponential space in terms of pathwidth and by extension treewidth. These results are intended to contribute towards a more precise understanding of the parameterized complexity of Bayesian inference and thus of its required computational resources in terms of both time and space.

关键词： Bayesian networks inference parameterized complexity theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：