Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexitytheory. In this work, we study the case where both graphs H and G stem from given classes of g...
详细信息
ISBN:
(纸本)9781611975994
Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexitytheory. 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.
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) ...
详细信息
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.
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...
详细信息
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.
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 comp...
详细信息
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 parameterizedcomplexity 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.
We study the parameterizedcomplexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorph...
详细信息
We study the parameterizedcomplexity 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 parameterizedcomplexity depending on the class of allowed pattern graphs.
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 progr...
详细信息
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 parameterizedcomplexity. However, the full potential of parameterizedcomplexity 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.
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 ...
详细信息
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.
We examine a parameterizedcomplexity 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...
详细信息
ISBN:
(数字)9783030108014
ISBN:
(纸本)9783030108014;9783030108007
We examine a parameterizedcomplexity 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.
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 c...
详细信息
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 parameterizedcomplexity 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.
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 th...
详细信息
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 parameterizedcomplexity 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 parameterizedcomplexity of Bayesian inference and thus of its required computational resources in terms of both time and space.
暂无评论