Search

Given a graph property \Phi, the problem \#IndSub(\Phi) asks, on input of a graph G and a positive integer k, to compute the number \#\sansI \sansn \sansd \sansS \sansu \sansb (\Phi, k \rightarrow G) of induced subgraphs of size k in G that satisfy \Phi. The search for explicit criteria on \Phi ensuring that \#IndSub(\Phi) is hard was initiated by Jerrum and Meeks [J. Comput. System Sci., 81 (2015), pp. 702--716] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell, and Marx [STOC, ACM, New York, pp. 151--158] proving that a full classification into "easy"" and "hard"" properties is possible and some partial results on edge-monotone properties due to Meeks [Discrete Appl. Math., 198 (2016), pp. 170--194] and D\"orfler et al. [MFCS, LIPIcs Leibniz Int. Proc. Inform. 138, Wadern Germany, 2019, 26], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is, subgraph-closed, properties: We show that for any nontrivial monotone property \Phi, the problem \#IndSub(\Phi) cannot be solved in time f(k)\cdot | V (G)| o(k/log1/2(k)) for any function f, unless the exponential time hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a \#\sansW [\sansone ]-completeness result. The methods we develop for the above problem also allow us to prove a conjecture by Jerrum and Meeks [ACM Trans. Comput. Theory, 7 (2015), 11; Combinatorica 37 (2017), pp. 965--990]: \#IndSub(\Phi) is \#\sansW [\sansone ]-complete if \Phi is a nontrivial graph property only depending on the number of edges of the graph. [ABSTRACT FROM AUTHOR]

The betweenness centrality of a graph vertex measures how often this vertex is visited on shortest paths between other vertices of the graph. In the analysis of many real-world graphs or networks, the betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In particular, it is among the most popular tools in social network analysis. In recent years, a growing number of real-world networks have been modeled as temporal graphs instead of conventional (static) graphs. In a temporal graph, we have a fixed set of vertices and there is a finite discrete set of time steps, and every edge might be present only at some time steps. While shortest paths are straightforward to define in static graphs, temporal paths can be considered "optimal" with respect to many different criteria, including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of temporal betweenness centrality , posing new challenges on the algorithmic side. We provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths. Computing the betweenness centrality for vertices in a graph is closely related to counting the number of optimal paths between vertex pairs. While in static graphs computing the number of shortest paths is easily doable in polynomial time, we show that counting foremost and fastest paths is computationally intractable (#P-hard), and hence, the computation of the corresponding temporal betweenness values is intractable as well. For shortest paths and two selected special cases of foremost paths, we devise polynomial-time algorithms for temporal betweenness computation. Moreover, we also explore the distinction between strict (ascending time labels) and non-strict (non-descending time labels) time labels in temporal paths. In our experiments with established real-world temporal networks, we demonstrate the practical effectiveness of our algorithms, compare the various betweenness concepts, and derive recommendations on their practical use. [ABSTRACT FROM AUTHOR]

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L (v) ⊆ V(H) for every v∈ V(G), a f:V(G)→ V(H) that preserves the edges (i.e., uv∈ E(G) implies f(u)f(v)∈ E(H)) and respects the lists (i.e., f(v)∈ L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time |V(H)|t⋅ n(1). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H, we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. It follows from earlier results that if irr(H)=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from (G,L) to H — can be counted in time \(\operatorname{irr}(H)^t\cdot n^{\mathcal {O}(1)}\) if a tree decomposition of G having width at most t is given in the input, and, — given that \(\operatorname{irr}(H)\ge 2\) , cannot be counted in time \((\operatorname{irr}(H)-\varepsilon)^t\cdot n^{\mathcal {O}(1)}\) for any \(\varepsilon \gt 0\) , even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops. [ABSTRACT FROM AUTHOR]

We study the computational complexity of the problem #IndSub(Φ) of counting k-vertex induced subgraphs of a graph G that satisfy a graph property Φ. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): - If a hereditary property Φ is true for all graphs, or if it is true only for finitely many graphs, then #IndSub(Φ) is solvable in polynomial time. - Otherwise, #IndSub(Φ) is #W[1]-complete when parameterised by k, and, assuming ETH, it cannot be solved in time f(k)µ/G/o(k) for any function f. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [TCS 02]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As additional result, we also present an exhaustive and explicit parameterised complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalise some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of #IndSub(Φ) for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [FOCS 20]. [ABSTRACT FROM AUTHOR]

Logarithmic space-bounded complexity classes such as L and NL play a central role in space-bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space-bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space-bounded models developed by Elberfeld, Stockhusen and Tantau. They defined the operators para W and para β for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators para W and para β by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, para W [ 1 ] and para β tail . Then, we consider counting versions of all four operators and apply them to the class L . We obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0, 1)-matrices is # para β tail L -hard and can be written as the difference of two functions in # para β tail L . These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of # para β tail L under parameterised logspace parsimonious reductions coincides with # para β L . In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research. [ABSTRACT FROM AUTHOR]

The overall purpose of the present work is to lay the foundations for a new approach to bridge logic and probabilistic computation. To this aim we introduce extensions of classical and intuitionistic propositional logic with counting quantifiers , that is, quantifiers that measure to which extent a formula is true. The resulting systems, called cCPL and iCPL , respectively, admit a natural semantics, based on the Borel σ -algebra of the Cantor space, together with a sound and complete proof system. Our main results consist in relating cCPL and iCPL with some central concepts in the study of probabilistic computation. On the one hand, the validity of cCPL -formulae in prenex form characterizes the corresponding level of Wagner's hierarchy of counting complexity classes, closely related to probabilistic complexity. On the other hand, proofs in iCPL correspond, in the sense of Curry and Howard, to typing derivations for a randomized extension of the λ -calculus, so that counting quantifiers reveal the probability of termination of the underlying probabilistic programs. [ABSTRACT FROM AUTHOR]

• The first TotP-complete problems under parsimonious reductions. • Hardness of approximation for these problems and some of their generalizations. • A family of hard-to-approximate instances for the complete problem Size-of-Subtree. • Exponential time hardness results for Size-of-Subtree under variants of the Exponential Time Hypothesis. • Approximation preserving reduction of the general #SAT to instances of it that are promised to be self-reducible with easy decision. Hard counting problems with easy decision version, like computing the permanent and counting independent sets, are of particular importance in counting complexity theory. TotP is the class of all self-reducible problems in # P with decision version in P. It has been a long standing open question to determine TotP -complete problems under strong reductions that preserve exactly the values of the functions (Karp), since Cook reductions blur structural differences between counting classes, specifically under Cook reductions TotP -complete problems are also # P -complete. In this paper we present the first such problems and we show some implications of these results to counting complexity. The problems that we prove to be TotP -complete under Karp reductions are: (a) #Tree-Monotone-Circuit-SAT , which further implies that it is hard to compute, both exactly and approximately, the number of satisfying assignments of monotone circuits, where the monotonicity is defined by a partial order which is given as part of the input. (b) Max-Lower-Set-Size , which implies that given a poset it is hard to compute and approximate the size of a principal upper set, and the size of the maximum lower set all elements of which share a given property P. (c) Size-of-Subtree , which directly implies that every problem in TotP admits a polynomial-time approximation algorithm the error of which depends on the amount of imbalance of the respective self-reducibility tree of the problem. We settle the worst case complexity of this problem, we provide a family of instances that are hard to approximate, and we show exponential time hardness results under variants of the exponential time hypothesis (ETH). (d) #Clustered-Monotone-SAT , which implies that approximating #SAT remains hard even on instances for which some kind of navigation among solutions is possible. Thus we narrow down any further research regarding the polynomial-time approximability of #SAT to instances with the aforementioned property. Among other implications, our results show that all these problems do not admit an FPRAS, unless NP = RP , something that we would not be able to conclude by showing them to be TotP -complete under Cook reductions.1 [ABSTRACT FROM AUTHOR]

We study the complexity of approximating the partition function of the q-state Potts model and the closely related Tutte polynomial for complex values of the underlying parameters. Apart from the classical connections with quantum computing and phase transitions in statistical physics, recent work in approximate counting has shown that the behaviour in the complex plane, and more precisely the location of zeros, is strongly connected with the complexity of the approximation problem, even for positive real-valued parameters. Previous work in the complex plane by Goldberg and Guo focused on q = 2, which corresponds to the case of the Ising model; for q > 2, the behaviour in the complex plane is not as well understood and most work applies only to the real-valued Tutte plane. Our main result is a complete classification of the complexity of the approximation problems for all non-real values of the parameters, by establishing #P-hardness results that apply even when restricted to planar graphs. Our techniques apply to all q ≥ 2 and further complement/refine previous results both for the Ising model and the Tutte plane, answering in particular a question raised by Bordewich, Freedman, Lovász and Welsh in the context of quantum computations. [ABSTRACT FROM AUTHOR]

We study the problem # I N D S U B (Φ) of counting all induced subgraphs of size k in a graph G that satisfy the property Φ . It is shown that, given any graph property Φ that distinguishes independent sets from bicliques, # I N D S U B (Φ) is hard for the class # W [ 1 ] , i.e., the parameterized counting equivalent of N P . Under additional suitable density conditions on Φ , satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen # W [ 1 ] -hardness by establishing that # I N D S U B (Φ) cannot be solved in time f (k) · n o (k) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime. [ABSTRACT FROM AUTHOR]

Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined on graphs. They arise from the theory of holographic algorithms, which was originally inspired by concepts from quantum computation. Here, we employ quantum information theory to explain existing results about holant problems in a concise way and to derive two new dichotomies: one for a new family of problems, which we call Holant+, and, building on this, a full dichotomy for Holantc. These two families of holant problems assume the availability of certain unary constraint functions - the two pinning functions in the case of Holantc, and four functions in the case of Holant+ - and allow arbitrary sets of algebraic-complex valued constraint functions otherwise. The dichotomy for Holant+ also applies when inputs are restricted to instances defined on planar graphs. In proving these complexity classifications, we derive an original result about entangled quantum states. [ABSTRACT FROM AUTHOR]

We study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H. Faben and Jerrum [Theory Comput., 11 (2015), pp. 35-57] introduced an explicit criterion on the graph H and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class ⊕P of parity problems. We verify their conjecture for all graphs H that exclude the complete graph on four vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the ⊕P-complete cases, assuming the randomized exponential time hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph H. Using this, we subsume all prior progress toward resolving the conjecture (Faben and Jerrum [Theory Comput., 11 (2015), pp. 35-57]; Göbel, Goldberg, and Richerby [ACM Trans. Comput. Theory, 6 (2014), 17; ACM Trans. Comput. Theory, 8 (2016), 12]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2. [ABSTRACT FROM AUTHOR]

We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query q, we consider the following two problems: Given as input an incomplete database D, (a) return the number of completions of D that satisfy q; or (b) return the number of valuations of the nulls of D yielding a completion that satisfies q. We obtain dichotomies between #P-hardness and polynomial-time computability for these problems when q is a self-join–free conjunctive query and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in D (what is called Codd tables); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations: For instance, while the latter is always in #P, we prove that the former is not in #P under some widely believed theoretical complexity assumption. Moreover, we find that both (1) and (2) can reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial-time randomized approximation scheme (FPRAS), in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes. [ABSTRACT FROM AUTHOR]

A retraction is a homomorphism from a graph G to an induced subgraph H of G that is the identity on H. In a long line of research, retractions have been studied under various algorithmic settings. Recently, the problem of approximately counting retractions was considered. We give a complete trichotomy for the complexity of approximately counting retractions to all square-free graphs (graphs that do not contain a cycle of length 4). It turns out there is a rich and interesting class of graphs for which this problem is complete in the class #BIS. As retractions generalise homomorphisms, our easiness results extend to the important problem of approximately counting homomorphisms. By giving new #BIS-easiness results, we now settle the complexity of approximately counting homomorphisms for a whole class of non-trivial graphs that were previously unresolved. [ABSTRACT FROM AUTHOR]

We prove that it is # P -complete to count the triangulations of a (non-simple) polygon. [ABSTRACT FROM AUTHOR]

We investigate the problem # IndSub (Φ) of counting all induced subgraphs of size k in a graph G that satisfy a given property Φ . This continues the work of Jerrum and Meeks who proved the problem to be # W [ 1 ] -hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties Φ , the problem # IndSub (Φ) is hard for # W [ 1 ] if the reduced Euler characteristic of the associated simplicial (graph) complex of Φ is non-zero. This observation links # IndSub (Φ) to Karp's famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the "topological approach to evasiveness" which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that # IndSub (Φ) is # W [ 1 ] -hard for every monotone property Φ that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not k-edge-connected for k > 2 . Moreover, we show that for those properties # IndSub (Φ) can not be solved in time f (k) · n o (k) for any computable function f unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that # IndSub (Φ) is # W [ 1 ] -hard if Φ is any non-trivial modularity constraint on the number of edges with respect to some prime q or if Φ enforces the presence of a fixed isolated subgraph. [ABSTRACT FROM AUTHOR]

We show that counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs is # P -complete under many-one counting ("weakly parsimonious") reductions, and that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) can exist for this integer counting problem unless N P = R P . [ABSTRACT FROM AUTHOR]

We show a computational complexity dichotomy theorem for symmetric complex-weighted Boolean #CSP when the constraint graph of the input must be planar. The problems that are #P-hard over general graphs but tractable over planar graphs are precisely those with a holographic reduction to matchgates. We also obtain a dichotomy theorem for a symmetric arity 4 signature with complex weights in the planar Holant framework, which we use in the proof of our #CSP dichotomy. [ABSTRACT FROM AUTHOR]

We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently viewed as edge-injective homomorphisms from the disjoint union of k length-2 paths into (arbitrary) host graphs. Here, a homomorphism from H to G is edge-injective if it maps any two distinct edges of H to distinct edges in G. We show that edge-injective homomorphisms from a pattern graph H can be counted in polynomial time if H has bounded vertex-cover number after removing isolated edges. For hereditary classes ℋ of pattern graphs, we complement this result: If the graphs in ℋ have unbounded vertex-cover number even after deleting isolated edges, then counting edge-injective homomorphisms with patterns from ℋ is #W[1]-hard. Our proofs rely on an edge-colored variant of Holant problems and a delicate interpolation argument; both may be of independent interest. [ABSTRACT FROM AUTHOR]

A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertices of H, and it is a compaction if it uses all of the vertices of H and all of the nonloop edges of H. Hell and NeŽsetřil gave a complete characterization of the complexity of deciding whether there is a homomorphism from an input graph G to a fixed graph H. A complete characterization is not known for surjective homomorphisms or for compactions, thoug h there are many interesting results. Dyer and Greenhill gave a complete characterization of the complexity of counting homomorphisms from an input graph G to a fixed graph H. In this paper, we give a complete characterization of the complexity of counting surjective homomorphisms from an input graph G to a fixed graph H, and we also give a complete characterization of the complexity of counting compactions from an input graph G to a fixed graph H. In an addendum we use our characterizations to point out a dichotomy for the complexity of the respective approximate counting problems (in the connected case). [ABSTRACT FROM AUTHOR]

Abstract We show that the Clifford gates and stabilizer circuits in the quantum computing literature, which admit efficient classical simulation, are equivalent to affine signatures under a unitary condition. The latter is a known class of tractable functions under the Holant framework. [ABSTRACT FROM AUTHOR]

We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis # ETH introduced by Dell et al. (2014) [18] . Our framework allows us to convert classical # P -hardness results for counting problems into tight lower bounds under # ETH , thus ruling out algorithms with running time 2 o ( n ) on graphs with n vertices and O ( n ) edges. As exemplary applications of this framework, we obtain tight lower bounds under # ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (2016) [24] . [ABSTRACT FROM AUTHOR]

Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Boolean Holant problems with nonnegative algebraic weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric and no auxiliary function is assumed to be available. Let F be a set of nonnegative functions defined on the Boolean domain. We show that the problem Holant(F) is computable in polynomial time if the function set F satisfies one of three conditions: (1) every function in F is a tensor product of functions of arity at most 2; (2) every function in F is affine; (3) F is holographically transformable to a product type by some real orthogonal matrix. Otherwise the problem is #P-hard. [ABSTRACT FROM AUTHOR]

Holographic algorithms introduced by Valiant have two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via basis transformations. In this paper, we replace matchgates in the paradigm above by the affine type and the product type constraint functions, which are known to be tractable in general (not necessarily planar) graphs. We present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. We also give polynomial-time algorithms to the same problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The latter result implies that the symmetric Boolean Holant dichotomy (Cai, Guo, and Williams, SICOMP 2016) is efficiently decidable. Our proof techniques are mainly algebraic. [ABSTRACT FROM AUTHOR]

We analyse the computational efficiency of tissue P systems, a biologically-inspired computing device modelling the communication between cells. In particular, we focus on tissue P systems with fission rules (cell division and/or cell separation), where the number of cells can increase exponentially during the computation. We prove that the complexity class characterised by these devices in polynomial time is exactly P # P , the class of problems solved by polynomial-time Turing machines with oracles for counting problems. [ABSTRACT FROM AUTHOR]

We study the complexity of approximately evaluating the Ising and Tutte partition functions with complex parameters. Our results are partly motivated by the study of the quantum complexity classes BQP and IQP. Recent results show how to encode quantum computations as evaluations of classical partition functions. These results rely on interesting and deep results about quantum computation in order to obtain hardness results about the difficulty in (classically) evaluating the partition functions for certain fixed parameters. The motivation for this paper is to study more comprehensively the complexity of (classically) approximating the Ising and Tutte partition functions with complex parameters. Partition functions are combinatorial in nature, and quantifying their approximation complexity does not require a detailed understanding of quantum computation. Using combinatorial arguments, we give the first full classification of the complexity of multiplicatively approximating the norm and additively approximating the argument of the Ising partition function for complex edge interactions (as well as of approximating the partition function according to a natural complex metric). We also study the norm approximation problem in the presence of external fields, for which we give a complete dichotomy when the parameters are roots of unity. Previous results were known just for a few such points, and we strengthen these results from BQP-hardness to # P-hardness. Moreover, we show that computing the sign of the Tutte polynomial is # P-hard at certain points related to the simulation of BQP. Using our classifications, we then revisit the connections to quantum computation, drawing conclusions that are a little different from (and incomparable to) ones in the quantum literature, but along similar lines. [ABSTRACT FROM AUTHOR]

Lightweight description logics are knowledge representation formalisms characterised by the low complexity of their standard reasoning tasks. They have been successfully employed for constructing large ontologies that model domain knowledge in several different practical applications. In order to maintain these ontologies, it is often necessary to detect the axioms that cause a given consequence. This task is commonly known as axiom pinpointing. In this paper, we provide a thorough analysis of the complexity of several decision, counting, and enumeration problems associated to axiom pinpointing in lightweight description logics. [ABSTRACT FROM AUTHOR]

Holographic algorithms, alternatively known as Pfaffian circuits, have received much attention for giving polynomial-time algorithms to a subset of problems in # P . Much work has been done determining the power of this machinery. One intriguing aspect is that these circuits must be planar. We investigate relaxations of this planarity condition. We show that an approach using orbit closures does not work, but give a different technique that allows one SWAP gate to be used in a Pfaffian circuit given suitable bases and restricted types of graphs. This is done by exploiting the fact that Pfaffian gates lie in a hyperplane. [ABSTRACT FROM AUTHOR]

A monotone arithmetic circuit computes a given multivariate polynomial f if its values on all nonnegative integer inputs are the same as those of f . The circuit counts f if this holds for 0–1 inputs; on other inputs, the circuit may output arbitrary values. The circuit decides f if it has the same 0–1 roots as f . We first show that some multilinear polynomials can be exponentially easier to count than to compute them, and that some polynomials can be exponentially easier to decide than to count them. Our main results are general lower bounds on the size of counting circuits. [ABSTRACT FROM AUTHOR]

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and graph homomorphism can be viewed as subfamilies of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant and Holant problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, a complexity dichotomy for a variety of subfamilies of Holant such as #CSP, graph homomorphism, Holant, and Holant for Boolean domain was proved. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions on Boolean inputs. This setting already captures most of the interesting combinatorial counting problems defined by local constraints, such as (perfect) matching. This is the first time a dichotomy is obtained for general Holant problems without any auxiliary functions. One benefit of working with the Holant framework is some powerful new reduction technique such as the holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail; thus, this new idea of reduction might also be of independent interest. Besides proving a dichotomy and developing a new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP, restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian orientations on 2 k-regular graphs is #P-hard for any $${k \geq 2}$$ . [ABSTRACT FROM AUTHOR]

Parameterised subgraph counting problems are the most thoroughly studied topic in the theory of parameterised counting, and there has been significant recent progress in this area. Many of the existing tractability results for parameterised problems which involve finding or counting subgraphs with particular properties rely on bounding the treewidth of these subgraphs in some sense; here, we prove a number of hardness results for the situation in which this bounded treewidth condition does not hold, resulting in dichotomies for some special cases of the general subgraph counting problem. The paper also gives a thorough survey of known results on this subject and the methods used, as well as discussing the relationships both between multicolour and uncoloured versions of subgraph counting problems, and between exact counting, approximate counting and the corresponding decision problems. [ABSTRACT FROM AUTHOR]

We explore the complexity of counting solutions to conjunctive queries, a basic class of queries from database theory. We introduce a parameter, called the quantified star size of a query ϕ, which measures how the free variables are spread in ϕ. As usual in database theory, we associate a hypergraph to a query ϕ. We show that for classes of queries for which these associated hypergraphs admit good decompositions, e.g., bounded width generalized hypertree decompositions, bounded quantified star size exactly characterizes the subclasses of hypergraphs for which counting the number of solutions is tractable. In the case of bounded arity, this allows us to fully characterize the classes of hypergraphs for which counting the solutions is tractable. Finally, we also analyze the complexity of computing the quantified star size of a conjunctive query. [ABSTRACT FROM AUTHOR]

We give a quantum-inspired O ( n 4 ) algorithm computing the Tutte polynomial of a lattice path matroid, where n is the size of the ground set of the matroid. Furthermore, this can be improved to O ( n 2 ) arithmetic operations if we evaluate the Tutte polynomial on a given input, fixing the values of the variables. The best existing algorithm, found in 2004, was O ( n 5 ) , and the problem has only been known to be polynomial time since 2003. Conceptually, our algorithm embeds the computation in a determinant using a recently demonstrated equivalence of categories useful for counting problems such as those that appear in simulating quantum systems. [ABSTRACT FROM AUTHOR]

In this paper, we address the computational hardness of optimally decoding a quantum stabilizer code. Much like classical linear codes, errors are detected by measuring certain check operators which yield an error syndrome, and the decoding problem consists of determining the most likely recovery given the syndrome. The corresponding classical problem is known to be NP-complete, and are appropriate a similar decoding problem for quantum codes is also known to be NP-complete. However, this decoding strategy is not optimal in the quantum setting as it does not consider error degeneracy, which causes distinct errors to have the same effect on the code. Here, we show that optimal decoding of stabilizer codes (previously known to be NP-hard) is in fact computationally much harder than optimal decoding of classical linear codes, it is #P-complete. [ABSTRACT FROM AUTHOR]

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that A is fixed. In this case, we obtain the following dichotomy: If A / rad A is noncommutative, then computing the determinant over A is hard. “Hard” here means # P -hard over fields of characteristic 0 and Mod p P -hard over fields of characteristic p > 0 . If A / rad A is commutative and the underlying field is perfect, then we can compute the determinant over A in polynomial time. We also consider the case when A is part of the input. Here the hardness is closely related to the nilpotency index of the commutator ideal of A . Our work generalizes and builds upon previous papers by Arvind and Srinivasan (STOC 2010) [1] as well as Chien et al. (STOC 2011) [5] . [ABSTRACT FROM AUTHOR]

We introduce a family of parameterised counting problems on graphs, p -# Induced Subgraph With Property ( Φ ), which generalises a number of problems which have previously been studied. This paper focuses on the case in which Φ defines a family of graphs whose edge-minimal elements all have bounded treewidth; this includes the special case in which Φ describes the property of being connected. We show that exactly counting the number of connected induced k -vertex subgraphs in an n -vertex graph is #W[1]-hard, but on the other hand there exists an FPTRAS for the problem; more generally, we show that there exists an FPTRAS for p -# Induced Subgraph With Property ( Φ ) whenever Φ is monotone and all the minimal graphs satisfying Φ have bounded treewidth. We then apply these results to a counting version of the Graph Motif problem. [ABSTRACT FROM AUTHOR]

Logic-based abduction is an important reasoning method with many applications in Artificial Intelligence including diagnosis, planning, and configuration. The goal of an abduction problem is to find a 'solution', i.e., an explanation for some observed symptoms. Usually, many solutions exist, and one is often interested in minimal ones only. Previous definitions of 'solutions' to an abduction problem tacitly made an open-world assumption. However, as far as minimality is concerned, this assumption may not always lead to the desired behaviour. To overcome this problem, we propose a new definition of solutions based on a closed-world approach. Moreover, we also introduce a new variant of minimality where only a part of the hypotheses is subject to minimization. A thorough complexity analysis reveals the close relationship between these two new notions as well as the differences compared with previous notions of solutions. [ABSTRACT FROM AUTHOR]

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to PPP = P#P, the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between PPP and PSPACE. In particular, for each integer k ≥⃒ 0 we provide a lower bound to the computing power of P systems of depth k. [ABSTRACT FROM AUTHOR]

Generalized counting constraint satisfaction problems include Holant problems with planarity restrictions; polynomial-time algorithms for such problems include matchgates and matchcircuits, which are based on Pfaffians. In particular, they use gates which are expressible in terms of a vector of sub-Pfaffians of a skew-symmetric matrix. We introduce a new type of circuit based instead on determinants, with seemingly different expressive power. In these determinantal circuits , a gate is represented by the vector of all minors of an arbitrary matrix. Determinantal circuits permit a different class of gates. Applications of these circuits include proofs of theorems from algebraic graph theory including the Chung–Langlands formula for the number of rooted spanning forests of a graph and computing Tutte polynomials of certain matroids. They also give a strategy for simulating quantum circuits with closed timelike curves. Monoidal category theory provides a useful language for discussing such counting problems, turning combinatorial restrictions into categorical properties. We introduce the counting problem in monoidal categories and count-preserving functors as a way to study FP subclasses of problems in settings which are generally # P -hard. Using this machinery we show that, surprisingly, determinantal circuits can be simulated by Pfaffian circuits at quadratic cost. [ABSTRACT FROM AUTHOR]

We consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity λ is sufficiently large, there is no fully polynomial randomised approximation scheme for evaluating the partition function unless NP = RP . The result extends to a nearby region of the parameter space in a more general two-state spin system with three parameters. We also give a polynomial-time randomised approximation scheme for the logarithm of the partition function. [ABSTRACT FROM AUTHOR]

We study the complexity of the approximate weighted counting constraint satisfaction problem #CSP ( F ) . In the conservative case, where F contains all unary functions, a classification is known over the Boolean domain; we extend this to arbitrary finite domains. We show that if F is “weakly log-modular”, then #CSP ( F ) is in FP. Otherwise, it is at least as difficult to approximate as #BIS (counting independent sets in bipartite graphs). #BIS is complete for the complexity class # R H Π 1 , and believed to be intractable. We further sub-divide the #BIS-hard case: if F is “weakly log-supermodular”, #CSP ( F ) is as easy as a Boolean log-supermodular weighted #CSP; otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case: #CSP ( F ) is in FP, is #BIS-equivalent, or is equivalent to #SAT (approximately counting the satisfying assignments of Boolean CNF formulas). We also discuss algorithmic aspects of our classification. [ABSTRACT FROM AUTHOR]

Abstract: This paper is a study of weighted counting of the solutions of acyclic conjunctive queries (ACQ). The unweighted quantifier free version of this problem is known to be tractable (for combined complexity), but it is also known that introducing even a single quantified variable makes it -hard. We first show that weighted counting for quantifier free ACQ is still tractable and that even minimalistic extensions of the problem lead to hard cases. We then introduce a new parameter for quantified queries that permits to isolate a large island of tractability. We show that, up to a standard assumption from parameterized complexity, this parameter fully characterizes tractable subclasses for counting weighted solutions for ACQs. Thus we completely determine the tractability frontier for weighted counting for ACQ. [Copyright &y& Elsevier]

Abstract: Conjunctive queries (CQs) are one of the most fundamental forms of database queries. In general, the evaluation of CQs is -complete. Consequently, there has been an intensive search for tractable fragments. In this paper, we want to initiate a systematic search for tractable fragments of the counting problem of CQs, i.e., the problem of counting the answers to a CQ. We prove several new tractability and intractability results by starting with acyclic conjunctive queries and generalising these results to CQs of bounded hypertree-width. We also extend our study to the counting problem of unions of CQs. [Copyright &y& Elsevier]

Abstract: We prove a complexity dichotomy theorem for a class of partition functions over -regular graphs, for any fixed . These problems can be viewed as graph homomorphisms from an arbitrary -regular input graph to the weighted two vertex graph on defined by a real-valued symmetric function . We completely classify the computational complexity of this problem. We show that there are exactly the following alternatives, for any given . Depending on , over -regular graphs, either [1.] the problem is even for planar graphs, [2.] the problem is for general (non-planar) graphs, but solvable in polynomial time for planar graphs, or [3.] the problem is solvable in polynomial time for general graphs. The dependence on is an explicit criterion. Furthermore, we show that in case (2) the problem is solvable in polynomial time over -regular planar graphs, by exactly the theory of holographic algorithms using matchgates. [Copyright &y& Elsevier]

Each symmetric matrix A over C defines a graph homomorphism function ZA(·) on undirected graphs. The function ZA(·) is also called the partition function from statistical physics, and can encode many interesting graph properties, including counting vertex covers and k-colorings. We study the computational complexity of ZA(·) for arbitrary symmetric matrices A with algebraic complex values. Building on work by Dyer and Greenhill [Random Structures and Algorithms, 17 (2000), pp. 260-289], Bulatov and Grohe [Theoretical Computer Science, 348 (2005), pp. 148-186], and especially the recent beautiful work by Goldberg et al. [SIAM J. Comput., 39 (2010), pp. 3336-3402], we prove a complete dichotomy theorem for this problem. We show that ZA(·) is either computable in polynomial-time or #P-hard, depending explicitly on the matrix A. We further prove that the tractability criterion on A is polynomial-time decidable. [ABSTRACT FROM AUTHOR]

We introduce the method of proving complexity dichotomy theorems by holographic reductions. Combined with interpolation, we present a unified strategy to prove #P-hardness. Specifically, we prove a complexity dichotomy theorem for a class of counting problems on 2-3 regular graphs expressible by Boolean signatures. For these problems, whenever a holographic reduction followed by interpolation fails to prove #P-hardness, we can show that the problem is solvable in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract: Let be an integer and let be a complex-valued symmetric function on domain (i.e., where ). We introduce a new technique, called a syzygy, and prove a dichotomy theorem for the following class of problems, specified by and : given an arbitrary -regular graph , where the function is attached to each edge, compute . is known as the partition function of the spin system, also known as counting graph homomorphisms on domain size two, and is a special case of Holant problems. The dichotomy theorem gives a complete classification of the computational complexity of this problem, depending on and . The dependence on and is explicit. [Copyright &y& Elsevier]

The cover polynomial and its geometric version introduced by Chung & Graham and D'Antona & Munarini, respectively, are two-variate graph polynomials for directed graphs. They count the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, can be thought of as interpolations between determinant and permanent, and are proposed as directed analogues of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is # P-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomials: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial and its geometric version is # P-hard under polynomial time Turing reductions, while only three points in the cover polynomial and two points in the geometric cover polynomial are easy. We also study the complexity of approximately evaluating the geometric cover polynomial. Under the reasonable complexity assumptions RP ≠ NP and RFP ≠ # P, we give a succinct characterization of a large class of points at which approximating the geometric cover polynomial within any polynomial factor is not possible. [ABSTRACT FROM AUTHOR]

Abstract: Abduction is an important method of non-monotonic reasoning with many applications in artificial intelligence and related topics. In this paper, we concentrate on propositional abduction, where the background knowledge is given by a propositional formula. Decision problems of great interest are the existence and the relevance problems. The complexity of these decision problems has been systematically studied while the counting complexity of propositional abduction has remained obscure. The goal of this work is to provide a comprehensive analysis of the counting complexity of propositional abduction in various settings. [Copyright &y& Elsevier]

Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colorings or the number of independent sets of a graph and also the partition functions of certain "spin glass" models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [Random Structures Algorithms, 17 (2000), pp. 260-289] and Bulatov and Grohe [Theoret. Comput. Sci., 348 (2005), pp. 148-186], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by Hadamard matrices (these turn out to be central in our proofs) we obtain a simple algebraic tractability criterion, which says that the tractable cases are those "representable" by a quadratic polynomial over the field F2. [ABSTRACT FROM AUTHOR]