Search

Arguing for the need to combine declarative and probabilistic programming, Bárány et al. (TODS 2017) recently introduced a probabilistic extension of Datalog as a “purely declarative probabilistic programming language.” We revisit this language and propose a more principled approach towards defining its semantics based on stochastic kernels and Markov processes—standard notions from probability theory. This allows us to extend the semantics to continuous probability distributions, thereby settling an open problem posed by Bárány et al. We show that our semantics is fairly robust, allowing both parallel execution and arbitrary chase orders when evaluating a program.We cast our semantics in the framework of infinite probabilistic databases (Grohe and Lindner, LMCS 2022) and show that the semantics remains meaningful even when the input of a probabilistic Datalog program is an arbitrary probabilistic database. [ABSTRACT FROM AUTHOR]

Probabilistic databases (PDBs) model uncertainty in data. The current standard is to view PDBs as finite probability spaces over relational database instances. Since many attributes in typical databases have infinite domains, such as integers, strings, or real numbers, it is often more natural to viewPDBs as infinite probability spaces over database instances. In this article, we lay the mathematical foundations of infinite probabilistic databases. Our focus then is on independence assumptions. Tuple-independent PDBs play a central role in theory and practice of PDBs. Here we study infinite tuple-independent PDBs as well as related models such as infinite block-independent disjoint PDBs. While the standardmodel of PDBs focuses on a set-based semantics, we also study tuple-independent PDBs with a bag semantics and independence in PDBs over uncountable fact spaces. We also propose a new approach to PDBs with an open-world assumption, addressing issues raised by Ceylan et al. (Proc. KR 2016) and generalizing their work, which is still rooted in finite tuple-independent PDBs. Moreover, for countable PDBs we propose an approximate query answering algorithm. [ABSTRACT FROM AUTHOR]

In a recent breakthrough, Babai [Proceedings of STOC, ACM, New York, 2016, pp. 684--697] gave a quasipolynomial-time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithm runs in time nO ((log d)c), where n is the number of vertices of the input graphs, d is the maximum degree of the input graphs, and c is an absolute constant. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor, and Luks [Proceedings of FOCS, IEEE, New York, 1983, pp. 162-171] runs in time nO (log d). [ABSTRACT FROM AUTHOR]

Fuels with high‐knock resistance enable modern spark‐ignition engines to achieve high efficiency and thus low CO2 emissions. Identification of molecules with desired autoignition properties indicated by a high research octane number and a high octane sensitivity is therefore of great practical relevance and can be supported by computer‐aided molecular design (CAMD). Recent developments in the field of graph machine learning (graph‐ML) provide novel, promising tools for CAMD. We propose a modular graph‐ML CAMD framework that integrates generative graph‐ML models with graph neural networks and optimization, enabling the design of molecules with desired ignition properties in a continuous molecular space. In particular, we explore the potential of Bayesian optimization and genetic algorithms in combination with generative graph‐ML models. The graph‐ML CAMD framework successfully identifies well‐established high‐octane components. It also suggests new candidates, one of which we experimentally investigate and use to illustrate the need for further autoignition training data. [ABSTRACT FROM AUTHOR]

We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3k + 4) is a complete isomorphism test for the class of all graphs of rank width at most k. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width k is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time nf(k) for a non- elementary function f. Our result yields an isomorphism test for graphs of rank width k running in time nO(k). Another consequence of our result is the first polynomial-time canonisation algorithm for graphs of bounded rank width. Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width. [ABSTRACT FROM AUTHOR]

Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [2010, 2011], form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes (parameterized by the length of the input formula). At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighborhood covers for nowhere dense graphs. This extends and improves previous constructions of neighborhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterization of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a "rankpreserving" version of Gaifman's locality theorem. [ABSTRACT FROM AUTHOR]

We prove that for every positive integer k, there exists an mso1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of cmso1-definability and recognizability on graphs of bounded linear cliquewidth. [ABSTRACT FROM AUTHOR]

We give a new FPT algorithm testing isomorphism of n-vertex graphs of tree-width k in time 2k polylog(k)n3, improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2 O(k5 log k)n5. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree-width k. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai's algorithm as a black box in one place. We also give a second algorithm that, at the price of a slightly worse running time 2 O(k2 log k)n3, avoids the use of Babai's algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm. [ABSTRACT FROM AUTHOR]

We give a logical characterization of the polynomial-time properties of graphs embeddable in some surface. For every surface S, a property P of graphs embeddable in S is decidable in polynomial time if and only if it is definable in fixed-point logic with counting. It is a consequence of this result that for every surface S there is a k such that a simple combinatorial algorithm, namely "the k-dimensionalWeisfeiler-Lehman algorithm", decides isomorphism of graphs embeddable in S in polynomial time. We also present (without proof) generalizations of these results to arbitrary classes of graphs with excluded minors. [ABSTRACT FROM AUTHOR]

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let HOM(C,--) be the problem of deciding whether a given structure A ∈ C has a homomorphism to a given (arbitrary) structure B. We prove that, under some complexity theoretic assumption from parameterized complexity theory, HOM(C,--) is in polynomial time if and only if C has bounded tree width modulo homomorphic equivalence. Translated into the language of constraint satisfaction problems, our result yields a characterization of the tractable structural restrictions of constraint satisfaction problems. Translated into the language of database theory, it implies a characterization of the tractable instances of the evaluation problem for conjunctive queries over relational databases. [ABSTRACT FROM AUTHOR]

The W*-hierarchy, a variant of the better known W-hierarchy is characterized. It is proved that W[t] C W*[t] C W[2t-2] for each t > 2 and an improvement on earlier characterization of the hierarchy in terms of model-checking problems was obtained.

In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown that nowhere dense classes of graphs admit sparse neighborhood covers of small degree. We show that a monotone graph class admits sparse neighborhood covers if and only if it is nowhere dense. The existence of such covers for nowhere dense classes is established through bounds on so-called weak coloring numbers. The core results of this paper are various lower and upper bounds on the weak coloring numbers and other, closely related, generalized coloring numbers. We prove tight bounds for these numbers on graphs of bounded treewidth. We clarify and tighten the relation between the density of shallow minors and the various generalized coloring numbers. These upper bounds are complemented by new, stronger exponential lower bounds on the weak and strong coloring numbers, and by superpolynomial lower bounds on the weak coloring numbers on classes of polynomial expansion. Finally, we show that computing weak r-coloring numbers is NP-complete for all r ≥ 3 [ABSTRACT FROM AUTHOR]

The dichotomy conjecture for the parameterized embedding problem states that the problem of deciding whether a given graph G from some class ]> ]> K ]> of ˵pattern graphs″ can be embedded into a given graph H (that is, is isomorphic to a subgraph of H) is fixed-parameter tractable if ]> ]> K ]> is a class of graphs of bounded tree width and ]> ]> W [ 1 ] ]> -complete otherwise. Towards this conjecture, we prove that the embedding problem is ]> ]> W [ 1 ] ]> -complete if ]> ]> K ]> is the class of all grids or the class of all walls. [ABSTRACT FROM AUTHOR]

Tangles of graphs have been introduced by Robertson and Seymour in the context of their graph minor theory. Tangles may be viewed as describing "k-connected components" of a graph (though in a twisted way). An interesting aspect of tangles is that they can be defined not only for graphs, but more generally for arbitrary connectivity functions (that is, integer-valued submodular and symmetric set functions). However, tangles are difficult to deal with algorithmically. To start with, it is unclear how to represent them, because they are families of separations and, as such, may be exponentially large. Our first contribution is a data structure for representing and accessing all tangles of a graph up to some fixed order. Using this data structure, we can prove an algorithmic version of a very general structure theorem due to Carmesin et al. (for graphs) and Hundertmark (for arbitrary connectivity functions) that yields a canonical tree decomposition whose parts correspond to the maximal tangles. This may be viewed as a generalization of the decomposition of a graph into its 3-connected components. [ABSTRACT FROM AUTHOR]

We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for all classes C of graphs that are closed under taking subgraphs, FO and MSO have the same expressive power on C if and only if, C has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking induced subgraphs, we show an analogous result for guarded second-order logic (GSO), the variant of MSO that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman-Vaught-type theorem that works for infinite collections of structures despite being constructive. [ABSTRACT FROM AUTHOR]

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph H as a minor to graphs excluding H as a topological subgraph. We prove that for a fixed H, every graph excluding H as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter |H|. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a "typical" application of the structure theorem, we show that on graphs excluding H as a topological subgraph, Partial Dominating Set (find k vertices whose closed neighborhood has maximum size) can be solved in time f(H,k)· nO(1). More significantly, we show that on graphs excluding H as a topological subgraph, Graph Isomorphism can be solved in time nf(H). This result unifies and generalizes two previously known important polynomial time solvable cases of Graph Isomorphism: boundeddegree graphs [E. M. Luks, J. Comput. System Sci., 25 (1982), pp. 42-65] and H-minor free graphs [I. N. Ponomarenko, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 174 (1988), pp. 147-177, 182]. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition. [ABSTRACT FROM AUTHOR]

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimizers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterized by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections. On the other hand, we show that in the average-case model, every join-project plan can be turned into a plan containing no projections in such a way that the expected time to evaluate the plan increases only by a constant factor independent of the size of the database. Not surprisingly, the key combinatorial parameter in this context is the maximum density of the underlying hypergraph. We show how to make effective use of this parameter to eliminate the projections. Abstract. Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimizers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterized by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections. On the other hand, we show that in the average-case model, every join-project plan can be turned into a plan containing no projections in such a way that the expected time to evaluate the plan increases only by a constant factor independent of the size of the database. Not surprisingly, the key combinatorial parameter in this context is the maximum density of the underlying hypergraph. We show how to make effective use of this parameter to eliminate the projections. [ABSTRACT FROM AUTHOR]

Abstract: The general intractability of the constraint satisfaction problem (CSP) has motivated the study of the complexity of restricted cases of this problem. Thus far, the literature has primarily considered the formulation of the CSP where constraint relations are given explicitly. We initiate the systematic study of CSP complexity with succinctly specified constraint relations. [ABSTRACT FROM AUTHOR]

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]

A class of relational structures is said to have the extension preservation property if every first-order sentence that is preserved under extensions on the class is equivalent to an existential sentence. The class of all finite structures does not have the extension preservation property. We study the property on classes of finite structures that are better behaved. We show that the property holds for classes of acyclic structures, structures of bounded degree, and more generally structures that are wide in a sense that we will make precise. We also show that the preservation property holds for the class of structures of treewidth at most k, for any k. In contrast, we show that the property fails for the class of planar graphs. [ABSTRACT FROM AUTHOR]

Abstract: Motivated by recent results showing that there are natural parameterized problems that are fixed-parameter tractable, but can only be solved by fixed-parameter tractable algorithms the running time of which depends nonelementarily on the parameter, we propose a notion of bounded fixed-parameter tractability, where the dependence of the running time on the parameter is restricted to be singly exponential. We develop a basic theory that is centred around the class EPT of tractable problems and an EW-hierarchy of classes of intractable problems, both in the bounded sense. By and large, this theory is similar to the established unbounded parameterized complexity theory, but there are some remarkable differences. Most notably, certain natural model-checking problems that are known to be fixed-parameter tractable in the unbounded sense have a very high complexity in the bounded theory. The problem of computing the VC-dimension of a family of sets, which is known to be complete for the class in the unbounded theory, is complete for the class in the bounded theory. It turns out that our bounded parameterized complexity theory is closely related to the classical complexity theory of problems that can be solved by a nondeterministic polynomial time algorithm that only uses nondeterministic bits, and in particular to the classes LOGSNP and LOGNP introduced by Papadimitriou and Yannakakis. [Copyright &y& Elsevier]

We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t ≥ 1, that corresponds to Downey and Fellows's W-hierarchy [R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999] and we show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, is #W[1]-complete. This makes it highly unlikely that these problems are fixed-parameter tractable, even though their decision versions are fixed-parameter tractable. More explicitly, our result shows that most likely there is no f(k) · nc-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f : N → N and constant c, even though there is a 2O(k) · n2.376 algorithm for finding a cycle or path of length k. [N. Alon, R. Yuster, and U. Zwick, J. ACM, 42 (1995), pp. 844-856]. [ABSTRACT FROM AUTHOR]