BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Manuel Bodirsky

Manuel Bodirsky appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.LOComputational ComplexityLogic in Computer Sciencemath.COmath.RAArtificial IntelligenceDiscrete MathematicsComputational Engineering, Finance, and ScienceDatabasesmath.DSmath.GRmath.OC

Catalog footprint

What is connected

40works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

40 published item(s)

preprint2026arXiv

The Complexity of Resilience for Digraph Queries

We prove a complexity dichotomy for the resilience problem for unions of conjunctive digraph queries (i.e., for existential positive sentences over the signature $\{R\}$ of directed graphs). Specifically, for every union $μ$ of conjunctive digraph queries, the following problem is in P or NP-complete: given a directed multigraph $G$ and a natural number $u$, can we remove $u$ edges from $G$ so that $G \models \neg μ$? In fact, we verify a more general dichotomy conjecture from (Bodirsky et al., 2024) for all resilience problems in the special case of directed graphs, and show that for such unions of queries $μ$ there exists a countably infinite ('dual') valued structure $Δ_μ$ which either primitively positively constructs 1-in-3-3-SAT, and hence the resilience problem for $μ$ is NP-complete by general principles, or has a pseudo cyclic canonical fractional polymorphism, and the resilience problem for $μ$ is in P.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

Robin Hirsch posed in 1996 the 'Really Big Complexity Problem': classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We provide a complete classification for the case that A is symmetric and has a flexible atom; in this case, the problem is NP-complete or in P. The classification task can be reduced to the case where A is integral. If a finite integral relation algebra has a flexible atom, then it has a normal representation B. We can then study the computational complexity of the network satisfaction problem of A using the universal-algebraic approach, via an analysis of the polymorphisms of B. We also use a Ramsey-type result of Nešetřil and Rödl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Descriptive Complexity of Temporal Constraint Satisfaction Problems

Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes coincides with an important dichotomy in universal algebra; in particular, the border can be described by a strong height-one Maltsev condition. For infinite-domain CSPs, the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q;<); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the Boolean rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Constraint satisfaction problems for reducts of homogeneous graphs

For $n\geq 3$, let $(H_n, E)$ denote the $n$-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on $n$ vertices. We show that for all structures $Γ$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $Γ$ is either in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

ω-categorical structures avoiding height 1 identities

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of non-trivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of non-trivial height 1 identities differ for $ω$-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

ASNP: a tame fragment of existential second-order logic

Amalgamation SNP (ASNP) is a fragment of existential second-order logic that strictly contains binary connected MMSNP of Feder and Vardi and binary guarded monotone SNP of Bienvenu, ten Cate, Lutz, and Wolter; it is a promising candidate for an expressive subclass of NP that exhibits a complexity dichotomy. We show that ASNP has a complexity dichotomy if and only if the infinite-domain dichotomy conjecture holds for constraint satisfaction problems for first-order reducts of binary finitely bounded homogeneous structures. For such CSPs, powerful universal-algebraic hardness conditions are known that are conjectured to describe the border between NP-hard and polynomial-time tractable CSPs. The connection to CSPs also implies that every ASNP sentence can be evaluated in polynomial time on classes of finite structures of bounded treewidth. We show that the syntax of ASNP is decidable. The proof relies on the fact that for classes of finite binary structures given by finitely many forbidden substructures, the amalgamation property is decidable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Canonical Functions: a proof via topological dynamics

Canonical functions are a powerful concept with numerous applications in the study of groups, monoids, and clones on countable structures with Ramsey-type properties. In this short note, we present a proof of the existence of canonical functions in certain sets using topological dynamics, providing a shorter alternative to the original combinatorial argument. We moreover present equivalent algebraic characterisations of canonicity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Hardness of Network Satisfaction for Relation Algebras with Normal Representations

We study the computational complexity of the general network satisfaction problem for a finite relation algebra $A$ with a normal representation $B$. If $B$ contains a non-trivial equivalence relation with a finite number of equivalence classes, then the network satisfaction problem for $A$ is NP-hard. As a second result, we prove hardness if $B$ has domain size at least three and contains no non-trivial equivalence relations but a symmetric atom $a$ with a forbidden triple $(a,a,a)$, that is, $a \not\leq a \circ a$. We illustrate how to apply our conditions on two small relation algebras.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables

Many combinatorial optimisation problems can be modelled as valued constraint satisfaction problems. In this paper, we present a polynomial-time algorithm solving the valued constraint satisfaction problem for a fixed number of variables and for piecewise linear cost functions. Our algorithm finds the infimum of a piecewise linear function and decides whether it is a proper minimum.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Structures with Small Orbit Growth

Let $K_{exp+}$ be the class of all structures $A$ such that the automorphism group of $A$ has at most $c n^{d n}$ orbits in its componentwise action on the set of $n$-tuples with pairwise distinct entries, for some constants $c,d$ with $d < 1$. We show that $K_{exp+}$ is precisely the class of finite covers of first-order reducts of unary structures, and also that $K_{exp+}$ is precisely the class of first-order reducts of finite covers of unary structures. It follows that the class of first-order reducts of finite covers of unary structures is closed under taking model companions and model-complete cores, which is an important property when studying the constraint satisfaction problem for structures from $K_{exp+}$. We also show that Thomas' conjecture holds for $K_{exp+}$: all structures in $K_{exp+}$ have finitely many first-order reducts up to first-order interdefinability.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Two-element structures modulo primitive positive constructability

Primitive positive constructions have been introduced in recent work of Barto, Opršal, and Pinsker to study the computational complexity of constraint satisfaction problems. Let $\mathfrak P_{\operatorname{fin}}$ be the poset which arises from ordering all finite relational structures by pp-constructability. This poset is infinite, but we do not know whether it is uncountable. In this paper, we give a complete description of the restriction $\mathfrak P_{\operatorname{Boole}}$ of $\mathfrak P_{\operatorname{fin}}$ to relational structures on a two-element set; in particular, we prove that $\mathfrak P_{\operatorname{Boole}}$ is a lattice. Finally, we use $\mathfrak P_{\operatorname{Boole}}$ to present the various complexity regimes of Boolean constraint satisfaction problems that were described by Allender, Bauland, Immerman, Schnoor and Vollmer.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation

Valued constraint satisfaction problems (VCSPs) are a large class of combinatorial optimisation problems. The computational complexity of VCSPs depends on the set of allowed cost functions in the input. Recently, the computational complexity of all VCSPs for finite sets of cost functions over finite domains has been classified. Many natural optimisation problems, however, cannot be formulated as VCSPs over a finite domain. We initiate the systematic investigation of infinite-domain VCSPs by studying the complexity of VCSPs for piecewise linear homogeneous cost functions. Such VCSPs can be solved in polynomial time if the cost functions are improved by fully symmetric fractional operations of all arities. We show this by reducing the problem to a finite-domain VCSP which can be solved using the basic linear program relaxation. It follows that VCSPs for submodular PLH cost functions can be solved in polynomial time; in fact, we show that submodular PLH functions form a maximally tractable class of PLH cost functions.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)

The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable when the model-complete core of the template has a pseudo-Siggers polymorphism, and NP-complete otherwise. One of the important questions related to this conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each non-trivial set of height 1 identities a structure whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of non-trivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of non-trivial height 1 identities differ for $ω$-categorical structures with less than double exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A counterexample to the reconstruction of $ω$-categorical structures from their endomorphism monoids

We present an example of two countable $ω$-categorical structures, one of which has a finite relational language, whose endomorphism monoids are isomorphic as abstract monoids, but not as topological monoids -- in other words, no isomorphism between these monoids is a homeomorphism. For the same two structures, the automorphism groups and polymorphism clones are isomorphic, but not topologically isomorphic. In particular, there exists a countable $ω$-categorical structure in a finite relational language which can neither be reconstructed up to first-order bi-interpretations from its automorphism group, nor up to existential positive bi-interpretations from its endomorphism monoid, nor up to primitive positive bi-interpretations from its polymorphism clone.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distance Constraint Satisfaction Problems

We study the complexity of constraint satisfaction problems for templates $Γ$ that are first-order definable in $(\Bbb Z; succ)$, the integers with the successor relation. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), we provide a full classification for the case that Gamma is locally finite (i.e., the Gaifman graph of $Γ$ has finite degree). We show that one of the following is true: The structure Gamma is homomorphically equivalent to a structure with a d-modular maximum or minimum polymorphism and $\mathrm{CSP}(Γ)$ can be solved in polynomial time, or $Γ$ is homomorphically equivalent to a finite transitive structure, or $\mathrm{CSP}(Γ)$ is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Reconstructing the topology of clones

Function clones are sets of functions on a fixed domain that are closed under composition and contain the projections. They carry a natural algebraic structure, provided by the laws of composition which hold in them, as well as a natural topological structure, provided by the topology of pointwise convergence, under which composition of functions becomes continuous. Inspired by recent results indicating the importance of the topological ego of function clones even for originally algebraic problems, we study questions of the following type: In which situations does the algebraic structure of a function clone determine its topological structure? We pay particular attention to function clones which contain an oligomorphic permutation group, and discuss applications of this situation in model theory and theoretical computer science.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Reducts of the Homogeneous Binary Branching C-relation

Let (L;C) be the (up to isomorphism unique) countable homogeneous structure carrying a binary branching C-relation. We study the reducts of (L;C), i.e., the structures with domain L that are first-order definable in (L;C). We show that up to existential interdefinability, there are finitely many such reducts. This implies that there are finitely many reducts up to first-order interdefinability, thus confirming a conjecture of Simon Thomas for the special case of (L;C). We also study the endomorphism monoids of such reducts and show that they fall into four categories.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The universal homogeneous binary tree

A partial order is called semilinear iff the upper bounds of each element are linearly ordered and any two elements have a common upper bound. There exists, up to isomorphism, a unique countable existentially closed semilinear order, which we denote by S2. We study the reducts of S2, that is, the relational structures with the same domain as S2 all of whose relations are first-order definable in S2. Our main result is a classification of the model-complete cores of the reducts of S2. From this, we also obtain a classification of reducts up to first-order interdefinability, which is equivalent to a classification of all closed permutation groups that contain the automorphism group of S2.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Ramsey Classes: Examples and Constructions

This article is concerned with classes of relational structures that are closed under taking substructures and isomorphism, that have the joint embedding property, and that furthermore have the Ramsey property, a strong combinatorial property which resembles the statement of Ramsey's classic theorem. Such classes of structures have been called Ramsey classes. Nesetril and Roedl showed that they have the amalgamation property, and therefore each such class has a homogeneous Fraisse-limit. Ramsey classes have recently attracted attention due to a surprising link with the notion of extreme amenability from topological dynamics. Other applications of Ramsey classes include reduct classification of homogeneous structures. We give a survey of the various fundamental Ramsey classes and their (often tricky) combinatorial proofs, and about various methods to derive new Ramsey classes from known Ramsey classes. Finally, we state open problems related to a potential classification of Ramsey classes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Schaefer's theorem for graphs

Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems: it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in polynomial time, or is NP-complete. We present an analog of this dichotomy result for the propositional logic of graphs instead of Boolean logic. In this generalization of Schaefer's result, the input consists of a set W of variables and a conjunction Φ of statements ("constraints") about these variables in the language of graphs, where each statement is taken from a fixed finite set Ψ of allowed quantifier-free first-order formulas; the question is whether Φ is satisfiable in a graph. We prove that either Ψ is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. This is achieved by a universal-algebraic approach, which in turn allows us to use structural Ramsey theory. To apply the universal-algebraic approach, we formulate the computational problems under consideration as constraint satisfaction problems (CSPs) whose templates are first-order definable in the countably infinite random graph. Our method to classify the computational complexity of those CSPs is based on a Ramsey-theoretic analysis of functions acting on the random graph, and we develop general tools suitable for such an analysis which are of independent mathematical interest.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

The universal-algebraic approach has proved a powerful tool in the study of the complexity of CSPs. This approach has previously been applied to the study of CSPs with finite or (infinite) omega-categorical templates, and relies on two facts. The first is that in finite or omega-categorical structures A, a relation is primitive positive definable if and only if it is preserved by the polymorphisms of A. The second is that every finite or omega-categorical structure is homomorphically equivalent to a core structure. In this paper, we present generalizations of these facts to infinite structures that are not necessarily omega-categorical. (This abstract has been severely curtailed by the space constraints of arXiv -- please read the full abstract in the article.) Finally, we present applications of our general results to the description and analysis of the complexity of CSPs. In particular, we give general hardness criteria based on the absence of polymorphisms that depend on more than one argument, and we present a polymorphism-based description of those CSPs that are first-order definable (and therefore can be solved in polynomial time).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Datalog and Constraint Satisfaction with Infinite Templates

On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this connection for infinite structures. This has applications for constraint satisfaction with infinite templates. If the template Gamma is omega-categorical, we present various equivalent characterizations of those Gamma such that the constraint satisfaction problem (CSP) for Gamma can be solved by a Datalog program. We also show that CSP(Gamma) can be solved in polynomial time for arbitrary omega-categorical structures Gamma if the input is restricted to instances of bounded treewidth. Finally, we characterize those omega-categorical templates whose CSP has Datalog width 1, and those whose CSP has strict Datalog width k.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Decidability of definability

For a fixed countably infinite structure Γ with finite relational signature τ, we study the following computational problem: input are quantifier-free τ-formulas ϕ_0,ϕ_1,...,ϕ_n that define relations R_0,R_1,...,R_n over Γ. The question is whether the relation R_0 is primitive positive definable from R_1,...,R_n, i.e., definable by a first-order formula that uses only relation symbols for R_1,..., R_n, equality, conjunctions, and existential quantification (disjunction, negation, and universal quantification are forbidden). We show decidability of this problem for all structures Γ that have a first-order definition in an ordered homogeneous structure Δ with a finite relational signature whose age is a Ramsey class and determined by finitely many forbidden substructures. Examples of structures Γ with this property are the order of the rationals, the random graph, the homogeneous universal poset, the random tournament, all homogeneous universal C-relations, and many more. We also obtain decidability of the problem when we replace primitive positive definability by existential positive, or existential definability. Our proof makes use of universal algebraic and model theoretic concepts, Ramsey theory, and a recent characterization of Ramsey classes in topological dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Essential Convexity and Complexity of Semi-Algebraic Constraints

Let Γbe a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for Γ: the problem to decide whether a given primitive positive sentence is true in Γ. We focus on those structures Γthat contain the relations \leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a,b\inS, there are only finitely many points on the line segment between a and b that are not in S. If Γcontains a relation S that is not essentially convex and this is witnessed by rational points a,b, then we show that the CSP for Γis NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if Γis a first-order expansion of (R;*,+), then the CSP for Γcan be solved in polynomial time if and only if all relations in Γare essentially convex (unless P=NP).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Minimal functions on the random graph

We show that there is a system of 14 non-trivial finitary functions on the random graph with the following properties: Any non-trivial function on the random graph generates one of the functions of this system by means of composition with automorphisms and by topological closure, and the system is minimal in the sense that no subset of the system has the same property. The theorem is obtained by proving a Ramsey-type theorem for colorings of tuples in finite powers of the random graph, and by applying this to find regular patterns in the behavior of any function on the random graph. As model-theoretic corollaries of our methods we re-derive a theorem of Simon Thomas classifying the first-order closed reducts of the random graph, and prove some refinements of this theorem; also, we obtain a classification of the minimal reducts closed under primitive positive definitions, and prove that all reducts of the random graph are model-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

New Ramsey Classes from Old

Let C_1 and C_2 be strong amalgamation classes of finite structures, with disjoint finite signatures sigma and tau. Then C_1 wedge C_2 denotes the class of all finite (sigma cup tau)-structures whose sigma-reduct is from C_1 and whose tau-reduct is from C_2. We prove that when C_1 and C_2 are Ramsey, then C_1 wedge C_2 is also Ramsey. We also discuss variations of this statement, and give several examples of new Ramsey classes derived from those general results.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Peek Arc Consistency

This paper studies peek arc consistency, a reasoning technique that extends the well-known arc consistency technique for constraint satisfaction. In contrast to other more costly extensions of arc consistency that have been studied in the literature, peek arc consistency requires only linear space and quadratic time and can be parallelized in a straightforward way such that it runs in linear time with a linear number of processors. We demonstrate that for various constraint languages, peek arc consistency gives a polynomial-time decision procedure for the constraint satisfaction problem. We also present an algebraic characterization of those constraint languages that can be solved by peek arc consistency, and study the robustness of the algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Topological Birkhoff

One of the most fundamental mathematical contributions of Garrett Birkhoff is the HSP theorem, which implies that a finite algebra B satisfies all equations that hold in a finite algebra A of the same signature if and only if B is a homomorphic image of a subalgebra of a finite power of A. On the other hand, if A is infinite, then in general one needs to take an infinite power in order to obtain a representation of B in terms of A, even if B is finite. We show that by considering the natural topology on the functions of A and B in addition to the equations that hold between them, one can do with finite powers even for many interesting infinite algebras A. More precisely, we prove that if A and B are at most countable algebras which are oligomorphic, then the mapping which sends each function from A to the corresponding function in B preserves equations and is continuous if and only if B is a homomorphic image of a subalgebra of a finite power of A. Our result has the following consequences in model theory and in theoretical computer science: two ω-categorical structures are primitive positive bi-interpretable if and only if their topological polymorphism clones are isomorphic. In particular, the complexity of the constraint satisfaction problem of an ω-categorical structure only depends on its topological polymorphism clone.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tractable Set Constraints

Many fundamental problems in artificial intelligence, knowledge representation, and verification involve reasoning about sets and relations between sets and can be modeled as set constraint satisfaction problems (set CSPs). Such problems are frequently intractable, but there are several important set CSPs that are known to be polynomial-time tractable. We introduce a large class of set CSPs that can be solved in quadratic time. Our class, which we call EI, contains all previously known tractable set CSPs, but also some new ones that are of crucial importance for example in description logics. The class of EI set constraints has an elegant universal-algebraic characterization, which we use to show that every set constraint language that properly contains all EI set constraints already has a finite sublanguage with an NP-hard constraint satisfaction problem.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Boltzmann Samplers, Pólya Theory, and Cycle Pointing

We introduce a general method to count unlabeled combinatorial structures and to efficiently generate them at random. The approach is based on pointing unlabeled structures in an "unbiased" way that a structure of size n gives rise to n pointed structures. We extend Polya theory to the corresponding pointing operator, and present a random sampling framework based on both the principles of Boltzmann sampling and on Pólya operators. All previously known unlabeled construction principles for Boltzmann samplers are special cases of our new results. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and nonplane unrooted trees, and tree-like structures in general, but also to families of graphs (such as cacti graphs and outerplanar graphs) and families of planar maps.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Complexity of Existential Positive First-Order Logic

Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logspace or complete for the class CSP(gamma)_NP under deterministic polynomial-time many-one reductions. Here, CSP(gamma)_NP is the class of problems that can be reduced to the Constraint Satisfaction Problem of gamma under non-deterministic polynomial-time many-one reductions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets

A famous result by Jeavons, Cohen, and Gyssens shows that every constraint satisfaction problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called universal-algebraic approach to a systematic theory of tractability and hardness in finite domain constraint satisfaction. Not surprisingly, the theorem of Jeavons et al. fails for arbitrary infinite domain CSPs. Many CSPs of practical interest, though, and in particular those CSPs that are motivated by qualitative reasoning calculi from Artificial Intelligence, can be formulated with constraint languages that are rather well-behaved from a model-theoretic point of view. In particular, the automorphism group of these constraint languages tends to be large in the sense that the number of orbits of n-subsets of the automorphism group is bounded by some function in n. In this paper we present a generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n-subsets grows sub-exponentially in n, and prove that preservation under a semi-lattice operation for such CSPs implies polynomial-time tractability. Unlike the result of Jeavons et al., this includes many CSPs that cannot be solved by Datalog.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Reducts of Ramsey structures

One way of studying a relational structure is to investigate functions which are related to that structure and which leave certain aspects of the structure invariant. Examples are the automorphism group, the self-embedding monoid, the endomorphism monoid, or the polymorphism clone of a structure. Such functions can be particularly well understood when the relational structure is countably infinite and has a first-order definition in another relational structure which has a finite language, is totally ordered and homogeneous, and has the Ramsey property. This is because in this situation, Ramsey theory provides the combinatorial tool for analyzing these functions -- in a certain sense, it allows to represent such functions by functions on finite sets. This is a survey of results in model theory and theoretical computer science obtained recently by the authors in this context. In model theory, we approach the problem of classifying the reducts of countably infinite ordered homogeneous Ramsey structures in a finite language, and certain decidability questions connected with such reducts. In theoretical computer science, we use the same combinatorial methods in order to classify the computational complexity for various classes of infinite-domain constraint satisfaction problems. While the first set of applications is obviously of an infinitary character, the second set concerns genuinely finitary problems -- their unifying feature is that the same tools from Ramsey theory are used in their solution.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Rooted Phylogeny Problems

Several computational problems in phylogenetic reconstruction can be formulated as restrictions of the following general problem: given a formula in conjunctive normal form where the literals are rooted triples, is there a rooted binary tree that satisfies the formula? If the formulas do not contain disjunctions, the problem becomes the famous rooted triple consistency problem, which can be solved in polynomial time by an algorithm of Aho, Sagiv, Szymanski, and Ullman. If the clauses in the formulas are restricted to disjunctions of negated triples, Ng, Steel, and Wormald showed that the problem remains NP-complete. We systematically study the computational complexity of the problem for all such restrictions of the clauses in the input formula. For certain restricted disjunctions of triples we present an algorithm that has sub-quadratic running time and is asymptotically as fast as the fastest known algorithm for the rooted triple consistency problem. We also show that any restriction of the general rooted phylogeny problem that does not fall into our tractable class is NP-complete, using known results about the complexity of Boolean constraint satisfaction problems. Finally, we present a pebble game argument that shows that the rooted triple consistency problem (and also all generalizations studied in this paper) cannot be solved by Datalog.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Surjective Homomorphism Problems -- a Survey

We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction and compaction. In comparison with these problems, surjective homomorphism problems seem to be harder to classify and we examine especially three concrete problems that have arisen from the literature, two of which remain of open complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

All reducts of the random graph are model-complete

We study locally closed transformation monoids which contain the automorphism group of the random graph. We show that such a transformation monoid is locally generated by the permutations in the monoid, or contains a constant operation, or contains an operation that maps the random graph injectively to an induced subgraph which is a clique or an independent set. As a corollary, our techniques yield a new proof of Simon Thomas' classification of the five closed supergroups of the automorphism group of the random graph; our proof uses different Ramsey-theoretic tools than the one given by Thomas, and is perhaps more straightforward. Since the monoids under consideration are endomorphism monoids of relational structures definable in the random graph, we are able to draw several model-theoretic corollaries: One consequence of our result is that all structures with a first-order definition in the random graph are model-complete. Moreover, we obtain a classification of these structures up to existential interdefinability.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Finite trees are Ramsey under topological embeddings

We show that the class of finite rooted binary plane trees is a Ramsey class (with respect to topological embeddings that map leaves to leaves). That is, for all such trees P,H and every natural number k there exists a tree T such that for every k-coloring of the (topological) copies of P in T there exists a (topological) copy H' of H in T such that all copies of P in H' have the same color. When the trees are represented by the so-called rooted triple relation, the result gives rise to a Ramsey class of relational structures with respect to induced substructures.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The reducts of equality up to primitive positive interdefinability

We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a classification of the reducts of the logic of equality. It turns out that there exists a continuum of such reducts. Equivalently, expressed in the language of universal algebra, we classify those locally closed clones over a countable domain which contain all permutations of the domain.

0 citations0 reviewsNo code linkedOpen access